3A星算法試驗(yàn)報(bào)告

1、人工智能實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)二 A*算法實(shí)驗(yàn)I一、實(shí)驗(yàn)?zāi)康模菏煜ず驼莆諉l(fā)式搜索的定義、估價(jià)函數(shù)和算法過(guò)程，并利用A*算法求解N數(shù)碼難題，理解求解流程和搜索順序。二、實(shí)驗(yàn)原理：A*算法是一種啟發(fā)式圖搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。對(duì)于 一般的啟發(fā)式圖搜索，總是選擇估價(jià)函數(shù) f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。因此， f是根據(jù)需要找到一條最小代價(jià)路徑的觀點(diǎn)來(lái)估算節(jié)點(diǎn)的，所以，可考慮每個(gè)節(jié) 點(diǎn)n的估價(jià)函數(shù)值為兩個(gè)分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn) n的實(shí)際代價(jià)以及從節(jié)點(diǎn)n 到達(dá)目標(biāo)節(jié)點(diǎn)的估價(jià)代價(jià)。三、實(shí)驗(yàn)內(nèi)容：1 參考A*算法核心代碼，以8數(shù)碼問(wèn)題為例實(shí)現(xiàn)A*算法的求解程序（編程語(yǔ) 言不限），要求設(shè)計(jì)兩種不同的估價(jià)函

2、數(shù)。2在求解8數(shù)碼問(wèn)題的A*算法程序中，設(shè)置相同的初始狀態(tài)和目標(biāo)狀態(tài)，針對(duì) 不同的估價(jià)函數(shù)，求得問(wèn)題的解，并比較它們對(duì)搜索算法性能的影響， 包括擴(kuò)展 節(jié)點(diǎn)數(shù)、生成節(jié)點(diǎn)數(shù)等。3對(duì)于8數(shù)碼問(wèn)題，設(shè)置與上述2相同的初始狀態(tài)和目標(biāo)狀態(tài)，用寬度優(yōu)先搜 索算法（即令估計(jì)代價(jià)h（n）=0的A*算法）求得問(wèn)題的解，以及搜索過(guò)程中的擴(kuò) 展節(jié)點(diǎn)數(shù)、生成節(jié)點(diǎn)數(shù)。4上交源程序。四、實(shí)驗(yàn)結(jié)果：1 A*算法求解框圖:開(kāi)始蹲開(kāi)物節(jié)力F入襄申取出囊中沒(méi)有嘉柱到達(dá)韓點(diǎn),我家失敗鰭束，最大的市點(diǎn).挑到最短需彼，相索族切將節(jié)苴M人do« 囊并畤與漂可U 晤龍的下在tlwc 表史的寸巨簫人 到第一個(gè)震中2 在求解8數(shù)碼問(wèn)題

3、的A*算法程序中，設(shè)置相同的初始狀態(tài)和目標(biāo)狀態(tài)，針 對(duì)不同的估價(jià)函數(shù)，求得問(wèn)題的解，并比較它們對(duì)搜索算法性能的影響，包 括擴(kuò)展節(jié)點(diǎn)數(shù)、生成節(jié)點(diǎn)數(shù)等。：int calw(string s)計(jì)算該狀態(tài)的不在位數(shù) h(n)(int re=0;for(int i=0;i<9;i+) if(si!=ti) re+;/ 取一格局與目的格局位置不符的數(shù)碼數(shù)目return re;情輸入測(cè)試的組料1Case 1 ： 56012378 便部 HI 5 61 23 7 8，動(dòng)過(guò)程;Step 1：4 3 63 127 8Eftep 2 ：,S 6b 127 QStep 2B： 13 4S 2 7 6 5Seep

4、 21：1 3 &24 7 6 5Etep 22=136 2 4? & SSeep 23； 12 3 847 t 5地素節(jié)武執(zhí)8423請(qǐng)按任意鍵處續(xù)-h(n)/計(jì)算各數(shù)碼移到目的位置所需移：int calw(string s)計(jì)算該狀態(tài)的不在位數(shù)int re=0, i;int ss92;for(i = 0; i < 9; +i) 動(dòng)的距離總和sssi - 480 = i / 3;sssi - 481 = i % 3;)for(i = 0; i < 9; +i)re += (abs(ssi0 - sourcei0) + abs(ssi1 - sourcei1);return re;：int calw(string s)計(jì)算該狀態(tài)的不在位數(shù) h(n) return 0;/寬度優(yōu)先多動(dòng)過(guò)程:tep 2 .5 61 23 根據(jù)寬度優(yōu)先搜索算法和A*算法，分析啟發(fā)式搜索的特點(diǎn)。啟發(fā)式搜索算法使得搜索的效率好幾倍地提高。而不同的啟發(fā)式搜索算法差異也較大。總之啟發(fā)式搜索算法是由h(n)決定的，好的估價(jià)函數(shù)將決定算法性能的好壞。五、實(shí)驗(yàn)心得與體會(huì)通