這是一個非常簡單的小例子用來方便理解A*最基本的工作邏輯，如圖片上解釋的一樣，這裡就不在贅述，直接開始計算。

起點是a所以不存在g值即為0，它相對於z的直線距離是11，也就是說H=11，那麼我們可以輕鬆的計算出a的F為0+11 = 11 。這裡我們需要引入一個新的概念叫做鄰居點（邊緣點）

鄰居點的概念：從字面上不難看出鄰居點即為相連的點。例如a的鄰居點是b和c，c的鄰居點是b，d和e。e的鄰居點是c，d，z。相鄰且相連的點即為鄰居點。

有了鄰居點的概念後，下一步我們就要計算b和c這兩個點到底要去走哪個點了。c點的h值為a->c的實際距離為4，c點到終點的直線距離為8，f值為8+4=12。同理我們計算的b點的f=5+8=13, 我們需要把計算過f值得點都放入frontier邊緣集合中進行比較， 比較後發現c點的f值更小，所以下一步擴展到c點，因此我們需要把c點從frontier邊緣集合中剔除，加入到explored以已展集合中。但是我們也不能把 b點就這麼放棄，有可能之後要對他做g值更新，這裡可能又要介紹一個新的概念就是frontier邊緣集合。

邊緣集合: 所以計算過f值得點都要先加在邊緣集合中等待比較，比較出來的最小值的點要在邊緣集合中刪掉，加入以擴展集合，其餘的點保持不變

已擴展集合：如上面所說，在邊緣集合中剔除的點要被加入擴展集合中，並且不再作為邊緣點進行計算，這就意味著一旦加入已擴展集合中的點就將被徹底凍結，不能作為邊緣點或者鄰居點進行擴展比較

回到我們的例子中，已經從a來到了c，此時c的邊緣點是b，d，e。我們要分別計算下他們的f值，這裡可能會有個疑問就是b點不是已經計算過了么為什麼還要在這裡計算一次，原因很簡單，可以回想下，上一步計算b的路徑是a->b，但是這裡計算的是a->c->b因為這裡的b是從c擴展而來的，此時我們更新b的g值為真實路徑a->c->b = 5，和之前從a直接擴展到b代價是一樣的所以這裡面我們可以選擇不去更新（但是如果a->c->b = 4，那麼就需要重新把路徑重新更新），在計算b的f = 5+8 =13。同理可以計算出來d和e分別為16,16. 我們把d，e加入邊緣集合，通過比較發現b的值更小所以下一步走到了b。並同時刪除掉邊緣集合中的b使其加入已擴展集合中

我們又往目標邁進了一步，現在b點有兩個鄰居點分別是c和d，但是c已經加入到已擴展集合中所以b點只有一個選擇就是d，並且可以計算得到f值為14 .所以下一步走到d。

好了我們離終點越來越近了，d點的鄰居點c,e,z 通過比較發現z是終點，這時候終於走到了終點。所以我們得到的路徑就是z->d->b->a或者z->d->b->c->a。這兩種路徑走法的最短距離都是一樣的。

通過這例子主要理解下explored已擴展集合和frontier邊緣集合這兩個概念，之後我會展現一個更加形象的例子，並且一步一步的更新到終點，因為對於這個演算法最難理解的肯定就是g值得更新了，這一個點也是卡我很久的一個疑惑。

示例：

我用Excel畫了一個小地圖，圖上註明了每個數字的解釋，可以詳細的看一下

那麼我們就從第一步開始：

起點為start，終點為goal，需要跨越中間的灰色障礙物抵達終點，納悶我們開始計算路徑，首先start周圍我們可以找到8個鄰居點，分別是1-7（因為8的可能性太低所以就沒有統計進來），我們可以看出格子1,6,4相對於start的真實路徑是10即為g值，而2,3,5,7的g值為14，紅色數字表明了每個格子相對於goal的距離（這裡使用的距離統計是曼哈頓距離）因此我們可以統計出他們的f值分別為1:70， 2:84， 3:84， 4:70， 5:64， 6:50， 7:64. 因為這幾個點都是從start擴展而來，所以箭頭都指向父節點start，通過比較f值最小的點事6，所以現在移步到格子6，並且用橘黃色框框起來代表把格子6放入已擴展集合中，而剩餘的1,2,3,4,5,7放入邊緣集合中等待下次比較。

來到格子6後，可以擴展出1,7,8,9,10,5,4這些邊界點，但是其中1,7,4,5已經在之前就擴展過並且指向了父節點START，所以當來到6號格子時，我們要比較6->1,7,4,5 這幾個格子的G值是否比之前的G值小，例如：6->5 G值為10+10=20，但是此前5號格的G值為14（注意左下角的黑色數字），小於從6號擴展過來的G值，所以不必替換父節點，以此類推發現1,7,4,5都不需要更新G值。

通過比較，發現格子9的F值最小，所以從6走到了9，並且指向父節點6，同時8,10都指向6，原因很簡單8,9,10都是從格子6擴展而來。

繼續擴展，在格子9上，我們發現鄰居點7,8,5,10都有父節點，除非新的g值更小，否則我們不會更新G值和對應的父節點，我們可以在這裡計算下，例如：10這個格子通過箭頭我們可以看出來，10是從6擴展而來，進而從start擴展到6，所以計算G(start->6->10)=24，然而如果10是從9擴展而來，我們往前推算得到G(start->6->9->10）=30，很顯然這裡我們不需要對10的父節點更新，因為從6擴展而來的g值更小，希望可以很好地理解這塊的解釋，因為對後面的擴展非常非常的重要。通過比較在邊緣集合中的F值，我們發現10的F值最小所以我們下一步擴展到10並將其加入已擴展集合中

這裡加快下步驟，在格子10上邊界點補充了12,11,19和5（其中5由父節點start擴展而來除非10->5的G更小否則不更新），比較F值後，點來到5號格子

5號格子的邊緣點為4,13,12,11（因為10已經擴展過，所以不再是邊緣點），有意思的事情發生了，之前由10擴展而來的邊緣點12,11分別對應G值38,34. 但是此時在5號格子時，5->12, 5->11的G值都有所降低變成了24,28 比之前的更小，所以這裡我們要更新父節點，所以這裡我把箭頭由都指向10改成了都指向5，這裡是很重要的一步，這一步很好的更新了G值以及父節點，之後依次類推

在格子4上，這裡又有一個小點需要注意，之前13號格子是從5擴展而來的，所以對於13他的G值是28，但是相比於13->4->start，G值只有20，所以我們這裡需要更新下13的路徑變成父節點為4，並且更新13號格子的F值為90

通過一步步的擴展我們走到了終點，到了終點後我們可以通過箭頭的指引在一步步的找回start，這個路徑就是我們通過A*找到的。

偽代碼：

通過兩個例子的講解，這裡貼出來偽代碼：

function A*(start, goal)

// The set of nodes already evaluated

closedSet := {}

// The set of currently discovered nodes that are not evaluated yet. // Initially, only the start node is known. openSet := {start} // For each node, which node it can most efficiently be reached from. // If a node can be reached from many nodes, cameFrom will eventually contain the // most efficient previous step. cameFrom := an empty map // For each node, the cost of getting from the start node to that node. gScore := map with default value of Infinity

// The cost of going from start to start is zero.

gScore[start] := 0 // For each node, the total cost of getting from the start node to the goal // by passing by that node. That value is partly known, partly heuristic. fScore := map with default value of Infinity // For the first node, that value is completely heuristic. fScore[start] := heuristic_cost_estimate(start, goal) while openSet is not empty current := the node in openSet having the lowest fScore[] value if current = goal

return reconstruct_path(cameFrom, current)

openSet.Remove(current) closedSet.Add(current) for each neighbor of current if neighbor in closedSet continue // Ignore the neighbor which is already evaluated. if neighbor not in openSet // Discover a new node openSet.Add(neighbor) // The distance from start to a neighbor //the "dist_between" function may vary as per the solution requirements.

tentative_gScore := gScore[current] + dist_between(current, neighbor)

if tentative_gScore >= gScore[neighbor] continue // This is not a better path. // This path is the best until now. Record it! cameFrom[neighbor] := current gScore[neighbor] := tentative_gScore fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal) return failurefunction reconstruct_path(cameFrom, current) total_path := [current]

while current in cameFrom.Keys:

current := cameFrom[current] total_path.append(current) return total_path
推薦閱讀：