A*算法筆記

A*算法介紹

A*算法最初發(fā)表于1968年，由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael發(fā)表。它可以被認為是Dijkstra算法的擴展。

A*算法屬于啟發(fā)式搜索(Heuristically Search)。

---

其他搜索算法

1.廣度優(yōu)先搜索

以廣度為優(yōu)先級向外拓展。

2.Dijkstra算法

由迪杰斯特拉在1956年提出，利用貪心策略，每次拓展權值最小的節(jié)點直到終點，如果每個節(jié)點權值相同，將退化成BFS。

3.最佳優(yōu)先搜索(Best First)

預先計算出每個節(jié)點到終點的距離，利用優(yōu)先隊列選取代價最小的節(jié)點，但是又最大的缺點就是搜索結果不一定是最優(yōu)解。

---

A*算法具體實現(xiàn)

A*算法利用下面的函數(shù)計算優(yōu)先級

$$f(n)=g(n)+h(n)$$

其中:

• f(n)為綜合優(yōu)先級

• g(n)為從起點出發(fā)已消耗的代價

• h(n)為節(jié)點距離終點預計代價，即啟發(fā)式函數(shù)

并且使用兩個集合表示待遍歷節(jié)點(open)和已遍歷節(jié)點(close)。

input：圖，點和邊的集合。

output：最優(yōu)路徑

偽代碼

將起點加入open表; while(open表不為空){取出open表中優(yōu)先級最高的節(jié)點n;if(n為終點){從終點回溯構造最優(yōu)路徑;返回最優(yōu)路徑;}else{將n加入close表;for(遍歷鄰居節(jié)點){if(鄰居節(jié)點在close表中||無法拓展) 跳過;if(鄰居節(jié)點在open表中){更新g(n);}else{計算優(yōu)先級;將n設置為父節(jié)點;將此鄰居節(jié)點加入open表中;}}} } 如果open表為空，則起點終點不連通;

啟發(fā)式函數(shù)

利用啟發(fā)式函數(shù)可控制A*算法行為。

• 如果h(n) = 0，算法退化為Dijkstra算法。

• 如果h(n)總小于實際值，則結果一定為最短路徑，不會漏解。越小可擴展節(jié)點越多，算法越慢。

• 如果h(n)等于實際值，擴展路徑即為最短路徑，無法實現(xiàn)。

• 如果h(n)大于實際值，有可能漏解，但是擴展節(jié)點變少，算法速度變快。

通過以上幾種情況可知，我們可以設計h(n)函數(shù)達到我們目的，這就是A*算法靈活所在。

---

關于地圖

算法關注的只有圖(Graph)，對于算法效率而言，圖的節(jié)點數(shù)越少越好，這樣擴展節(jié)點少遍歷次數(shù)也少。

包括柵格地圖，多邊形地圖 …

---

關于距離

基于柵格地圖

Manhattan距離

在不允許對角擴展的情況下，可以使用曼哈頓距離,D為移動代價。

$$h(n)=D?(abs(n.x?goal.x)+abs(n.y?goal.y))$$

對角線距離

在允許對角移動是，可以使用對角線距離，D為上下左右移動代價，D2為對角移動代價，如D2=sqrt(2)*D。

$$h\_diagonal(n)=min(abs(n.x?goal.x),abs(n.y?goal.y))$$

$$h\_straight(n)=(abs(n.x?goal.x)+abs(n.y?goal.y))$$

$$h(n)=D2?h\_diagonal(n)+D?(h\_straight(n)?2?h\_diagonal(n))$$

參考資料：

Introduction to the A* Algorithm

https://zhuanlan.zhihu.com/p/54510444

PathFinding.js

A*—java代碼 - 木子木泗 - 博客園

https://www.gamedev.net/reference/articles/article2003.asp

A*算法中啟發(fā)函數(shù)的使用_free4wuyou的專欄-CSDN博客_啟發(fā)函數(shù)

總結

以上是生活随笔為你收集整理的Astar算法笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。