A是什麼演算法

① 什麼是A搜索演算法

A*搜索演算法，俗稱A星演算法，作為啟發式搜索演算法中的一種，這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

② 人工智慧 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，歡迎大家指出，共同學習。

③ A*演算法優化

A演算法是游戲中路徑搜索的常見演算法。Dijkstra是最短路徑的經典演算法，A演算法的思路基本上和Dijkstra演算法一致，在Dijkstra演算法的基礎上增加了啟發函數，也就是：

f(n) = g(n) + h(n)

其中，n是路徑上某一點，g(n)是從出發點到該點的cost，h(n)是關於該點的啟發函數，通常是對從該點到目標花費的一個估計，例如到目標的直線距離或者曼哈頓距離。 A演算法每次選擇f(n)最小的點，然後更新所有g(n)。
如果你明白Dijkstra演算法，那麼在這里h(n) = 0 的話，A演算法就和Dijkstra演算法一樣了。
本文不詳細講解A演算法，需要詳細了解A演算法的具體過程的，參見以下兩篇文章：

理解A*演算法的具體過程
A*演算法詳解

A*演算法優化的關鍵在於h(n)的選擇。 一個啟發函數h(n)被稱為admissible的，是指h(n)的估計，不會超過節點N到目標的實際花費。
如果h(x)滿足以下條件，h(x)被稱為單調的(monotone, or consistent)。 對於任意一條邊(x,y),
h(x) <= d(x,y) + h(y)
其中d(x,y)是（x,y）的長度

如果滿足這個條件，就意味著沒有任何節點需要被處理多次，也就是說，在Dijkstra演算法中，新加入一個節點會導致已添加節點中cost降低的情況不會存在，也就不需要去更新已添加節點(稱為close set)。

如果一個啟發函數是單調的，那麼該啟發函數一定是admissible的。如果該啟發函數是admissible的，那麼可以證明A*在同類演算法中搜尋到最短的路徑。

問題出在這里：如果我們更在意的是搜索的時間空間花費，而不是最優結果，那麼A*演算法就有優化空間。所以我們放鬆要求，修改我們的啟發函數，使得我們搜尋到的路徑不會比最佳路徑差太多，就是優化演算法，稱為ε-admissible演算法。

有多種ε-admissible演算法，在此只舉例最簡單直接的一種： 加權A*(靜態加權)演算法。

假如ha(n)是一個admissible的啟發函數，我們選取新的啟發函數hw(n) = ε ha(n)，其中ε>1 作為啟發函數。就可以在某種程度上進行優化。 下圖1是使用ha(n)作為啟發式演算法，下圖2是使用hw(n)作為啟發式演算法，其中ε取5.

圖1：ha(x)作為啟發演算法

圖2：hn(x)作為啟發演算法

可以看出，ha(n)可以找到最小路徑，但是多了許多無用的搜索；而hw(n)找到的不是最優路徑，但是減少了大量無用搜索。
其他的優化演算法思路類似都是在於啟發函數的選擇。詳見參考文獻。

參考文獻：
https://en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality https://en.wikipedia.org/wiki/Consistent_heuristic