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

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

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

3、而且這些表示法也各也優(yōu)缺點(diǎn)，數(shù)組可以方便地實(shí)現(xiàn)對其中某個(gè)元素的存取，但插入和刪除操作 卻很困難，而鏈表則利于插入和刪除，但對某個(gè)特定元素的定位卻需借助 于搜索。而腳算法則需要快速插入和刪除所求得的最優(yōu)值以及可以對當(dāng)前 結(jié)點(diǎn)以下結(jié)點(diǎn)的操作，因而數(shù)組或鏈表都顯得太通用了，用來實(shí)現(xiàn)側(cè)算法 會(huì)使速度有所降低。要實(shí)現(xiàn)這些，可以通過二分樹、跳轉(zhuǎn)表等數(shù)據(jù)結(jié)構(gòu)來 實(shí)現(xià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)。需要指出的是.當(dāng)結(jié)點(diǎn)數(shù)n大于10

4、, 000時(shí)，堆將不再是正確 的選擇，但這足已滿足我們一般的要求。求出2D的迷宮中起始點(diǎn)S到目標(biāo)點(diǎn)E的最短路徑？算法：findpath （）把S點(diǎn)加入樹根（各點(diǎn)所在的樹的高度表示從S點(diǎn)到該點(diǎn)所走過的步 數(shù)）；把s點(diǎn)加入排序隊(duì)列（按該點(diǎn)到E點(diǎn)的距離排序+走過的步數(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)的距離，并把該位置加入樹，最后把該點(diǎn)按距離從小到大排序后并放入隊(duì)列中（由trytile函數(shù)實(shí)現(xiàn)）4、如果該點(diǎn)從四個(gè)方向上都不能移動(dòng)

5、，則把該點(diǎn)從store_queue中刪 除5、回到第一點(diǎn)，直到找到E點(diǎn)則結(jié)束從目標(biāo)點(diǎn)回溯樹，直到樹根則可以找到最佳路徑，并保存在“th中文末附帶的程序參考了風(fēng)云的最短路徑代碼，并加以改進(jìn)和優(yōu)化：把原來用于存放已處理節(jié)點(diǎn)的堆棧改為隊(duì)列（store_queue）,這樣在從 sort_queue隊(duì)列出列時(shí)可直接放入store_queue中。解除了地圖大小的限制（如果有64K內(nèi)存限制時(shí)，地圖大小只能是180x180）。刪除了原程序中的一些冗余，見程序中的注釋。程序繼續(xù)使用dis_map數(shù)組保存各點(diǎn)歷史歷史最佳距離，也包含了某點(diǎn)是否已 經(jīng)經(jīng)過的信息，雖然這樣做可能會(huì)比使用鏈表多用一些內(nèi)存，但是在搜索時(shí)可

6、 以節(jié)省不時(shí)間。程序更具有實(shí)用性，可直接或修改后運(yùn)用于你的程序中，但請你使用該代碼后 應(yīng)該返回一些信息給我，如算法的改進(jìn)或使用于什么程序等。三、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一一>四.運(yùn)行結(jié)果oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooO OCOOOOOoooooo00000000ooooooooooooooooooooooooQOOO000000000000000OOOOOOOOOOOCOOOOOOOOOOQOOO000 0000000 00000000oooooaaooooooooocaooooooaoooaooooooooooaooo ooooooooooooooooooooooooooooaoooocoooooooaoooooooooaoQOOoaoooooaoooocooooooooooaoooooooooOOQOOOOOOOOOOOOOOOQOOOOOOOOOCOOOOOOOO00e 000ooaaoaaaooOOOOOOO 0000000000 00000000aoooo ooodc oooooo aoocDCDC ooooao ooooa cooooa oaoooc oaooo aoooo