A算法人工智能課程設(shè)計(jì)

1、人工智能（ A* 算法）05 級(jí)計(jì)算機(jī)二班 姓名 : 學(xué)號(hào) :20054044054、 A* 算法概述A*算法是到目前為止最快的一種計(jì)算最短路徑的算法，但它一種較優(yōu)算法，即它一般只能找到較優(yōu)解，而非最優(yōu)解， 但由于其高效性，使其在實(shí)時(shí)系統(tǒng)、人工智能 等方面應(yīng)用極其廣泛。A* 算法結(jié)合了啟發(fā)式方法（這種方法通過(guò)充分利用圖給出的信息來(lái)動(dòng)態(tài)地作 出決定而使搜索次數(shù)大大降低） 和形式化方法 （這種方法不利用圖給出的信息， 而僅通 過(guò)數(shù)學(xué)的形式分析，如 Dijkstra 算法）。它通過(guò)一個(gè)估價(jià)函數(shù)（ Heuristic Function ） f（h）來(lái)估計(jì)圖中的當(dāng)前點(diǎn) p到終點(diǎn)的距離（帶權(quán)值），并由此決

2、定它的搜索方向， 當(dāng)這條 路徑失敗時(shí)，它會(huì)嘗試其它路徑。因而我們可以發(fā)現(xiàn)，A*算法成功與否的關(guān)鍵在于估價(jià)函數(shù)的正確選擇，從理 論上說(shuō)， 一個(gè)完全正確的估價(jià)函數(shù)是可以非常迅速地得到問(wèn)題的正確解答，但一般完全正確的估價(jià)函數(shù)是得不到的，因而 A*算法不能保證它每次都得到正確解答。一個(gè)不理 想的估價(jià)函數(shù)可能會(huì)使它工作得很慢，甚至?xí)o出錯(cuò)誤的解答。為了提高解答的正確性，我們可以適當(dāng)?shù)亟档凸纼r(jià)函數(shù)的值，從而使之進(jìn)行 更多的搜索， 但這是以降低它的速度為代價(jià)的， 因而我們可以根據(jù)實(shí)際對(duì)解答的速度和 正確性的要求而設(shè)計(jì)出不同的方案，使之更具彈性。、 A* 算法分析眾所周知， 對(duì)圖的表示可以采用數(shù)組或鏈表， 而

3、且這些表示法也各也優(yōu)缺點(diǎn)， 數(shù)組 可以方便地實(shí)現(xiàn)對(duì)其中某個(gè)元素的存取， 但插入和刪除操作卻很困難， 而鏈表則利于插 入和刪除，但對(duì)某個(gè)特定元素的定位卻需借助于搜索。而A*算法則需要快速插入和刪除所求得的最優(yōu)值以及可以對(duì)當(dāng)前結(jié)點(diǎn)以下結(jié)點(diǎn)的操作，因而數(shù)組或鏈表都顯得太通用了，用來(lái)實(shí)現(xiàn) A*算法會(huì)使速度有所降低。要實(shí)現(xiàn)這些，可以通過(guò)二分樹(shù)、跳轉(zhuǎn)表等數(shù) 據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，我采用的是簡(jiǎn)單而高效的帶優(yōu)先權(quán)的堆棧，經(jīng)實(shí)驗(yàn)表明，一個(gè)1000個(gè) 結(jié)點(diǎn)的圖， 插入而且移動(dòng)一個(gè)排序的鏈表平均需 500次比較和 2次移動(dòng)； 未排序的鏈表 平均需 1000 次比較和 2 次移動(dòng)；而堆僅需 10 次比較和 10 次移動(dòng)。需要

4、指出的是，當(dāng) 結(jié)點(diǎn)數(shù) n 大于 10，000 時(shí)，堆將不再是正確的選擇，但這足已滿足我們一般的要求。求出2D的迷宮中起始點(diǎn) S到目標(biāo)點(diǎn)E的最短路徑？算法：findpath（）把S點(diǎn)加入樹(shù)根（各點(diǎn)所在的樹(shù)的高度表示從S點(diǎn)到該點(diǎn)所走過(guò)的步數(shù)）；把 S 點(diǎn)加入排序隊(duì)列（按該點(diǎn)到 E 點(diǎn)的距離排序 +走過(guò)的步數(shù)從小到大排序） ；1、排序隊(duì)列 sort_queue 中距離最小的第一個(gè)點(diǎn)出列，并保存入 store_queue 中2、 從出列的點(diǎn)出發(fā)，分別向4個(gè)（或 8 個(gè)）方向中的一個(gè)各走出一步3、并估算第 2 步所走到位置到目標(biāo)點(diǎn)的距離，并把該位置加入樹(shù)，最后把該點(diǎn)按 距離從小到大排序后并放入隊(duì)列中（由

5、 trytile 函數(shù)實(shí)現(xiàn)）4、 如果該點(diǎn)從四個(gè)方向上都不能移動(dòng)，則把該點(diǎn)從store_queue 中刪除5、 回到第一點(diǎn)，直到找到E點(diǎn)則結(jié)束從目標(biāo)點(diǎn)回溯樹(shù)，直到樹(shù)根則可以找到最佳路徑，并保存在path 中文末附帶的程序參考了風(fēng)云的最短路徑代碼，并加以改進(jìn)和優(yōu)化：把原來(lái)用于存放已處理節(jié)點(diǎn)的堆棧改為隊(duì)列（ store_queue ），這樣在從 sort_queue 隊(duì)列出 列時(shí)可直接放入 store_queue 中。解除了地圖大小的限制（如果有 64K 內(nèi)存限制時(shí)，地圖大小只能是180x180 ） 。刪除了原程序中的一些冗余，見(jiàn)程序中的注釋。程序繼續(xù)使用 dis_map 數(shù)組保存各點(diǎn)歷史歷史最佳

6、距離，也包含了某點(diǎn)是否已經(jīng)經(jīng)過(guò)的信 息，雖然這樣做可能會(huì)比使用鏈表多用一些內(nèi)存，但是在搜索時(shí)可以節(jié)省不時(shí)間。程 序更具有實(shí)用性， 可直接或修改后運(yùn)用于你的程序中， 但請(qǐng)你使用該代碼后 應(yīng)該返回一 些信息給我，如算法的改進(jìn)或使用于什么程序等。三、A*算法程序本程序可以用 Borland C+或DJGPP編譯#include #include #include #include #define tile_num(x,y) (y)*map_w+(x) /將 x,y 坐標(biāo)轉(zhuǎn)換為地圖上塊的編號(hào)#define tile_x(n) (n)%map_w) /由塊編號(hào)得出 x,y 坐標(biāo)#define tile_

7、y(n) (n)/map_w)#define MAPMAXSIZE 180 /地圖面積最大為 180x180，如果沒(méi)有64K內(nèi)存限制可以更大#define MAXINT 32767/ 樹(shù)結(jié)構(gòu) , 比較特殊 , 是從葉節(jié)點(diǎn)向根節(jié)點(diǎn)反向鏈接，方便從葉節(jié)點(diǎn)找到根節(jié)點(diǎn)typedef struct tree_node *TREE;struct tree_node int h; / 節(jié)點(diǎn)所在的高度，表示從起始點(diǎn)到該節(jié)點(diǎn)所有的步數(shù)int tile; / 該節(jié)點(diǎn)的位置TREE father; / 該節(jié)點(diǎn)的上一步;/ 鏈接結(jié)構(gòu)，用于保存處理過(guò)的和沒(méi)有處理過(guò)的結(jié)點(diǎn)typedef struct link_node

8、*LINK;struct link_node TREE node;int f;LINK next;LINK sort_queue; / 保存沒(méi)有處理的行走方法的節(jié)點(diǎn)LINK store_queue; / 保存已經(jīng)處理過(guò)的節(jié)點(diǎn) ( 搜索完后釋放 )unsigned char * map; /地圖數(shù)據(jù)unsigned int * dis_map; /保存搜索路徑時(shí) , 中間目標(biāo)地最優(yōu)解int map_w,map_h; / 地圖寬和高int start_x,start_y,end_x,end_y; /地點(diǎn) , 終點(diǎn)坐標(biāo)/ 初始化隊(duì)列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;/ 待處理節(jié)點(diǎn)入隊(duì)列 , 依靠對(duì)目的地估價(jià)距離插入排序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;/ 將離目的地估計(jì)最近的方案出隊(duì)列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;/ 釋放棧頂節(jié)點(diǎn)void pop_stack()LINK s=store_queue-next;assert(s);store_queue-next=store_queue-next-next; free(s-node);free(s);/ 釋放申請(qǐng)過(guò)的所有節(jié)點(diǎn)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);/ 估價(jià)函數(shù) ,估價(jià) x,y 到目的地的距離 , 估計(jì)值必須保證比實(shí)際值小int judge(int x,int y)int distance;distance=abs(end_x-x)+abs(end_y-y);return distance;/ 嘗試下一步移動(dòng)到 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; / 如果曾經(jīng)有更好的方案移動(dòng)到 敗dis_maptile_num(x,y)=h; /記錄這次到 (x,y) 的距離為歷史最佳距離/ 將這步方案記入待處理隊(duì)列 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;/ 路徑尋找主函數(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,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; / 達(dá)到目的地成功返回child=trytile(x,y-1,root); /嘗試向上移動(dòng)child&=trytile(x,y+1,root); /嘗試向下移動(dòng)child&=trytile(x-1,y,root); /嘗試向左移動(dòng)child&=trytile(x+1,y,root); /

16、嘗試向右移動(dòng)if (child!=0)pop_stack(); / 如果四個(gè)方向均不能移動(dòng) , 釋放這個(gè)死節(jié)點(diǎn) 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;四、運(yùn)行結(jié)果口口 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