之前有介紹A* 演算法的代碼注釋和提供了MATLAB版的原始碼下載，這次主要是講解A* 演算法的基本組成和運行機制，相信能為剛開始學習路徑規劃的同學們提供到一點幫助，
宣告：這篇博客是基于我個人對A*演算法的理解基礎上寫出來的，與原作者或者現在的主流思想有沒有出入現在尚未知曉，如果文中有哪些地方書寫或者描述有錯誤，可以在評論區打出來，大家一起交流學習，共同進步，感謝！
原創作品，轉載請注明出處，
概述
1968年，一篇名為《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》的文章出版，里面提出了A* 演算法，并且使得A* 演算法在接下來的幾十年中飛速發展，并且廣泛應用在導航、迷宮求解、游戲尋路、機器人路徑規劃等應用中，
A* 演算法原理
A* 演算法是一種高效的啟發式搜索演算法，在二維的柵格地圖上尋路效果好，它通過估算節點的代價評估函式值并作為節點的綜合優先級，當選擇下一個需要遍歷的節點時，再選取綜合優先級最高的節點，逐步地找到最優路徑，A* 演算法可以快速的找到代價值最小，路程最短的路徑，但是隨著柵格精度的提高和地圖尺寸的擴大，對無用節點的重復搜索評估會導致 A* 演算法搜索時間呈指數級增長，
簡單的說就是在一個柵格地圖中，通過不斷計算當前點與目標點的代價值來選擇下一步應該怎么走，這個代價值主要是有兩部分組成，
A* 演算法的組成
代價計算公式：F(n)=G(n)+H(n)
其中， F(n) 是從初始狀態經由狀態n到目標狀態的代價估計，
G(n) 是在狀態空間中從初始狀態到狀態n的實際代價，
H(n) 是從狀態n到目標狀態的最佳路徑的估計代價，
此處用柵格地圖中的路徑規劃問題作為例子講解，
講解可以參照視頻，
以移動機器人的移動為例，假設柵格的大小為10*10(不考慮單位問題)，假設移動機器人當前所在的位置坐標為[4,2]，要前往目標點[1,5]處，
第一步，對當前位置周圍的八個相鄰柵格進行代價值計算，計算公式為F(n)=G(n)+H(n)；
上下左右移動是一個柵格的距離，為10，對角線移動的話就是根號200了，此處取近似值14，
G(n)的值為起始點到某一個柵格的最短行進距離，具體可以在下面圖解中詳細體會，
H(n)的計算方法一般有三種；
1：曼哈頓距離；
2：歐幾里得距離；
3：切比雪夫距離；
此處采用的是曼哈頓距離進行展示，其計算公式為：
H(n)=(abs(x1 - x2) + abs(y1 - y2))* 10(柵格寬度)
懂得了計算公式之后就可以計算出當前柵格周圍八個鄰域的柵格的代價值分別是多少了，
隨后就在這八個柵格中選擇代價值F(n)最小的一個柵格作為下一步前進的目標柵格，此處顯然是[3,3]，移動機器人移動到[3,3]處后同理再對周圍八個相鄰柵格進行代價值計算，選取代價值最低的柵格作為下一個前進的柵格，依次往復，直到到達目標位置為止，
注意此時的G(n)值變化的規律，這是A*演算法的關鍵之一！
找到目標點！注意此時圖中有3個柵格的總代價值為48，但是只對一個柵格進行了八鄰域計算，原因是圈起來的兩個柵格是后面才搜索計算到的，與此同時出現了代價值為42的柵格，因此也就舍棄了這兩個代價值為48的柵格，請讀者必須理解好這一點，這對后續的編程幫助非常大，
這就是A*演算法的尋路原理，值得注意的是，當尋路方向上有障礙物時，會出現同時有多個最小代價值柵格出現的情況，此時應當注意這些柵格都應該被作為當前柵格然后去計算相應鄰域柵格的代價值大小，
如下圖：
第一步：
第二步：
第三步：
柵格[2,3]的八鄰域內除去障礙物部分，發現[2,2]柵格的代價值最小，與此同時[4,3]柵格處的代價值也為50，因此下一次搜索柵格時應當把這兩個位置的柵格都考慮進去，
跟上一張圖片一樣，出現了多個代價值為64的柵格，每個都應該搜索其相應的八個鄰域，但是由于我的柵格地圖畫小了，所以就不展示出來了，大家明白意思就好了，
這樣就搜索到了目標點，
然后就可以在在搜索過的所有柵格內找出一條最短路徑了！這條路徑是區域最優的，但是不一定是全域最優，
由于篇幅原因，A*演算法的編程思路就留到下一篇博客進行介紹了，歡迎大家關注我！
創作不易，如果這篇文章有幫助到您的地方，歡迎點贊、關注、一鍵三連，感謝支持！
相關文章：
A* 演算法的MATLAB原始碼下載，
A* 演算法的MATLAB原始碼講解，
原創作品，轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/233571.html
標籤：其他