Aster（A*）算法

Aster算法是在Dijkstra算法基礎上發展出來的，是在靜態路徑中用于求解最優路徑有效的直接搜索算法，比dijkstra算法多了一個啟發式的搜索函數，也就是通過一個代價函數來確定搜索方向（從起點開始向周圍擴張，通過代價函數，計算得到周圍每個節點的代價值，選出最小代價節點作為下一個擴展點，重復這個過程直到到達目標點。）。

算法對比：

$A^{?}$算法的代價函數$f(n)$表示為：
$$f(n)=g(n)+h(n)$$
$g(n)$：表示起始點到節點n的實際代價。
$h(n)$（比dijkstra多的）：表示節點n到目標點的估計代價。

---

例子：要求機器人從起始點繞過障礙物到達目標點，這里我們使用$A^{?}$算法尋找出最優的路徑。
第一步：將地圖簡化成易于表示的區域。
我們使用正方形作為尋路算法的單元（也可用其他形狀），將如圖所示區域分為5X7的柵格。

第二步：建立open和closed列表
open列表：記錄下所有被考慮來尋找最短路徑的方格；把起始點定義為“父節點”，靠近父節點的點稱為子節點，將所有可通過的點放入open列表中作為待查點（圖中的8 9 10 15 17 22 23 24八個方格。）
closed列表：記錄下不會再被考慮的方格。如圖首先將起始點添加到closed列表中。

$A^{?}$算法中的代價函數$f(n)=g(n)+h(n)$中：

• g值：g值表示從當前方格到達起始點代價值。我們規定機器人水平（或垂直）移動一個格代價值為10，對角線方向移動代價值為14.方格左下角為g值。
  
• h值：h值表示從當前方格到目標點（圖中可樂所在位置）的代價。這里我們用曼哈頓距離表示。下圖表示了不同點h值得度量。（h值我們放在格子得右下角）

算g時要考慮障礙物的存在，h則不用。

h：指的是17這個格子到終點的h值

。。。。。。
。。。。。。
。。。。。。

---

總結

以上是生活随笔為你收集整理的（三）【机器人路径规划】Astar算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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