A算法人工智能課程設計

1、人工智能（A*算法）一、A*算法概述A*算法是到目前為止最快的一種計算最短路徑的算法，但它一種較優(yōu)算法，即它一般只能找到較優(yōu)解，而非最優(yōu)解，但由于其高效性，使其在實時系統(tǒng)、人工智能等方面應用極其廣泛。A*算法結(jié)合了啟發(fā)式方法（這種方法通過充分利用圖給出的信息來動態(tài)地作出決定而使搜索次數(shù)大大降低）和形式化方法（這種方法不利用圖給出的信息，而僅通過數(shù)學的形式分析，如 Dijkstra 算法）。它通過一個估價函數(shù)（Heuristic Function ） f（h）來估計圖中的當前點 p到終點的距離（帶權值），并由此決定它的搜索方向， 當這條 路徑失敗時，它會嘗試其它路徑。因而我們可以發(fā)現(xiàn)，A*算法成

2、功與否的關鍵在于估價函數(shù)的正確選擇，從理 論上說，一個完全正確的估價函數(shù)是可以非常迅速地得到問題的正確解答，但一般完全正確的估價函數(shù)是得不到的，因而A*算法不能保證它每次都得到正確解答。一個不理想的估價函數(shù)可能會使它工作得很慢，甚至會給出錯誤的解答。為了提高解答的正確性，我們可以適當?shù)亟档凸纼r函數(shù)的值，從而使之進行 更多的搜索，但這是以降低它的速度為代價的，因而我們可以根據(jù)實際對解答的速度和正確性的要求而設計出不同的方案，使之更具彈性。二、A*算法分析眾所周知，對圖的表示可以采用數(shù)組或鏈表，而且這些表示法也各也優(yōu)缺點，數(shù)組可以方便地實現(xiàn)對其中某個元素的存取，但插入和刪除操作卻很困難，而鏈表則利

3、于插入和刪除，但對某個特定元素的定位卻需借助于搜索。而A*算法則需要快速插入和刪除所求得的最優(yōu)值以及可以對當前結(jié)點以下結(jié)點的操作，因而數(shù)組或鏈表都顯得太通用了，用來實現(xiàn) A*算法會使速度有所降低。要實現(xiàn)這些，可以通過二分樹、跳轉(zhuǎn)表等數(shù) 據(jù)結(jié)構來實現(xiàn)，我采用的是簡單而高效的帶優(yōu)先權的堆棧，經(jīng)實驗表明，一個1000個結(jié)點的圖，插入而且移動一個排序的鏈表平均需500次比較和2次移動；未排序的鏈表平均需1000次比較和2次移動；而堆僅需10次比較和10次移動。需要指出的是，當 結(jié)點數(shù)n大于10, 000時，堆將不再是正確的選擇，但這足已滿足我們一般的要求。求出2D的迷宮中起始點 S到目標點E的最短路徑

4、？算法:findpath（）（把S點加入樹根（各點所在的樹的高度表示從S點到該點所走過的步數(shù)）；把S點加入排序隊列（按該點到E點的距離排序+走過的步數(shù)從小到大排序）；1、排序隊列sort_queue中距離最小的第一個點出列，并保存入store_queue中2、從出列的點出發(fā)，分別向 4個（或8個）方向中的一個各走出一步3、并估算第2步所走到位置到目標點的距離，并把該位置加入樹，最后把該點按距離從小到大排序后并放入隊列中（由 trytile函數(shù)實現(xiàn)）4、如果該點從四個方向上都不能移動，則把該點從store_queue中刪除5、回到第一點，直到找到E點則結(jié)束從目標點回溯樹，直到樹根則可以找到最佳路

5、徑，并保存在 path口中文末附帶的程序參考了風云的最短路徑代碼，并加以改進和優(yōu)化：把原來用于存放已處理節(jié)點的堆棧改為隊列（store_queue ）,這樣在從sort_queue隊列出列時可直接放入 store_queue中。解除了地圖大小的限制（如果有64K內(nèi)存限制時，地圖大小只能是180x180）。刪除了原程序中的一些冗余，見程序中的注釋。程序繼續(xù)使用dis_map數(shù)組保存各點歷史歷史最佳距離，也包含了某點是否已經(jīng)經(jīng)過的信息，雖然這樣做可能會比使用鏈表多用一些內(nèi)存，但是在搜索時可以節(jié)省不時間。程序更具有實用性，可直接或修改后運用于你的程序中，但請你使用該代碼后應該返回一些信息給我，如算法

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坐標轉(zhuǎn)換為地圖上塊的編號#define tile_x(n) (n)%map_w) / 由塊編號得出 x,y 坐標#define tile_y(n) (n)/map_w)#define MAPMAXSIZE 180 /地圖面積最大為 18

7、0x180 ,如果沒有64K內(nèi)存限制可以更大#define MAXINT 32767/樹結(jié)構，比較特殊，是從葉節(jié)點向根節(jié)點反向鏈接，方便從葉節(jié)點找到根節(jié)點typedef struct tree_node *TREE;struct tree_node int h; /節(jié)點所在的高度，表示從起始點到該節(jié)點所有的步數(shù)int tile; / 該節(jié)點的位置TREE father; /該節(jié)點的上一步;/鏈接結(jié)構，用于保存處理過的和沒有處理過的結(jié)點typedef struct link_node *LINK;struct link_node TREE node;int f;LINK next;LINK so

8、rt_queue; /保存沒有處理的行走方法的節(jié)點LINK store_queue; /保存已經(jīng)處理過的節(jié)點(搜索完后釋放)unsigned char * map; /地圖數(shù)據(jù)unsigned int * dis_map; /保存搜索路徑時，中間目標地最優(yōu)解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;/待處理節(jié)點入隊列，依靠對目的地估價距離插入排序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;/釋放棧頂節(jié)點void pop_stack()LINK s=store_queue->next;assert(s);store_queue->next=store_queue->next->next;free(s->node);free(s);/釋放申請過的所有節(jié)點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);)/估價函數(shù)，估價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; /如果曾經(jīng)有更好的方案移動到(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;/路徑尋找主函數(shù)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(); /如果四個方向均不能移動，釋放這個死節(jié)點)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()