A*算法是一種很常用的路徑查找和圖形遍歷算法。它有較好的性能和準確度

1 中心思路

• A*算法通過下面這個函數(shù)來計算每個節(jié)點n的優(yōu)先級
  • f(n)=g(n)+h(n)
    • f(n)是節(jié)點n的綜合優(yōu)先級。當選擇下一個要遍歷的節(jié)點時，總會選取綜合優(yōu)先級最高（f(n)值最小）的節(jié)點。
    • g(n) 是節(jié)點n距離起點的代價
    • h(n)是節(jié)點n距離終點的預計代價，這也就是A*算法的啟發(fā)函數(shù)
• A*算法在運算過程中，每次從優(yōu)先隊列中選取f(n)值最小（優(yōu)先級最高）的節(jié)點作為下一個待遍歷的節(jié)點。

1.1? 偽代碼

• A*算法使用兩個集合來表示待遍歷的節(jié)點（open_set），與已經(jīng)遍歷過的節(jié)點（close_set）

• 初始化open_set和close_set
• 將起點n0加入open_set中，并設置f(n0)=0（優(yōu)先級最高）
• 如果open_set不為空，則從open_set中選取優(yōu)先級最高的節(jié)點n：
  • 如果節(jié)點n為終點：
    • 從終點開始逐步追蹤parent節(jié)點，一直達到起點
    • 返回找到的結果路徑，算法結束
  • 如果節(jié)點n不是終點：
    • 將節(jié)點n從open_set中刪除，并加入close_set中
    • 遍歷節(jié)點n所有的鄰近節(jié)點
      • 如果鄰近節(jié)點m在close_set中（已經(jīng)訪問過來），則：
        • 跳過，選取下一個鄰近節(jié)點
      • 如果鄰近節(jié)點m也不在open_set中，則=
        • 設置節(jié)點m的parent為節(jié)點n
        • 計算節(jié)點m的優(yōu)先級f(n)
        • 將節(jié)點m加入open_set中

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

• 在極端情況下，當啟發(fā)函數(shù)h(n)始終為0，則將由g(n)決定節(jié)點的優(yōu)先級，此時算法就退化成了Dijkstra算法
  • ntu 課程筆記 ：MAS714(7) 最短路徑和優(yōu)先隊列_UQI-LIUWJ的博客-CSDN博客
• 如果h(n)始終小于等于節(jié)點n到終點的代價，則A*算法保證一定能夠找到最短路徑。
  • 但是當h(n)的值越小，算法將遍歷越多的節(jié)點，也就導致算法越慢。
• 如果h(n)完全等于節(jié)點n到終點的代價，則A*算法將找到最佳路徑，并且速度很快。
  • 可惜的是，并非所有場景下都能做到這一點。因為在沒有達到終點之前，我們很難確切算出距離終點還有多遠。
• 如果h(n)的值比節(jié)點n到終點的代價要大，則A*算法不能保證找到最短路徑，不過此時會很快
  • 
  • 比如這種情況最短路路徑應該是下路
  • 但如果我們估計的h(n)為實際路徑的兩倍
    • 那么選擇中間節(jié)點的時候，A*算法會選擇上路 （5+3*2=11，4+3.6*2=11.2）

  ?

2.1 一些經(jīng)驗啟發(fā)函數(shù)

• 如果圖形中只允許朝上下左右四個方向移動，則可以使用曼哈頓距離
  • 
• 如果圖形中允許朝八個方向移動，則可以使用對角距離
  • 
• 如果圖形中允許朝任何方向移動，則可以使用歐幾里得距離
  • 

  ?