A算法人工智能课程设计_第1页
A算法人工智能课程设计_第2页
A算法人工智能课程设计_第3页
A算法人工智能课程设计_第4页
A算法人工智能课程设计_第5页
已阅读5页,还剩6页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、人工智能( A* 算法)05 级计算机二班 姓名 : 学号 :20054044054、 A* 算法概述A*算法是到目前为止最快的一种计算最短路径的算法,但它一种较优算法,即它一般只能找到较优解,而非最优解, 但由于其高效性,使其在实时系统、人工智能 等方面应用极其广泛。A* 算法结合了启发式方法(这种方法通过充分利用图给出的信息来动态地作 出决定而使搜索次数大大降低) 和形式化方法 (这种方法不利用图给出的信息, 而仅通 过数学的形式分析,如 Dijkstra 算法)。它通过一个估价函数( Heuristic Function ) f(h)来估计图中的当前点 p到终点的距离(带权值),并由此决

2、定它的搜索方向, 当这条 路径失败时,它会尝试其它路径。因而我们可以发现,A*算法成功与否的关键在于估价函数的正确选择,从理 论上说, 一个完全正确的估价函数是可以非常迅速地得到问题的正确解答,但一般完全正确的估价函数是得不到的,因而 A*算法不能保证它每次都得到正确解答。一个不理 想的估价函数可能会使它工作得很慢,甚至会给出错误的解答。为了提高解答的正确性,我们可以适当地降低估价函数的值,从而使之进行 更多的搜索, 但这是以降低它的速度为代价的, 因而我们可以根据实际对解答的速度和 正确性的要求而设计出不同的方案,使之更具弹性。、 A* 算法分析众所周知, 对图的表示可以采用数组或链表, 而

3、且这些表示法也各也优缺点, 数组 可以方便地实现对其中某个元素的存取, 但插入和删除操作却很困难, 而链表则利于插 入和删除,但对某个特定元素的定位却需借助于搜索。而A*算法则需要快速插入和删除所求得的最优值以及可以对当前结点以下结点的操作,因而数组或链表都显得太通用了,用来实现 A*算法会使速度有所降低。要实现这些,可以通过二分树、跳转表等数 据结构来实现,我采用的是简单而高效的带优先权的堆栈,经实验表明,一个1000个 结点的图, 插入而且移动一个排序的链表平均需 500次比较和 2次移动; 未排序的链表 平均需 1000 次比较和 2 次移动;而堆仅需 10 次比较和 10 次移动。需要

4、指出的是,当 结点数 n 大于 10,000 时,堆将不再是正确的选择,但这足已满足我们一般的要求。求出2D的迷宫中起始点 S到目标点E的最短路径?算法:findpath()把S点加入树根(各点所在的树的高度表示从S点到该点所走过的步数);把 S 点加入排序队列(按该点到 E 点的距离排序 +走过的步数从小到大排序) ;1、排序队列 sort_queue 中距离最小的第一个点出列,并保存入 store_queue 中2、 从出列的点出发,分别向4个(或 8 个)方向中的一个各走出一步3、并估算第 2 步所走到位置到目标点的距离,并把该位置加入树,最后把该点按 距离从小到大排序后并放入队列中(由

5、 trytile 函数实现)4、 如果该点从四个方向上都不能移动,则把该点从store_queue 中删除5、 回到第一点,直到找到E点则结束从目标点回溯树,直到树根则可以找到最佳路径,并保存在path 中文末附带的程序参考了风云的最短路径代码,并加以改进和优化:把原来用于存放已处理节点的堆栈改为队列( store_queue ),这样在从 sort_queue 队列出 列时可直接放入 store_queue 中。解除了地图大小的限制(如果有 64K 内存限制时,地图大小只能是180x180 ) 。删除了原程序中的一些冗余,见程序中的注释。程序继续使用 dis_map 数组保存各点历史历史最佳

6、距离,也包含了某点是否已经经过的信 息,虽然这样做可能会比使用链表多用一些内存,但是在搜索时可以节省不时间。程 序更具有实用性, 可直接或修改后运用于你的程序中, 但请你使用该代码后 应该返回一 些信息给我,如算法的改进或使用于什么程序等。三、A*算法程序本程序可以用 Borland C+或DJGPP编译#include #include #include #include #define tile_num(x,y) (y)*map_w+(x) /将 x,y 坐标转换为地图上块的编号#define tile_x(n) (n)%map_w) /由块编号得出 x,y 坐标#define tile_

7、y(n) (n)/map_w)#define MAPMAXSIZE 180 /地图面积最大为 180x180,如果没有64K内存限制可以更大#define MAXINT 32767/ 树结构 , 比较特殊 , 是从叶节点向根节点反向链接,方便从叶节点找到根节点typedef struct tree_node *TREE;struct tree_node int h; / 节点所在的高度,表示从起始点到该节点所有的步数int tile; / 该节点的位置TREE father; / 该节点的上一步;/ 链接结构,用于保存处理过的和没有处理过的结点typedef struct link_node

8、*LINK;struct link_node TREE node;int f;LINK next;LINK sort_queue; / 保存没有处理的行走方法的节点LINK store_queue; / 保存已经处理过的节点 ( 搜索完后释放 )unsigned char * map; /地图数据unsigned int * dis_map; /保存搜索路径时 , 中间目标地最优解int map_w,map_h; / 地图宽和高int start_x,start_y,end_x,end_y; /地点 , 终点坐标/ 初始化队列void init_queue()sort_queue=(LINK)

9、malloc(sizeof(*sort_queue); sort_queue-node=NULL;sort_queue-f=-1; sort_queue-next=(LINK)malloc(sizeof(*sort_queue); sort_queue-next-node=NULL;sort_queue-next-f=MAXINT;sort_queue-next-next=NULL; store_queue=(LINK)malloc(sizeof(*store_queue); store_queue-node=NULL;store_queue-f=-1;store_queue-next=NUL

10、L;/ 待处理节点入队列 , 依靠对目的地估价距离插入排序void enter_queue(TREE node,int f)LINK p=sort_queue,father,q;while(fp-f) father=p;p=p-next;assert(p);q=(LINK)malloc(sizeof(*q);assert(sort_queue); q-f=f,q-node=node,q-next=p;father-next=q;/ 将离目的地估计最近的方案出队列TREE get_from_queue()LINK bestchoice=sort_queue-next;LINK next=sort

11、_queue-next-next; sort_queue-next=next; bestchoice-next=store_queue-next; store_queue-next=bestchoice;return bestchoice-node;/ 释放栈顶节点void pop_stack()LINK s=store_queue-next;assert(s);store_queue-next=store_queue-next-next; free(s-node);free(s);/ 释放申请过的所有节点void freetree()int i;LINK p;while(store_queu

12、e) p=store_queue;free(p-node); store_queue=store_queue-next;free(p);while (sort_queue) p=sort_queue;free(p-node);sort_queue=sort_queue-next;free(p);/ 估价函数 ,估价 x,y 到目的地的距离 , 估计值必须保证比实际值小int judge(int x,int y)int distance;distance=abs(end_x-x)+abs(end_y-y);return distance;/ 尝试下一步移动到 x,y 可行否int trytile

13、(int x,int y,TREE father)TREE p=father;int h;if (maptile_num(x,y)!= ) return 1; /如果 (x,y) 处是障碍 , 失败h=father-h+1;(x,y) 失if (h=dis_maptile_num(x,y) return 1; / 如果曾经有更好的方案移动到 败dis_maptile_num(x,y)=h; /记录这次到 (x,y) 的距离为历史最佳距离/ 将这步方案记入待处理队列 p=(TREE)malloc(sizeof(*p);p-father=father;p-h=father-h+1;p-tile=t

14、ile_num(x,y); enter_queue(p,p-h+judge(x,y); return 0;/ 路径寻找主函数int * findpath(void)TREE root;int i,j;int * path;memset(dis_map,0xff,map_h*map_w*sizeof(*dis_map); init_queue();root=(TREE)malloc(sizeof(*root);root-tile=tile_num(start_x,start_y);root-h=0;root-father=NULL;enter_queue(root,judge(start_x,s

15、tart_y);for (;) int x,y,child;TREE p;root=get_from_queue();if (root=NULL) return NULL;x=tile_x(root-tile);y=tile_y(root-tile);if (x=end_x & y=end_y) break; / 达到目的地成功返回child=trytile(x,y-1,root); /尝试向上移动child&=trytile(x,y+1,root); /尝试向下移动child&=trytile(x-1,y,root); /尝试向左移动child&=trytile(x+1,y,root); /

16、尝试向右移动if (child!=0)pop_stack(); / 如果四个方向均不能移动 , 释放这个死节点 path=(int*)malloc(root-h+2)*sizeof(int); assert(path);for (i=0;root;i+) pathi=root-tile; root=root-father; pathi=-1;freetree();return path;void printpath(int *path)int i;if(path=NULL) return ;for (i=0;pathi=0;i+) gotoxy(tile_x(pathi)+1,tile_y(p

17、athi)+1); cprintf(.);int readmap()FILE *f;int i,j;f=fopen(map.dat,r);assert(f);fscanf(f,%d,%dn,&map_w,&map_h); map=malloc(map_w*map_h+1);assert(map);for(i=0;i fgets(map+tile_num(0,i),map_w+2,f);fclose(f);start_x=-1,end_x=-1;for (i=0;i for (j=0;j if (maptile_num(j,i)=s) maptile_num(j,i)= ,start_x=j,s

18、tart_y=i;if (maptile_num(j,i)=e) maptile_num(j,i)= ,end_x=j,end_y=i; assert(start_x=0 & end_x=0); dis_map=malloc(map_w*map_h*sizeof(*dis_map); assert(dis_map);return 0;void showmap()int i,j;clrscr();for (i=0;i gotoxy(1,i+1);for (j=0;j if (maptile_num(j,i)!= ) cprintf(O);else cprintf( );gotoxy(start_

19、x+1,start_y+1);cprintf(s);gotoxy(end_x+1,end_y+1);cprin tf(e); int mai n()int * path;readmap();showmap();getch();path=fi ndpath();prin tpath(path);if(dis_map) free(dis_map);if(path) free(path);if(map) free(map);getch();return 0;四、运行结果口口 n cin 口口1 口 n 口 u 口 n 口 nnnon nnn ruci n nno 口 仃门 口 nnm 口口口 口口 n nnnn n. HKnr n n n n n n 口 on roc nnn nn n 100 厂厂口口r0OQCiQODOO10

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论