A*算法總結(jié)
A*是一種啟發(fā)式搜索，一種有序搜索，它之所以特殊完全是在它的估價(jià)函數(shù)上，如果我要求的是從初始結(jié)點(diǎn)到目的結(jié)點(diǎn)的一個(gè)最短路徑（或加權(quán)代價(jià)）的可行解，
那對(duì)于一個(gè)還不是目標(biāo)結(jié)點(diǎn)的結(jié)點(diǎn)，我對(duì)它的評(píng)價(jià)就要從兩個(gè)方面評(píng)價(jià)：第一，離目標(biāo)結(jié)點(diǎn)有多近，越近越好；第二，離起始結(jié)點(diǎn)有多遠(yuǎn)，越近越好。記號(hào)
[a,b]是表示結(jié)點(diǎn)a到結(jié)點(diǎn)b的實(shí)際最短路徑代價(jià)。設(shè)起始結(jié)點(diǎn)為S，當(dāng)前結(jié)點(diǎn)為n，目標(biāo)結(jié)點(diǎn)為G，于是n的實(shí)際代價(jià)應(yīng)該是f*(n)=g*(n)+h*
(n)，其中g(shù)*(n)=[S,n],h*(n)=[n,G]，對(duì)于是g*(n)是比較容易得到的，在搜索的過(guò)程中我們可以按搜索的順序?qū)λM(jìn)行累積計(jì)
算，當(dāng)然按BFS和DFS的不同，我們對(duì)它的估價(jià)g(n)可以滿(mǎn)足g(n)>=g*(n)，大多可以是相等的。但是對(duì)于h*(n)我們卻了解得非常
少，目標(biāo)結(jié)點(diǎn)正是要搜索的目的，我們是不知道在哪，就更不知道從n到目標(biāo)結(jié)點(diǎn)的路徑代價(jià)，但是或多或少我們還是可以估計(jì)的，記估價(jià)函數(shù)f(n)=g(n)
+h(n)。
我們說(shuō)如果在一般的圖搜索算法中應(yīng)用了上面的估價(jià)函數(shù)對(duì)OPEN表進(jìn)行排序的，就稱(chēng)A算法。在A算法之上，如果加上一個(gè)條件，對(duì)于所有的結(jié)點(diǎn)x，都有h(x)<=h*(x)，那就稱(chēng)為A*算法。如果取h(n)=0同樣是A*算法，這樣它就退化成了有序算法。
A*算法是否成功，也就是說(shuō)是否在效率上勝過(guò)蠻力搜索算法，就在于h(n)的選取，它不能大于實(shí)際的h*(n)，要保守一點(diǎn)，但越接近h*(n)給我們的啟發(fā)性就越大，是一個(gè)難把握的東西。
過(guò)程:
1. 將開(kāi)始節(jié)點(diǎn)放入開(kāi)放列表(開(kāi)始節(jié)點(diǎn)的F和G值都視為0);
2. 重復(fù)一下步驟:
i. 在開(kāi)放列表中查找具有最小F值的節(jié)點(diǎn),并把查找到的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn);
ii. 把當(dāng)前節(jié)點(diǎn)從開(kāi)放列表刪除, 加入到封閉列表;
iii. 對(duì)當(dāng)前節(jié)點(diǎn)相鄰的每一個(gè)節(jié)點(diǎn)依次執(zhí)行以下步驟:
1. 如果該相鄰節(jié)點(diǎn)不可通行或者該相鄰節(jié)點(diǎn)已經(jīng)在封閉列表中,則什么操作也不執(zhí)行,繼續(xù)檢驗(yàn)下一個(gè)節(jié)點(diǎn);
2. 如果該相鄰節(jié)點(diǎn)不在開(kāi)放列表中,則將該節(jié)點(diǎn)添加到開(kāi)放列表中, 并將該相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn),同時(shí)保存該相鄰節(jié)點(diǎn)的G和F值;
3. 如果該相鄰節(jié)點(diǎn)在開(kāi)放列表中, 則判斷若經(jīng)由當(dāng)前節(jié)點(diǎn)到達(dá)該相鄰節(jié)點(diǎn)的G值是否小于原來(lái)保存的G值,若小于,則將該相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn),并重新設(shè)置該相鄰節(jié)點(diǎn)的G和F值.
iv. 循環(huán)結(jié)束條件:
當(dāng)終點(diǎn)節(jié)點(diǎn)被加入到開(kāi)放列表作為待檢驗(yàn)節(jié)點(diǎn)時(shí), 表示路徑被找到,此時(shí)應(yīng)終止循環(huán);
或者當(dāng)開(kāi)放列表為空,表明已無(wú)可以添加的新節(jié)點(diǎn),而已檢驗(yàn)的節(jié)點(diǎn)中沒(méi)有終點(diǎn)節(jié)點(diǎn)則意味著路徑無(wú)法被找到,此時(shí)也結(jié)束循環(huán);
3. 從終點(diǎn)節(jié)點(diǎn)開(kāi)始沿父節(jié)點(diǎn)遍歷, 并保存整個(gè)遍歷到的節(jié)點(diǎn)坐標(biāo),遍歷所得的節(jié)點(diǎn)就是最后得到的路徑;
搜索過(guò)程中設(shè)置兩個(gè)表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)。算法中有一步是根據(jù)估價(jià)函數(shù)重排OPEN表。這樣循環(huán)中的每一步只考慮OPEN表中狀態(tài)最好的節(jié)點(diǎn)。
Best_First_Search()
{
Open = [起始節(jié)點(diǎn)];
Closed = [];
while ( Open表非空 )
{
從Open中取得一個(gè)節(jié)點(diǎn)X, 并從OPEN表中刪除.
if (X是目標(biāo)節(jié)點(diǎn))
{
求得路徑PATH;
返回路徑PATH;
}
for (每一個(gè)X的子節(jié)點(diǎn)Y)
{
if( Y不在OPEN表和CLOSE表中 )
{
求Y的估價(jià)值;
并將Y插入OPEN表中; //還沒(méi)有排序
}
else if( Y在OPEN表中 )
{
if( Y的估價(jià)值小于OPEN表的估價(jià)值 )
更新OPEN表中的估價(jià)值;
}
else //Y在CLOSE表中
{
if( Y的估價(jià)值小于CLOSE表的估價(jià)值 )
{
更新CLOSE表中的估價(jià)值;
從CLOSE表中移出節(jié)點(diǎn), 并放入OPEN表中;
}
}
將X節(jié)點(diǎn)插入CLOSE表中;
按照估價(jià)值將OPEN表中的節(jié)點(diǎn)排序;
} //end for
} //end while
} //end func