A 演算法簡介 (A Algorithm Brief)

A 演算法簡介 (A Algorithm Brief) A* 演算法簡介 (A* Algorithm Brief) 2004/12/20 09:44 A* (A-Star) 演算法是在Game中通常用來解決最短路徑(Shortest Path)問題的一種演算法. 相對於另一個知名的 Dijkstra 演算法來說, Dijkstra演算法雖然可以保證找到一條最短的路徑, 但不如A* 演算法這樣簡捷快速. 同時, Dijkstra的搜尋深度在某些情形下也容易顯得不適用. A* 演算法便是為了這些情形而出現的, 可以算是 Dijkstra演算法的一種改良. 底下用幾張...

A* 演算法簡介 (A* Algorithm Brief) 2004/12/20 09:44 A* (A-Star) 演算法是在Game中通常用來解決最短路徑(Shortest Path)問題的一種演算法. 相對於另一個知名的 Dijkstra 演算法來說, Dijkstra演算法雖然可以保證找到一條最短的路徑, 但不如A* 演算法這樣簡捷快速. 同時, Dijkstra的搜尋深度在某些情形下也容易顯得不適用. A* 演算法便是為了這些情形而出現的, 可以算是 Dijkstra演算法的一種改良. 底下用幾張圖來表現Dijkstra演算法與A* 演算法的不同: Dijkstra 演算法 A* 演算法無障礙有障礙 (圖片取自 Amit's Thoughts on Path-Finding and A-Star) 從以上的比較圖可以看出, A* 演算法的搜尋深度雖然不如 Dijkstra演算法, 但其結果仍然是很令人滿意的. 為什麼A* 演算法可以達到這樣的結果呢? 這是因為A* 演算法採用了一套特殊的啟發式評價(Heuristic Estimate)公式將許多明顯為壞的路徑排除考慮, 進而快速計算出一條滿意的路徑. 公式如下: 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* 演算法的虛擬碼如下: Add START to OPEN list while OPEN not empty get node n from OPEN that has the lowest f(n) if n is GOAL then return path move n to CLOSED for each n' = CanMove(n, direction) g(n') = g(n) + 1 calculate h(n') if n' in OPEN list and new n' is not better, continue if n' in CLOSED list and new n' is not better, continue remove any n' from OPEN and CLOSED add n as n's parent add n' to OPEN end for end while if we get to here, then there is No Solution 以上虛擬碼適用於一般遊戲中方格圖(Grid Map)的情形. 當要在真實地圖的路網(Road Map)上使用A* 演算法時, g(n)與h(n)的計算方式便會有所不同. 相關參考資料: 網頁: Amit's Thoughts on Path-Finding and A-Star Creating an A* algorithm Robot for QUT SoKoBan 維基百科: Shortest Path Problem A* Search Algorithm Dijkstra Algorithm 書籍: Core Techniques and Algorithms in Game Programming (英文) 大師談遊戲程式設計：核心技術與演算法 (中文)

                    本文档为【A 演算法簡介 (A Algorithm Brief)】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

A 演算法簡介 (A Algorithm Brief)

你可能还喜欢