A算法人工智能课程设计

1、A算法人工智能课程设计文档编制序号 LKKJDT-LLE0828-LLETD298-POI08人工智能（A*算法）一、A*算法概述A*算法是到目前为止最快的一种计算最短路径的算法，但它一种较 优算法，即它一般只能找到较优解，而非最优解，但由于其高效性，使 其在实时系统、人工智能等方面应用极其广泛。A*算法结合了启发式方法（这种方法通过充分利用图给出的信息 来动态地作出决定而使搜索次数大大降低）和形式化方法（这种方法不利 用图给出的信息，而仅通过数学的形式分析，如Dijkstra算法）。它通过 个估价函数（Heuristic Function） f （h）来估计图中的当前点p到终点 的距离（带权

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

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

4、, 000时，堆将不再是正确 的选择，但这足已满足我们一般的要求。求出2D的迷宫中起始点S到目标点E的最短路径？算法：findpath （）把S点加入树根（各点所在的树的高度表示从S点到该点所走过的步 数）；把s点加入排序队列（按该点到E点的距离排序+走过的步数从小到大 排序）；1、排序队列sort_queue中距离最小的第一个点出列，并保存入 store_queue 中2、从出列的点出发，分别向4个（或8个）方向中的一个各走出一步3、并估算第2步所走到位置到目标点的距离，并把该位置加入树，最后把该点按距离从小到大排序后并放入队列中（由trytile函数实现）4、如果该点从四个方向上都不能移动

5、，则把该点从store_queue中删 除5、回到第一点，直到找到E点则结束从目标点回溯树，直到树根则可以找到最佳路径，并保存在“th中文末附带的程序参考了风云的最短路径代码，并加以改进和优化：把原来用于存放已处理节点的堆栈改为队列（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) int readmap ()FILE *f;int i, j；f二fopen(", r)；assert(f);fscanf (f,，z%d, %dnz，, &map

7、_w, &map_h);map=malloc (map_w*map_h+l);assert(map);for (i=0; i fgets (map+tile_num(O, i), map_w+2, f);fclose(f);start_x=-l, 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)二'&

8、#39;，end_x=j, end_y二i ; assert(start_x>=0 && end_x>=0);dis_map=malloc(map_w*map_h*s i zeof (*dis_map);assert(dis_map);void showmap () int i, j；clrscr ();for (i=0;i gotoxy(1, i+1):for (j=0; j if (maptile_num(j, i) !二'')cprintf ("0");else cprintf (，? ”)；gotoxy (start_x+

9、l, start_y+l);cprintf("s");gotoxy(end_x+l, end_y+l);cprintf("e");int main()int * path;readmap ();showmap ();getch();path=f indpathO ;printpath(path);if(dis_map) free(dis_map);if (path) free(path);if(map) free(map);getch();return 0;<!-if !supportLineBreakNewLineZ-><!一一end

10、if一一>四.运行结果oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooO OCOOOOOoooooo00000000ooooooooooooooooooooooooQOOO000000000000000OOOOOOOOOOOCOOOOOOOOOOQOOO000 0000000 00000000oooooaaooooooooocaooooooaoooaooooooooooaooo ooooooooooooooooooooooooooooaoooocoooooooaoooooooooaoQOOoaoooooaoooocooooooooooaoooooooooOOQOOOOOOOOOOOOOOOQOOOOOOOOOCOOOOOOOO00e 000ooaaoaaaooOOOOOOO 0000000000 00000000aoooo ooodc oooooo aoocDCDC ooooao ooooa cooooa oaoooc oaooo aoooo