原因是因為，跟許多演算法比起來，A*會從現有找到的路挑最好的出來(Best-First)，並且猜測接下來最好的路是哪一條(Greedy)
也就是說，A*是一種結合Best-First和Greedy的聰明演算法
評估方法如下: (節錄自: http://blog.minstrel.idv.tw/2004/12/star-algorithm.html)
f(n) = g(n) + h(n)
g(n): 從啟始點到目前節點的距離
h(n): 預測目前節點到結束點的距離(此為 A* 演算法的主要評價公式)
f(n): 目前結點的評價分數
其中, h(n) 主導著A* 演算法的表現方式. 有以下幾種情形:
1. h(n)=0: A* 演算法這時等同 Dijkstra演算法, 並且保證能找到最短路徑
2. h(n)<目前節點到結束點的距離: A* 演算法保證找到最短路徑, h(n)越小, 搜尋深度越深
3. h(n)=目前節點到結束點的距離: A* 演算法僅會尋找最佳路徑, 並且能快速找到結果
4. h(n)>目前節點到結束點的距離: 不保證能找到最短路徑, 但計算比較快
5. h(n)與g(n)高度相關: A* 演算法此時成為 BFS (Best-First Search)
A*的優點從以下圖可明顯看出 :
A*的搜尋範圍明顯的比Dijkstra小
但是也有一點缺點:
A*有可能沒辦法找到最好的路徑
沒有留言:
張貼留言