A算法人工智能课程设计

1、人工智能（A*算法）一、A*算法概述A*算法是到目前为止最快的一种计算最短路径的算法，但它一种较优算法，即它一般只能找到较优解，而非最优解，但由于其高效性，使其在实时系统、人工智能等方面应用极其广泛。A*算法结合了启发式方法（这种方法通过充分利用图给出的信息来动态地作出决定而使搜索次数大大降低）和形式化方法（这种方法不利用图给出的信息，而仅通过数学的形式分析，如 Dijkstra 算法）。它通过一个估价函数（Heuristic Function ） f（h）来估计图中的当前点 p到终点的距离（带权值），并由此决定它的搜索方向， 当这条 路径失败时，它会尝试其它路径。因而我们可以发现，A*算法成

2、功与否的关键在于估价函数的正确选择，从理 论上说，一个完全正确的估价函数是可以非常迅速地得到问题的正确解答，但一般完全正确的估价函数是得不到的，因而A*算法不能保证它每次都得到正确解答。一个不理想的估价函数可能会使它工作得很慢，甚至会给出错误的解答。为了提高解答的正确性，我们可以适当地降低估价函数的值，从而使之进行 更多的搜索，但这是以降低它的速度为代价的，因而我们可以根据实际对解答的速度和正确性的要求而设计出不同的方案，使之更具弹性。二、A*算法分析众所周知，对图的表示可以采用数组或链表，而且这些表示法也各也优缺点，数组可以方便地实现对其中某个元素的存取，但插入和删除操作却很困难，而链表则利

3、于插入和删除，但对某个特定元素的定位却需借助于搜索。而A*算法则需要快速插入和删除所求得的最优值以及可以对当前结点以下结点的操作，因而数组或链表都显得太通用了，用来实现 A*算法会使速度有所降低。要实现这些，可以通过二分树、跳转表等数 据结构来实现，我采用的是简单而高效的带优先权的堆栈，经实验表明，一个1000个结点的图，插入而且移动一个排序的链表平均需500次比较和2次移动；未排序的链表平均需1000次比较和2次移动；而堆仅需10次比较和10次移动。需要指出的是，当 结点数n大于10, 000时，堆将不再是正确的选择，但这足已满足我们一般的要求。求出2D的迷宫中起始点 S到目标点E的最短路径

4、？算法:findpath（）（把S点加入树根（各点所在的树的高度表示从S点到该点所走过的步数）；把S点加入排序队列（按该点到E点的距离排序+走过的步数从小到大排序）；1、排序队列sort_queue中距离最小的第一个点出列，并保存入store_queue中2、从出列的点出发，分别向 4个（或8个）方向中的一个各走出一步3、并估算第2步所走到位置到目标点的距离，并把该位置加入树，最后把该点按距离从小到大排序后并放入队列中（由 trytile函数实现）4、如果该点从四个方向上都不能移动，则把该点从store_queue中删除5、回到第一点，直到找到E点则结束从目标点回溯树，直到树根则可以找到最佳路

5、径，并保存在 path口中文末附带的程序参考了风云的最短路径代码，并加以改进和优化：把原来用于存放已处理节点的堆栈改为队列（store_queue ）,这样在从sort_queue队列出列时可直接放入 store_queue中。解除了地图大小的限制（如果有64K内存限制时，地图大小只能是180x180）。删除了原程序中的一些冗余，见程序中的注释。程序继续使用dis_map数组保存各点历史历史最佳距离，也包含了某点是否已经经过的信息，虽然这样做可能会比使用链表多用一些内存，但是在搜索时可以节省不时间。程序更具有实用性，可直接或修改后运用于你的程序中，但请你使用该代码后应该返回一些信息给我，如算法

6、的改进或使用于什么程序等。三、A*算法程序本程序可以用 Borland C+或DJGP陶译#include <stdio.h>#include <conio.h>#include <stdlib.h>#include <mem.h>#define tile_num(x,y) (y)*map_w+(x) /将 x,y坐标转换为地图上块的编号#define tile_x(n) (n)%map_w) / 由块编号得出 x,y 坐标#define tile_y(n) (n)/map_w)#define MAPMAXSIZE 180 /地图面积最大为 18

7、0x180 ,如果没有64K内存限制可以更大#define MAXINT 32767/树结构，比较特殊，是从叶节点向根节点反向链接，方便从叶节点找到根节点typedef struct tree_node *TREE;struct tree_node int h; /节点所在的高度，表示从起始点到该节点所有的步数int tile; / 该节点的位置TREE father; /该节点的上一步;/链接结构，用于保存处理过的和没有处理过的结点typedef struct link_node *LINK;struct link_node TREE node;int f;LINK next;LINK so

8、rt_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; /地点,终点坐标/初始化队列sort_queue=(LINK)malloc(sizeof(*sort_queue);sort_queue->node=NULL;sort_queue->f=-1;sort_queue-

9、>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=NULL;/待处理节点入队列，依靠对目的地估价距离插入排序void enter_que

10、ue(TREE node,int f)(LINK p=sort_queue,father,q;while(f>p->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_queue->n

11、ext->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(

12、)int i;LINK p;while(store_queue)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);retur

13、n distance;)/尝试下一步移动到x,y 可行否int trytile(int x,int y,TREE father)(TREE p=father;int h;if (maptile_num(x,y)!='') return 1; /如果(x,y)处是障碍，失败h=father->h+1;if (h>=dis_maptile_num(x,y) return 1; /如果曾经有更好的方案移动到(x,y) 失败dis_maptile_num(x,y)=h; 记录这次到(x,y)的距离为历史最佳距离/将这步方案记入待处理队列p=(TREE)malloc(size

14、of(*p);p->father=father;p->h=father->h+1;p->tile=tile_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,

15、start_y);root->h=0;root->father=NULL;enter_queue(root,judge(start_x,start_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; /达至 U 目的地成功返回child=trytile(x,y-1,root); /尝试向上移动child

16、&=trytile(x,y+1,root); /尝试向下移动child&=trytile(x-1,y,root); /尝试向左移动child&=trytile(x+1,y,root); /尝试向右移动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();retu

17、rn path;)void printpath(int *path)int i;if(path=NULL) return ;for (i=0;pathi>=0;i+) gotoxy(tile_x(pathi)+1,tile_y(pathi)+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

18、*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,start_y=i;if (maptile_num(j,i)='e') maptile_num(j,i)=' ',end_x=j,end_y=i;assert(start_x>=

19、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_x+1,start_y+1);cprintf("s");gotoxy(end_x+1,end_y+1);cprintf("e");int main()int * path;readmap();showmap();getch();path=findpath();printpath(path);if(dis_map) free(dis_map);if(path) free(path);if(map) free(map);getch()