(一) 任務描述： 在隨機的二維柵格地圖中，地圖中存在隨機給定的靜態障礙物，給定路徑起點和路徑終點，利用 Astar 算法生成最優路徑。
（二）算法分析與具體實現Astar 算法是建立 Dijkstra 算法的思想上的，它們在進行圖的拓展的時候，每次都選擇了具備某種最優性的節點進行拓展，最終，當圖結構拓展到目標節點時，對應的路徑往往能夠滿足最優性的要求。而 Astar 算法與Dijkstra 算法的不同之處在于 Astar 算法在累計代價函數 g(n) 的基礎上，進一步引入了啟發函數 h(n)，節點排序以 g(n)+h(n) 為參照，當選取了合適的 h(n) 時，節點圖往往能夠迅速地向目標節點方向拓展，同時保證結果的最優秀，其偽代碼如 Algorithm 1 所示：
（三）仿真實驗及結果分析
在仿真實驗過程中，主要考慮了兩方面的影響因素：啟發函數 h(n) 與節點拓展形式 expand(n)。啟發函數選擇了三種距離函數：對角距離、曼哈頓距離以及歐氏距離；節點拓展形式考慮了四叉樹和八叉樹兩種。而在代價函數方面，使用的是對角距離函數，由于無論是四叉樹還是八叉樹，拓展節點與當前節點均為相鄰節點，在此情形下，對角距離與歐氏距離是相等的。在二維平面下三種距離函數的定義如下：
為了使得實驗結果根據可信性，令隨機地圖生成過程中的障礙物生成閾值為 0.1（ 0.25 時容易出現無解的情況），而后令隨機數種子從 1 取到 1000，生成約 1000 張地圖（不排除多個隨機數種子對應一張地圖的情形），
在八叉樹拓展形式下進行算法測試，最終主要出現了三類對比結果：
（ 1）存在可行路徑，而且三類方法尋得的最優路徑是相同的，實際上，這也是絕大多數地圖測試的結果，這說明，在絕大多數情況下，三種算法的最優路徑和實際的最短路徑是相同的，結果如圖 1(a) 所示。
（ 2）不存在可行路徑。這是比較少見的，實際上，這是在障礙物生成閾值為 0.25，隨機數種子為 9 時生成的地圖。如圖 1(b)，此情形下主要原因在于存在一個由障礙物和場地邊界線構成的封閉曲線，使得起始點和目標點分別在封閉曲線的內外部，不存在從起始點到目標點穿越該封閉曲線而無碰撞的可行路徑。
（ 3）存在可行路徑，但是曼哈頓距離所尋得的最優路徑與其他兩種距離所尋得的最優路徑不同。實際上，這是由于八叉樹拓展形勢下，對角距離是從當前點到目標點的真實距離，而 manh_dis ≥ diag_dis ≥ eucl_dis，因此，引用曼哈頓距離函數作為啟發函數時不一定能夠找到真正的最段路徑，如圖 1? 和圖 1(d) 所示。
圖 1: (a) 隨機種子為 1，障礙物生成閾值為 0.1，三種距離函數均尋到最優路徑； (b) 隨機種子為 9，障礙物生成閾值為 0.25，不存在可行路徑 ? 隨機種子為 266，障礙物生成閾值為 0.1，距離函數為對角距離和歐氏距離，兩種距離函數均尋到最優路徑，路徑長度為 11.8995； (d) 隨機種子為 266，障礙物生成閾值為 0.1，距離函數為曼哈頓距離，未能尋到最優路徑，路徑總長度為 12.4853.
為了驗證啟發函數對最優路徑尋取結果的影響，將節點拓展形式改為四叉樹拓展形式，此時，各個節點到目標節點的最優距離為曼哈頓距離，從 1000 張地圖的尋得路徑長度的統計結果來看，在存在可行路徑的情況下，三種算法尋得的最優路徑是相同的。 從表 1 中可以看出，在八叉樹拓展形式下，曼哈頓距離尋得的路徑確實不是最優的，而在四叉樹拓展形勢下，三種啟發函數尋得的路徑長度是相同的。
此外，算法運行時間同樣至關重要，因此，在 10000 張地圖下，對算法運行時間進行統計，此時障礙物生成閾值為 0.1，八叉樹拓展形式下僅隨機數種子為 276 時不存在可行路徑，四叉樹拓展形式下，有 8 張地圖不存在可行路徑，最終得到運行時間統計數據如下：

從表 2 中可以看出，曼哈頓距離函數對應的平均時間和運行時間標準差優于其他兩種距離函數，而歐氏距離函數對應的平均時間與對角距離函數對應的平均運行時間大致相同和標準差大致相同。算法運行時間與距離函數的選取存在一定的關聯性，可能是由于距離函數導致節點拓展形式存在差異，但是也并不能排除由于本身距離函數計算復雜度不同而導致這一現象發生的可能性。
csdn鏈接:https://download.csdn.net/download/qq_31813825/11940280

總結

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

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