A*算法研究
許多工業與科學計算問題都可以轉化為在圖中尋路問題。啟發式的尋路方法將問題表示為一個圖，然后利用問題本身的信息，來加速解的搜索過程。一個典型的例子是有一些通路連接若干城市，找出從指定起點城市到指定終點城市的路徑。但是有些問題不存在如此明顯的事先定義好的圖，它們的圖是隱式圖，也就是說，問題給定了搜索起點與一系列操作，對起點進行這些操作得到了它的后繼結點，以及該操作的代價，對這些后繼結點不斷地重復操作，就得到了一個帶權的有向圖，隱式圖就定義好了。
對于解決最小路徑問題，A*算法性能卓越。首先，對于任何有解路徑，A*總能找到一條最佳路徑，也就是說A*算法是可采納的。其次，在保證能找到最佳路徑的前提下，A*算法擴展了最少個數的結點，也就是說A*算法是最優的。
使用啟發信息的一種重要方法就是估價函數。A*使用來表示結點的估價函數，它表示從起點到目標，經由結點最小費用路徑上的費用。它由和兩部分組成，即。其中表示從初始結點到的最佳解路徑的費用，表示從到目標結點的最佳解路徑的費用。但想要知道它們的精確值很難，我們可以使用來估計，使用來估計，來估計。表示目前為止，從起始點到的最小費用，因為日后可能找到更小的費用，所以有。而在A*算法中，對的估計通常是樂觀的，比實際所需的費用要小，即有。它們之間的關系可以用下圖形象地表示：
注：黃色是估計值，黑色是最佳解路徑費用
A*算法維護兩個集合：OPEN 集和 CLOSED 集。OPEN 集包含待檢測節點。初始狀態的OPEN集僅包含一個元素：開始位置。CLOSED集包含已檢測節點。初始狀態的CLOSED集為空。從圖形上來看，OPEN集是已訪問區域的邊界，CLOSED集是已訪問區域的內部。每個節點還包含一個指向父節點的指針，以確定追蹤關系。
算法有一個主循環，重復地從OPEN集中取最優節點n（即f值最小的節點）來檢測。如果n是目標節點，那么算法結束；否則，將節點n從OPEN集刪除，并添加到CLOSED集中，然后查看n的所有鄰節點n'。cost= g(n) + movementcost(n, n')。n'有如下三種情況：
- 鄰結點在CLOSED集中，說明它已被檢測過，如果cost<g(n')，那么說明找到了一條通過n到達n'更近的路徑，更新g(n')為cost, n'的父結點為n，把鄰結點從CLOSED集中刪去，并把它重新放入OPEN集中（因為同樣都是到達n'，h(n')是一樣的，g(n')小必然能帶來更小的f(n')），如果cost>=g(n')，則跳過該鄰結點。
- 鄰結點在OPEN集中，說明它之前被拓展過，如果cost<g(n')，那么說明找到了一條通過n到達n'更近的路徑，更新g(n')為cost, n'的父結點為n，鄰結點仍留在OPEN集中。如果cost>=g(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)越大啟發信息越多，但是有時計算啟發信息本身的代價很高，例如計算的開銷較大，可以使用來代替，（總是成立）雖然會擴展多一些的結點，但是依舊是高效的。h(n)=0時，A*退化成了DIjkstra算法。
當時，算法不再可采納，不一定能找到最優解，但是能以較快的速度找到滿意解，這在大多數時候是高效的。例如使用來代替。當h(n)很大時，A*變成了貪心算法。
所以要仔細選擇h(n)，在算法是否可采納、搜索效率、計算開銷之間權衡。
總結
- 上一篇： Centos6.5添加163软件yum源
- 下一篇： PM_LOG