a星演算法視頻

Ⅰ A星演算法詳解(個人認為最詳細,最通俗易懂的一個版本)

在探索領域中，尋找最短路徑的問題經常需要使用到A*演算法。A*演算法是一種廣泛應用於路徑規劃和游戲開發中的啟發式搜索演算法。本文將通過詳細的步驟，深入解讀A*演算法的運作原理和實現細節。首先，我們假設目標是從A點移動到B點，其中兩點之間被一堵牆隔開。圖1展示了這個示例，其中綠色代表A點，紅色代表B點，藍色代表牆。

圖1展示了簡化後的搜索區域，我們將其劃分為正方形的格子。這一簡化方法將搜索區域轉化為二維數組，數組的每一項代表一個格子，其狀態為可走或不可走。通過計算從A點到B點需要經過哪些格子，我們可以找到一條路徑。當路徑確定後，角色將從一個格子的中心移動到另一個格子的中心，直至到達目的地。

在A*演算法中，搜索區域的簡化為節點（nodes）的引入提供了基礎。節點可以被放置在任意多邊形內，可以位於多邊形的中心，也可以位於邊線上。使用這種方法最簡單的原因在於其通用性，適用於不同形狀的搜索區域。

演算法開始於定義起點A，並將其加入到一個名為開放列表（open list）的集合中。開放列表是一個待檢查的格子列表，其中的格子可能是路徑的一部分，也可能是路徑的候選。隨後，我們檢查起點A的相鄰格子，並將其中可走的或可到達的格子加入開放列表中，同時將起點A作為這些格子的父節點。在追蹤路徑時，父節點的信息至關重要。

下一步是從開放列表中選擇一個與起點A相鄰的格子，重復上述過程。但選擇哪一格子則基於其F值最小的原則。F值是由G值（從起點A到特定格子的移動代價）和H值（從該格子到終點B的估算成本）相加得到的。

路徑排序涉及計算路徑中每個格子的F、G和H值。G值代表從起點A到指定格子的移動代價，橫向和縱向移動的代價為10，對角線移動的代價為14。這些數值簡化了計算過程，同時提高了演算法的執行效率。H值通過估計起點到終點的曼哈頓距離計算得出，即橫向和縱向距離的總和，忽略對角移動。

計算出G和H值後，我們得到F值，用於後續選擇操作。在選擇過程開始時，我們會遍歷開放列表，選擇F值最小的格子。這一過程不斷重復，直到將終點加入開放列表，路徑被找到。在每一步中，選擇的格子從開放列表移除，加入到關閉列表（closed list）中，表示不再需要關注的格子。

在搜索過程中，我們需要對選定的格子執行一系列操作。首先，將該格子從開放列表中移除並加入到關閉列表中。接著，檢查與該格子相鄰的格子，忽略那些已位於關閉列表中或不可走的格子。對於不在開放列表中的相鄰格子，將其加入開放列表中，並將選定的格子作為其父節點。若相鄰格子已在開放列表中，會檢查新路徑是否更優。如果新路徑更優，則更新該格子的父節點，並重新計算其F、G和H值。

在搜索過程中，我們不斷重復上述步驟，直到找到終點或確定無法找到路徑。當終點被加入開放列表後，搜索過程完成。此時，我們可以通過追蹤父節點從終點回溯到起點，找到最短路徑。

在實現A*演算法時，關鍵在於如何高效地維護開放列表和關閉列表，以及計算路徑代價（G、H和F值）。為了優化性能，可以採用排序數據結構（如二叉堆）來管理開放列表，以便快速找到具有最小F值的格子。在考慮其他單位、優化速度、地形損耗、維護未探測區域、平滑路徑以及處理非方形搜索區域時，A*演算法的實現細節變得更為豐富和復雜。通過閱讀相關的高級主題和參考資料，如Amit的A*頁面、Smart Moves: Intelligent Path Finding和Terrain Analysis等文章，可以進一步深入理解A*演算法的高級應用和優化策略。

Ⅱ A星尋路演算法詳解

A星尋路演算法詳解

A星演算法是解決靜態路網中求解最短路徑的有效直接搜索方法。其核心公式為F = G + H，其中F表示當前點的總估價，G表示從起始點到指定網格的實際代價，H表示從當前網格點到終點的預計代價。啟發函數的大小取決於計算H代價的函數，常用啟發函數包括曼哈頓距離和歐幾里得距離。

曼哈頓距離是指在坐標系中，從一個點到另一個點沿著網格線（水平或垂直）的距離。歐幾里得距離是指在n維空間中，兩點之間的直線距離。在二維空間中，歐幾里得距離可以通過勾股定理得到。

A星演算法的實現步驟包括：根據核心公式計算當前點的F值，選取F值最小的點進行探索。計算其周圍相鄰節點的G、H、F值，更新節點的G、F值和父節點。若節點已探索，則跳過，否則加入openList並計算其F值。重復上述步驟直至找到終點。

通過例子展示A星演算法的實現過程。在網格地圖中，黑色方格表示障礙物，白色方格為可通行區域，綠色方格為起點，紅色方格為終點。根據演算法步驟，計算每個節點的G、H、F值，選擇F值最小的節點進行探索。在探索過程中，若遇到障礙物則H值不受影響。最終找到一條從起點到終點的最短路徑。

A星演算法是一種啟發式搜索演算法，通過啟發式函數評估每個節點，並選擇具有最低F值的節點作為下一個要探索的節點。最終，演算法會找到一條最優路徑。

通過一個網站演示A星演算法的過程，項目源碼可以在相關鏈接中查看。歡迎關注公眾號「前端架構師筆記」了解更多精彩文章。

Ⅲ 人工智慧 A*演算法原理

A 演算法是啟發式演算法重要的一種，主要是用於在兩點之間選擇一個最優路徑，而A 的實現也是通過一個估值函數

上圖中這個熊到樹葉的 曼哈頓距離 就是藍色線所表示的距離，這其中不考慮障礙物，假如上圖每一個方格長度為1，那麼此時的熊的曼哈頓距離就為9.
起點（X1,Y1）,終點（X2,Y2）,H=|X2-X1|+|Y2-Y1|
我們也可以通過幾何坐標點來算出曼哈頓距離，還是以上圖為例，左下角為（0，0）點，熊的位置為（1，4），樹葉的位置為（7，1），那麼H=|7-1|+|1-4|=9。

還是以上圖為例，比如剛開始熊位置我們會加入到CLOSE列表中，而熊四周它可以移動到的點位我們會加入到OPEN列表中，並對熊四周的8個節點進行F=G+H這樣的估值運算，然後在這8個節點中選中一個F值為最小的節點，然後把再把這個節點從OPEN列表中刪除，加入到Close列表中，從接著在對這個節點的四周8個節點進行一個估值運算，再接著依次運算，這樣說大家可能不是太理解，我會在下邊做詳細解釋。

從起點到終點，我們通過A星演算法來找出最優路徑

我們把每一個方格的長度定義為1，那從起始點到5位置的代價就是1，到3的代價為1.41，定義好了我們接著看上圖，接著運算

第一步我們會把起始點四周的點加入OPEN列表中然後進行一個估值運算，運算結果如上圖，這其中大家看到一個小箭頭都指向了起點，這個箭頭就是指向父節點，而open列表的G值都是根據這個進行計算的，意思就是我從上一個父節點運行到此處時所需要的總代價，如果指向不一樣可能G值就不一樣，上圖中我們經過計算發現1點F值是7.41是最小的，那我們就選中這個點，並把1點從OPEN列表中刪除，加入到CLOSE列表中，但是我們在往下運算的時候發現1點的四周，2點，3點和起始點這三個要怎麼處理，首先起始點已經加入到了CLOSE，他就不需要再進行這種運算，這就是CLOSE列表的作用，而2點和3點我們也可以對他進行運算，2點的運算，我們從1移動到2點的時候，他需要的代價也就是G值會變成2.41，而H值是不會變的F=2.41+7=9.41，這個值我們發現大於原來的的F值，那我們就不能對他進行改變（把父節點指向1，把F值改為9.41，因為我們一直追求的是F值最小化），3點也同理。

在對1點四周進行運算後整個OPEN列表中有兩個點2點和3點的F值都是7.41，此時我們系統就可能隨機選擇一個點然後進行下一步運算，現在我們選中的是3點，然後對3點的四周進行運算，結果是四周的OPEN點位如果把父節點指向3點值時F值都比原來的大，所以不發生改變。我們在看整個OPEN列表中，也就2點的7.41值是最小的，那我們就選中2點接著運算。

我們在上一部運算中選中的是1點，上圖沒有把2點加入OPEN列表，因為有障礙物的阻擋從1點他移動不到2點，所以沒有把2點加入到OPEN列表中，整個OPEN列表中3的F=8是最小的，我們就選中3，我們對3點四周進行運算是我們發現4點經過計算G=1+1=2，F=2+6=8所以此時4點要進行改變，F變為8並把箭頭指向3點（就是把4點的父節點變為3），如下圖

我們就按照這種方法一直進行運算，最後 的運算結果如下圖

而我們通過目標點位根據箭頭（父節點），一步一步向前尋找最後我們發現了一條指向起點的路徑，這個就是我們所需要的最優路徑。 如下圖的白色選中區域

但是我們還要注意幾點

最優路徑有2個

這是我對A*演算法的一些理解，有些地方可能有BUG，歡迎大家指出，共同學習。