A*算法研究
許多工業(yè)與科學(xué)計(jì)算問題都可以轉(zhuǎn)化為在圖中尋路問題。啟發(fā)式的尋路方法將問題表示為一個(gè)圖，然后利用問題本身的信息，來加速解的搜索過程。一個(gè)典型的例子是有一些通路連接若干城市，找出從指定起點(diǎn)城市到指定終點(diǎn)城市的路徑。但是有些問題不存在如此明顯的事先定義好的圖，它們的圖是隱式圖，也就是說，問題給定了搜索起點(diǎn)與一系列操作，對起點(diǎn)進(jìn)行這些操作得到了它的后繼結(jié)點(diǎn)，以及該操作的代價(jià)，對這些后繼結(jié)點(diǎn)不斷地重復(fù)操作，就得到了一個(gè)帶權(quán)的有向圖，隱式圖就定義好了。
對于解決最小路徑問題，A*算法性能卓越。首先，對于任何有解路徑，A*總能找到一條最佳路徑，也就是說A*算法是可采納的。其次，在保證能找到最佳路徑的前提下，A*算法擴(kuò)展了最少個(gè)數(shù)的結(jié)點(diǎn)，也就是說A*算法是最優(yōu)的。
使用啟發(fā)信息的一種重要方法就是估價(jià)函數(shù)。A*使用來表示結(jié)點(diǎn)的估價(jià)函數(shù)，它表示從起點(diǎn)到目標(biāo)，經(jīng)由結(jié)點(diǎn)最小費(fèi)用路徑上的費(fèi)用。它由和兩部分組成，即。其中表示從初始結(jié)點(diǎn)到的最佳解路徑的費(fèi)用，表示從到目標(biāo)結(jié)點(diǎn)的最佳解路徑的費(fèi)用。但想要知道它們的精確值很難，我們可以使用來估計(jì)，使用來估計(jì)，來估計(jì)。表示目前為止，從起始點(diǎn)到的最小費(fèi)用，因?yàn)槿蘸罂赡苷业礁〉馁M(fèi)用，所以有。而在A*算法中，對的估計(jì)通常是樂觀的，比實(shí)際所需的費(fèi)用要小，即有。它們之間的關(guān)系可以用下圖形象地表示：
注：黃色是估計(jì)值，黑色是最佳解路徑費(fèi)用
A*算法維護(hù)兩個(gè)集合：OPEN 集和 CLOSED 集。OPEN 集包含待檢測節(jié)點(diǎn)。初始狀態(tài)的OPEN集僅包含一個(gè)元素：開始位置。CLOSED集包含已檢測節(jié)點(diǎn)。初始狀態(tài)的CLOSED集為空。從圖形上來看，OPEN集是已訪問區(qū)域的邊界，CLOSED集是已訪問區(qū)域的內(nèi)部。每個(gè)節(jié)點(diǎn)還包含一個(gè)指向父節(jié)點(diǎn)的指針，以確定追蹤關(guān)系。
算法有一個(gè)主循環(huán)，重復(fù)地從OPEN集中取最優(yōu)節(jié)點(diǎn)n（即f值最小的節(jié)點(diǎn)）來檢測。如果n是目標(biāo)節(jié)點(diǎn)，那么算法結(jié)束；否則，將節(jié)點(diǎn)n從OPEN集刪除，并添加到CLOSED集中，然后查看n的所有鄰節(jié)點(diǎn)n'。cost= g(n) + movementcost(n, n')。n'有如下三種情況：
- 鄰結(jié)點(diǎn)在CLOSED集中，說明它已被檢測過，如果cost<g(n')，那么說明找到了一條通過n到達(dá)n'更近的路徑，更新g(n')為cost, n'的父結(jié)點(diǎn)為n，把鄰結(jié)點(diǎn)從CLOSED集中刪去，并把它重新放入OPEN集中（因?yàn)橥瑯佣际堑竭_(dá)n'，h(n')是一樣的，g(n')小必然能帶來更小的f(n')），如果cost>=g(n')，則跳過該鄰結(jié)點(diǎn)。
- 鄰結(jié)點(diǎn)在OPEN集中，說明它之前被拓展過，如果cost<g(n')，那么說明找到了一條通過n到達(dá)n'更近的路徑，更新g(n')為cost, n'的父結(jié)點(diǎn)為n，鄰結(jié)點(diǎn)仍留在OPEN集中。如果cost>=g(n')，則跳過該鄰結(jié)點(diǎn)。
- 鄰結(jié)點(diǎn)不在CLOSED集或者OPEN集中，則加入OPEN集中。
算法用偽代碼表示如下：
OPEN = priority queue containing START
?
CLOSED = empty set
?
while lowest rank in OPEN is not the GOAL:
?
current = remove lowest rank item from OPEN
?
add current to CLOSED
?
for neighbors of current:
?
cost = g(current) + movementcost(current, neighbor)
?
if neighbor in OPEN and cost less than g(neighbor):
?
remove neighbor from OPEN, because new path is better
?
if neighbor in CLOSED and cost less than g(neighbor): **
?
remove neighbor from CLOSED
?
if neighbor not in OPEN and neighbor not in CLOSED:
?
set g(neighbor) to cost
?
add neighbor to OPEN
?
set priority queue rank to g(neighbor) + h(neighbor)
?
set neighbor's parent to current
?
reconstruct reverse path from goal to start
?
by following parent pointers
在A*算法中，h(n)越大啟發(fā)信息越多，但是有時(shí)計(jì)算啟發(fā)信息本身的代價(jià)很高，例如計(jì)算的開銷較大，可以使用來代替，（總是成立）雖然會擴(kuò)展多一些的結(jié)點(diǎn)，但是依舊是高效的。h(n)=0時(shí)，A*退化成了DIjkstra算法。
當(dāng)時(shí)，算法不再可采納，不一定能找到最優(yōu)解，但是能以較快的速度找到滿意解，這在大多數(shù)時(shí)候是高效的。例如使用來代替。當(dāng)h(n)很大時(shí)，A*變成了貪心算法。
所以要仔細(xì)選擇h(n)，在算法是否可采納、搜索效率、計(jì)算開銷之間權(quán)衡。
總結(jié)
- 上一篇： Centos6.5添加163软件yum源
- 下一篇： PM_LOG