星算法實(shí)驗(yàn)報(bào)告

1、A*算法實(shí)驗(yàn)報(bào)告一、 實(shí)驗(yàn)原理A*算法，作為啟發(fā)式算法中很重要的一種，被廣泛應(yīng)用在最優(yōu)路徑求解和一些策略設(shè)計(jì)的問題中。而A*算法最為核心的部分，就在于它的一個估值函數(shù)的設(shè)計(jì)上： f(n)=g(n)+h(n) 其中f(n)是每個可能試探點(diǎn)的估值，它有兩部分組成：一部分為g(n)，它表示從起始搜索點(diǎn)到當(dāng)前點(diǎn)的代價(jià)（通常用某結(jié)點(diǎn)在搜索樹中的深度來表示）。另一部分，即h(n)，它表示啟發(fā)式搜索中最為重要的一部分，即當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估值，h(n)設(shè)計(jì)的好壞，直接影響著具有此種啟發(fā)式函數(shù)的啟發(fā)式算法的是否能稱為A*算法。一種具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是：

2、1) 搜索樹上存在著從起始點(diǎn)到終了點(diǎn)的最優(yōu)路徑。 2) 問題域是有限的。 3）所有結(jié)點(diǎn)的子結(jié)點(diǎn)的搜索代價(jià)值0。 4）h(n)=h*(n) （h*(n)為實(shí)際問題的代價(jià)值）。 當(dāng)此四個條件都滿足時，一個具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法，并一定能找到最優(yōu)解。對于一個搜索問題，顯然，條件1,2,3都是很容易滿足的，而 條件4)： h(n)g+1; if(lei=2) /如果是斜線走g_value=father-g+1.414;修改后的擴(kuò)展結(jié)點(diǎn)數(shù)837三、 實(shí)驗(yàn)分析A*算法最為核心的過程，就在每次選擇下一個當(dāng)前搜索點(diǎn)時，是從所有已探知的但未搜索過點(diǎn)中(可能是不同層，亦可不

3、在同一條支路上)，選取f值最小的結(jié)點(diǎn)進(jìn)行展開。而所有“已探知的但未搜索過點(diǎn)”可以通過一個按f值升序的隊(duì)列(即優(yōu)先隊(duì)列)進(jìn)行排列。這樣，在整體的搜索過程中，只要按照類似廣度優(yōu)先的算法框架，從優(yōu)先隊(duì)列中彈出隊(duì)首元素（f值），對其可能子結(jié)點(diǎn)計(jì)算g、h和f值，直到優(yōu)先隊(duì)列為空(無解)或找到終止點(diǎn)為止。若修改地圖該算法得到的路徑是：算法依然有效其實(shí)該算法的啟發(fā)函數(shù)是兩點(diǎn)之間的歐式距離，即當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的直線距離，對于此題目來說歐式距離啟發(fā)信息相對太少，若將啟發(fā)函數(shù)改為：chang=end_x-x;kuan=end_y-y;if(chang=kuan)distance=(int)1.414*kuan+chang-kuan;elsedistance=(int)1.414*chang+kuan-chang;即每次保證走的是四十五度，但與上圖比較路徑多了，代價(jià)多了，說明h函數(shù)并不合理，不滿足可采