迷宮尋路實驗報告

1、人工智能實驗報告實驗三A*算法實驗II一、實驗?zāi)康模菏煜ず驼莆誂*算法實現(xiàn)迷宮尋路功能，要求掌握啟發(fā)式函數(shù)的編寫以及各 類啟發(fā)式函數(shù)效果的比較。二、實驗原理：A*(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。公式表示為： f(n)=g(n)+h(n)，其中f(n)是節(jié)點n從初始點到目標(biāo)點的估價函數(shù)，g(n)是在 狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，h(n)是從n到目標(biāo)節(jié)點最佳路徑的 估計代價。保證找到最短路徑(最優(yōu)解的)條件，關(guān)鍵在于估價函數(shù)h(n)的選 ?。汗纼r值h(n)小于等于n到目標(biāo)節(jié)點的距離實際值，這種情況下，搜索的點 數(shù)多，搜索范圍大，效率低，但能得到最優(yōu)解。如果估

2、價值大于實際值，搜索的 點數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。三、實驗內(nèi)容：1、參考實驗系統(tǒng)給出的迷宮求解核心代碼，觀察求解過程與思路。2、畫出用A*算法求解迷宮最短路徑的流程圖。3、嘗試改變啟發(fā)式算法提高迷宮搜索速度。4分析不同啟發(fā)式函數(shù)對迷宮尋路速度的提升效果。四、實驗報告要求:1、畫出A*算法求解迷宮最短路徑問題的流程圖。2、試分析不同啟發(fā)式函數(shù)對迷宮尋路求解的速度提升效果。：gn = 0;fn = abs(Ei-ci)+abs(Ej-cj);fn1 = abs(Ei-ni)+abs(Ej-nj)+gn1;：gn = 0;fn = 0;fn1 = 0;：gn = 0;fn =

3、 0;fn1 = abs(Ei-ni)*abs(Ej-nj) + abs(Ej-nj)*abs(Ej-nj) +gn1;調(diào)節(jié)g(n)和h(n)函數(shù)影響搜索策略。使啟發(fā)式算法效率提高。3、分析啟發(fā)式函數(shù)中g(shù)(n)和h(n)求解方法不同對A*算法的影響。g(n)和h(n)求解方法不同將直接影響A*算法的效率，好的解決方法不僅 能夠使路徑變短，而且在求解過程中所搜索和產(chǎn)生的節(jié)點數(shù)也會盡量的少；而 比較差的解決方法則可能導(dǎo)致所找到的路徑未必是最短的，盡管它在求解過程 中所搜索和產(chǎn)生的節(jié)點數(shù)也比較少。五、實驗心得與體會A*算法作為啟發(fā)式算法的重要組成部分在實際應(yīng)用中有很大的作用。通過這 次實驗，我對g(n)和h(n)這兩個函數(shù)對于A*算法的影響