A*搜尋算法

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

基本介紹

  • 中文名:A*搜尋算法
  • 俗稱:A星算法
算法核心,A*算法流程,

算法核心

A*算法最為核心的部分,就在於它的一個估值函式的設計上:
f(n)=g(n)+h(n)
其中f(n)是每個可能試探點的估值,它有兩部分組成:
一部分,為g(n),它表示從起始搜尋點到當前點的代價(通常用某結點在搜尋樹中的深度來表示)。
另一部分,即h(n),它表示啟發式搜尋中最為重要的一部分,即當前結點到目標結點的估值,h(n)設計的好壞,直接影響著具有此種啟發式函式的啟發式算法的是否能稱為A*算法。
一種具有f(n)=g(n)+h(n)策略的啟發式算法能成為A*算法的充分條件是:
1、搜尋樹上存在著從起始點到終了點的最優路徑。
2、問題域是有限的。
3、所有結點的子結點的搜尋代價值>0。
4、h(n)=<h*(n) (h*(n)為實際問題的代價值)。
當此四個條件都滿足時,一個具有f(n)=g(n)+h(n)策略的啟發式算法能成為A*算法,並一定能找到最優解。

A*算法流程

首先將起始結點S放入OPEN表,CLOSE表置空,算法開始時:
1、如果OPEN表不為空,從表頭取一個結點n,如果為空算法失敗。
2、n是目標解嗎?是,找到一個解(繼續尋找,或終止算法)。
3、將n的所有後繼結點展開,就是從n可以直接關聯的結點(子結點),如果不在CLOSE表中,就將它們放入OPEN表,並把S放入CLOSE表,同時計算每一個後繼結點的估價值f(n),將OPEN表按f(x)排序,最小的放在表頭,重複算法,回到1。
A*算法與廣度、深度優先和Dijkstra 算法的聯繫就在於:當g(n)=0時,該算法類似於DFS,當h(n)=0時,該算法類似於BFS。且同時,如果h(n)為0,只需求出g(n),即求出起點到任意頂點n的最短路徑,則轉化為單源最短路徑問題,即Dijkstra算法。這一點,可以通過上面的A*搜尋樹的具體過程中將h(n)設為0或將g(n)設為0而得到。

相關詞條

熱門詞條

聯絡我們