h(n):預測目前節點到結束點的距離。

Report
A* (A-star) algorithm
A*搜尋演算法:
這是一種在圖形平面上,有多個節點的
路徑,求出最低通過成本的演算法。常用
於遊戲中的NPC的移動計算(找最短的路徑)。
A*演算法公式
:f(n)=g(n)+h(n)
• g(n):從啟始點到目前節點的距離。
• h(n):預測目前節點到結束點的距離。
h(n)又稱為啟發式(heuristic),也就是錯誤嘗試法,因為不知
道最短路徑(路上有障礙),因此只能用猜測的方法去估算。
• f(n):當前節點的成本評價。
路線評分方式:
使用方程式f(n)=g(n)+h(n)計算:
g(n):從起點,沿著所產生的路徑,到當前節點的移動成本(cost)。
其中我們分配水平和垂直移動成本為10,對角線移動成本為14。
h(n):從當前節點,到終點的估計移動成本。
h(n)的估計有很多種方法,在這我們使用的方法是曼哈頓法
(Manhattan)。
使用水平和垂直的走法(忽略對角線走法和忽略路上障礙物),
當前格子到目標所經過的格子總數乘上10做為估計成本
G:10
H:30
f(n)
g(n)
起點
G:10
H:30
h(n)
當前結點
終點
G:14
H:20
從
A*演算法範例:
說明:綠色為起點A,藍色為障礙物,紅色為目標終點,
找到一條從起點A到目標的最短路徑。
開始搜尋,如下:
1.把起點A加入“open list” 。
2.起點A相鄰可到達的格子跟起點A做連結,並把這些格子加入“open list”。
此外把起點A設為這些格子的父節點。
3.起點A從“open list”移除,然後加到“closed list”。
淺藍色的外框表示此格子在“closed list”
淺綠色的外框表示此格子在“open list”
灰色指標指向父節點
下一步,我們要選擇一個在“open list” 裡的
格子做前進,但要選哪一個格子做前進?
A: f(n)最小的格子。
計算結果如下圖:
繼續搜尋:
4.在“open list” 裡選出一個f(n)最小的格子。
5.把此選出來的格子從“open list” 移除,然後加到“closed
list”。
6.查看此格子相鄰可到達格子(忽略那些“closed list”和不可到達的
格子),如果有還沒加到“open list” 的格子把它加入,並把新加入
格子的父節點指向此節點。
7.如果此格子相鄰的格子中,有早已經在“open list”的格子,那要
檢查是否經由當前的格子到這早在“open list”的格子,看早在
“open list”的格子的g(n)會不會比原來的g(n)減少,如果會,那這
早在“open list”的格子的父節點就要改變指向此當前的格子,並重
新計算此f(n)和g(n),如果不會,就什麼事都不用做。
繼續搜尋:
4.在“open list” 裡選出一個f(n)最小的格子。
5.把此選出來的格子從“open list” 移除,然後加到“closed list”。
74
14
60
60
10
54
50
60
10
40
F:40
50
74
14
14
G:10 H:30
60
60
10
54
50
14
40
繼續搜尋:
6.查看此格子相鄰可到達格子(忽略那些“closed list”和不可到達的格子),如
果有還沒加到“open list” 的格子把它加入,並把新加入格子的父節點指向此
節點。
74
14
60
60
10
54
50
60
10
40
F:40
50
74
14
14
G:10 H:30
60
60
10
54
50
14
40
繼續搜尋:
7.如果此格子相鄰的格子中,有早已經在“open list”的格子,那麼便檢查經由當前
格子到早在“open list”的格子之g(n)會不會比原來的g(n)減少
74
14
60
60
10
54
50
60
10
40
F:40
50
74
14
14
G:10 H:30
60
60
10
54
50
14
40
繼續搜尋:
如果會:那這早在“open list”的格子的父節點就要改變指向此當前的格子,並重
新計算此f(n)和g(n)。
如果不會:就什麼事都不用做。
74
14
60
60
10
54
50
60
10
40
F:40
50
74
14
14
G:10 H:30
60
60
10
54
50
14
40
74
14
60
60
10
54
50
60
10
40
F:40
50
74
14
14
G:10 H:30
60
60
10
54
50
88
28
14
40
74
60
24
50
重複做上一面4~7的步驟,直到加到目標格子加到“closed list”
中,則會像下面一張圖
88
28
74
14
74
60
60
60
10
50
50
40
G:10 H:30
60
60
10
54
50
88
80
94
24
14
F:40
74
14
50
54
60
10
24
70
28
20
14
40
74
60
24
50
。
最後只要從目標格子照著父節點往回推,推到起始點後,此路徑就是最短路徑了。
像下面一張圖。
A-star和Dijkstra 演算法比較:
如果h(n)為0,只需求出g(n),即求出起點到任意頂點n的最
短路徑,則轉化為單源最短路徑問題,即Dijkstra演算法
Dijkstra演算法雖然可以保證找到一條最短的路徑, 但不
如A* 演算法這樣簡捷快速。這是因為A* 演算法採用了
一套特殊的啟發式評價(Heuristic ),讓明顯的壞路排除
考慮。而Dijkstra演算法少了Heuristic,只能每一個方向
都搜尋,搜尋的範圍大了許多,所以速度比A*慢。
Dijkstra
無
障
礙
有
障
礙
A-star
此圖描述A*從起點到
終點的過程。空心點
為open set,實心點為
close set,顏色越接近
綠色表示越靠近終點。
此圖描述Dijkstra's algorithm
從起點到終點的過程。空心點
為open set,實心點為close set,
顏色越接近綠色表示越靠近終點。
資料和圖片來源:
http://zh.wikipedia.org/zh-tw/A*%E6%90%9C%E5%AF%BB%E7%AE%97%E6%B3%95
http://blog.minstrel.idv.tw/2004/12/star-algorithm.html
http://www.policyalmanac.org/games/aStarTutorial.htm#code
http://www.youtube.com/watch?feature=endscreen&NR=1&v=19h1g22hby8
http://www.ccg.leeds.ac.uk/people/j.macgill/xaStar/

similar documents