本文要介紹啟發式搜索這個領域,並示範如何以 Java 實作其中最廣泛使用的 A* 演算法。作者會先展示教科書式的實作為何會撞上記憶體與效能天花板,接著透過資料表示優化、替代集合框架與垃圾回收控制,逐步把效能拉回可用區間。
在人工智慧領域,狀態空間搜索是一項基礎技術:把問題建模為一個由可能狀態構成的空間,再在其中尋找可行解。啟發式搜索則是它的一個分支,特色是利用關於問題的先驗知識,以更少的代價找到解答。本文將帶你理解這個領域,並用 Java 完成 A*——最廣為使用的啟發式搜索演算法。由於這類演算法對運算與記憶體的要求都很高,我們也會說明如何抑制垃圾回收帶來的額外成本,並借助一套高效能的集合框架完成優化。全文範例程式碼可於文末下載。
電腦科學中大量問題可以用圖形資料結構表示,圖中的路徑即代表候選解答,因此「找最短路徑」就等同於「找最佳解」。以電子遊戲中的自主角色為例,角色的每一個動作對應圖上的一條邊,目標是抵達與對手交鋒的位置。
深度優先與廣度優先是最常見的圖形遍歷演算法,但它們屬於非啟發式方法,能處理的問題規模受到嚴格限制。此外,深度優先無法保證找到最佳解(某些情況下甚至找不到任何解),廣度優先也僅在特殊條件下才保證最佳性。相較之下,啟發式搜索是一種提示性搜索:它把問題知識以啟發函數的形式編碼進演算法,使求解效率大幅提升,因而能處理非啟發式方法完全無法負荷的難題。
遊戲路徑規劃是這個領域的經典應用,但能力不止於此。2007 年 DARPA 城市挑戰賽的優勝隊伍,便以啟發式搜索規劃可行路線;自然語言處理中的語音辨識解碼與句法分析、機器人學與生物資訊學,也都有成功案例。在多序列比對(MSA)這個資訊學難題上,相較於傳統的動態規劃做法,啟發式搜索能以更少記憶體、更快速度求解。
由於記憶體與運算需求高,實務上 C/C++ 往往是首選,Java 則被視為不划算的選擇。本文的目標之一,就是說明 Java 其實是可行且合適的語言。我們會先證明教科書式實作確實會在標準基準測試上耗盡記憶體,接著重新檢視幾個關鍵實作細節,透過替代集合框架逐一解決問題。
本文內容擴展自作者合著的一篇學術論文。原論文聚焦 C/C++,但其中多數概念同樣適用於 Java。
廣度優先搜索(BFS)與啟發式搜索共享大量概念與術語,理解它的實作細節,有助於後續討論。我們採用以代理為中心的視角:代理處於某個狀態,在該狀態下可執行一組操作;套用操作會使代理轉移到新的後繼狀態。這個模型能涵蓋相當廣泛的問題類型。
BFS 的目標是找出一連串操作,把代理從初始狀態引導到目標狀態。它從初始狀態出發,每回合拜訪最近產生的狀態,對該狀態套用所有可行操作以產生新狀態,並把新狀態加入尚未拜訪的清單(稱為搜尋的前沿)。「拜訪一個狀態並產生其所有後繼」的過程,稱為展開。
這個過程可以想成一棵樹的建構:根節點是初始狀態,子節點透過代表操作的邊連結。下圖為例,白圈是前沿節點,灰圈是已展開節點。

樹上每個節點代表一個狀態,但兩個不同節點可能對應同一個狀態——例如不同深度的兩個節點具有相同狀態。這些重複節點代表抵達同一狀態的兩條路徑,若不加處理會造成重複運算,因此必須記錄所有已拜訪的節點。
清單 1 是 BFS 的偽代碼:
function: BREADTH-FIRST-SEARCH(initial)
open ← {initial}
closed ← 0
loop do:
if EMPTY(open) then return failure
node ← SHALLOWEST(open)
closed ← ADD(closed, node)
for each action in ACTIONS(node)
successor ← APPLY(action, node)
if successor in closed then continue
if GOAL(successor) then return SOLUTION(node)
open ← INSERT(open, successor)
前沿保存在 open 清單(第 2 行),已拜訪節點保存在 closed 清單(第 3 行)。closed 的作用是避免重複拜訪,節點只有在不在 closed 中時才會被加入前沿。迴圈在 open 清空或找到目標時結束。
如圖 1 所示,BFS 會在進入下一層之前,拜訪當前深度層的所有節點。在「所有操作成本相同」的問題中,搜尋樹上的邊權重一致,這時 BFS 保證能找到最佳解——第一個產生的目標必在最短路上。但若各操作成本不同,邊權重就不均勻,此時 BFS 無法保證最佳性;更麻煩的是,它仍必須展開到達目標之前的所有節點,所需的記憶體極可能超出最先進電腦的容量,這使 BFS 只能處理規模很小的問題。
Dijkstra 演算法是 BFS 的擴展,它依「從初始狀態抵達該節點的成本」對前沿排序。只要成本非負,不論是否均勻,它都能保證最佳解;代價是必須拜訪所有成本小於最佳解的節點,因此可解問題數量仍然有限。下一節要介紹的演算法,能在大幅減少拜訪節點數的前提下完成同樣的保證。
A* 及其變體是最廣泛使用的啟發式搜索演算法。可以把 A* 視為 Dijkstra 的擴展:它引入問題相關的知識,在仍保證最佳解的情況下減少計算量。兩者都屬於最佳優先圖形遍歷演算法——優先拜訪「看起來最可能位於通往目標的最短路徑上」的節點,直到找到解答。在許多問題中,找到最佳解至關重要,這是這類演算法的價值所在。
A* 的關鍵差異在於使用了啟發式估值。在搜索演算法的語境中,啟發式估值有明確含義:一個估算「從某節點到目標 còn需成本」的函數。A* 藉此判斷哪些節點最值得拜訪,避免無效計算,也避免深入那些幾乎不可能通往最佳解的區域,因此通常以更少記憶體、更快速度求解。
具體做法是為每個節點計算一個 f 值,並依此排序 open 清單。f 值由兩個量組成:節點的 g 值(從初始狀態抵達該節點的累計成本)與 h 值(到目標的估算成本,即啟發式估值)。f 值最小的節點,就是最該拜訪的節點。

圖 2 中,前沿有三個節點,兩個 f 值為 5,一個為 3。A* 展開 f 值最小的那個,而它直接通往目標,於是另外兩個節點底下的整棵子樹都不必拜訪(圖 3)。這正是 A* 遠比 BFS 高效的原因。

若 A* 使用的啟發式估值是可接受的(admissible),它就只會拜訪找到最佳解所必需的節點。可接受的意思是「永不高估」:估計值必須小於或等於實際到達目標的成本,也就是一個下限值。若啟發式還滿足一致性(consistency),則每個狀態首次被產生時必定位於最佳路徑上,重複節點的處理也能更有效率。正因這個性質,A* 廣受歡迎——沒有其他演算法能在可接受的啟發式下,用更少節點保證最佳解。
與 BFS 類似,A* 維護兩個資料結構:已產生但未拜訪的節點放在 open 清單,已拜訪的節點放在 closed 清單。這兩個結構的實作方式,對效能有決定性影響,後文會詳細討論。
清單 2 是 A* 的完整偽代碼。
function: A*-SEARCH(initial)
open ← {initial}
closed ← 0
loop do:
if EMPTY(open) then return failure
node ← BEST(open)
if GOAL(node) then return SOLUTION(node)
closed ← ADD(closed, node)
for each action in ACTIONS(node)
successor ← APPLY(action, node)
if successor in open or successor in closed
IMPROVE(successor)
else
open ← INSERT(open, successor)
每次迴圈從 open 取出最佳節點,展開它、產生所有後繼;對每個後繼檢查是否已拜訪,若已拜訪則判斷是否存在更短路徑,若有則改放到 open 並移除次優節點。
我們可以用兩個假設簡化這段邏輯:所有操作成本相同,且啟發式可接受並一致。在一致性成立且成本均勻的前提下,不可能透過更短路徑重訪某狀態;同時,對某些問題而言,直接把重複節點放進 open、等取出時再檢查,反而比每次產生時都查重更有效率。於是清單 3 的簡化版把原偽代碼最後四行合併為一行,展開前只需確認該節點是否已在 closed 中即可避免迴圈,IMPROVE 函數也不再需要。
function: A*-SEARCH(initial)
open ← {initial}
closed ← 0
loop do:
if EMPTY(open) then return failure
node ← BEST(open)
if node in closed continue
if GOAL(node) then return SOLUTION(node)
closed ← ADD(closed, node)
for each action in ACTIONS(node)
successor ← APPLY(action, node)
open ← INSERT(open, successor)
本節依清單 3 完成一份直接的 Java 實作。你會看到,它在 30GB 記憶體限制下無法解決標準的啟發式搜索基準問題。
為了讓實作保持通用,我們先定義介面來抽離「A* 要解的問題是什麼」。任何要交給 A* 處理的問題都需實作 Domain 介面,提供查詢初始狀態、查詢可行操作、計算啟發式估值與產生後繼狀態等方法。
Domain 介面的 Java 原始碼public interface Domain {
public T initial();
public int h(T state);
public boolean isGoal(T state);
public int numActions(T state);
public int nthAction(T state, int nth);
public Edge apply (T state, int op);
public T copy(T state);
}
A* 在搜尋樹上產生邊與節點,因此需要 Edge 與 Node 兩個類別。每個節點含四個欄位:所表示的狀態、父節點參照,以及 g 與 h 值。
Node 類別的 Java 原始碼class Node {
final int f, g, pop;
final Node parent;
final T state;
private Node (T state, Node parent, int cost, int pop) {
this.g = (parent != null) ? parent.g+cost : cost;
this.f = g + domain.h(state);
this.pop = pop;
this.parent = parent;
this.state = state;
}
}
每條邊含三個欄位:成本或權重、產生後繼節點所用的操作、產生父節點所用的操作。
Edge 類別的 Java 原始碼public class Edge {
public int cost;
public int action;
public int parentAction;
public Edge(int cost, int action, int parentAction) {
this.cost = cost;
this.action = action;
this.parentAction = parentAction;
}
}
A* 本身實作 SearchAlgorithm 介面,只依賴 Domain 與 Edge。該介面提供單一方法執行搜索並回傳 SearchResult,後者承載搜索統計。
SearchAlgorithm 介面的 Java 原始碼public interface SearchAlgorithm {
public SearchResult search(T state);
}
open 與 closed 的資料結構選擇是關鍵細節。這裡用 Java 的 PriorityQueue 實作 open:它是一個平衡二元堆,入列與出列為 O(log n),測試元素是否在佇列中為線性時間,存取佇列頭為常數時間。二元堆是 open 的常見選擇;後文會說明,對某些問題用「桶式優先佇列」會更有效率。
本文以 15 puzzle 這個 toy 問題作為評估基準。它性質簡單易懂,是評估啟發式搜索演算法的標準題目(有人稱之為 AI 研究的「果蠅」)。15 puzzle 是滑塊拼圖:4×4 網格上放著 15 個滑塊,其中一格永遠空著,與空格相鄰的滑塊可以滑入該格,目標是透過滑動還原成指定排列。


作為基準,我們要求以盡可能少的移動次數從初始布局抵達目標布局。
本文使用的啟發式稱為曼哈頓距離:某滑塊的曼哈頓距離,是它到達目標位置所需的垂直與水平移動格數之和。一個狀態的啟發式估值,就是所有滑塊曼哈頓距離的總和(忽略空格)。由於無法靠「減少移動」把滑塊送到每個目標位置,這個總和必然是實際所需成本的下限值,因此它是可接受的啟發式。
把每種滑塊排列視為節點,若存在一個操作能把排列 A 轉為排列 B,就在兩節點間連一條邊,即得到狀態空間圖(圖 6)。

15 個滑塊在網格上的排列方式共有 16! 種,但受限於拼圖的物理約束,真正可達的狀態「只有」16!/2 = 10,461,394,944,000 種。試想即使能用 1 個位元組表示一個狀態(實際不可能),存下整個狀態空間也需要超過 10TB 記憶體,遠超任何現今電腦的容量。啟發式搜索的價值,就在於只拜訪其中極小的一部分,仍能保證最佳解。
實驗採用 15 puzzle 的一組著名起始布局,稱為 Korf 100。這組題目源自 Richard E. Korf 的研究——他最早證實可用 A* 的迭代加深變體 IDA* 求解隨機產生的 15 puzzle 布局。此後這 100 個隨機實例被廣泛沿用於啟發式搜索實驗。我們的實作經過優化,已不需迭代加深。
我們一次求解一個布局,每個布局存放在獨立的純文字檔案中,路徑由命令列參數指定。程式入口點為 TileSolver 類別,負責解析參數、建立問題實例並執行 A*。每次執行結束會把效能統計印到標準輸出,其中最受關注的是實測耗時(wall clock time);把各次執行的耗時相加,即為該基準的總執行時間。
原始碼中包含自動化實驗的 Ant 任務,可執行完整實驗:
ant TileSolver.korf100 -Dalgorithm="efficient"
algorithm 可指定 efficient 或 textbook。也可執行單一實例:
ant TileSolver -Dinstance="12" -Dalgorithm="textbook"
或執行不含三道最難題目的子集:
ant TileSolver.korf97 -Dalgorithm="textbook"
多數電腦的記憶體不足以用 textbook 版跑完全部實驗。為避免進入交換(swap),應謹慎限制 Java 行程可用的記憶體量;在 Linux 上可用 ulimit 這類 shell 指令設定。
| 演算法 | 最大記憶體使用量 | 總執行時間 |
|---|---|---|
| Textbook | 25GB | 1,846 秒 |
| Packed states | 11GB | 1,628 秒 |
| HPPC | 7GB | 1,084 秒 |
教科書版無法解出全部測資:三道最難的題目失敗,其餘題目則耗時超過 1,800 秒。這個成績不算好——C/C++ 的最佳實作能在 600 秒內解完 100 題。
失敗原因是記憶體。每次從 open 取出一個節點並展開,通常會產生更多節點,open 所需的記憶體隨之膨脹。這並非 Java 特有的問題,同等條件的 C/C++ 實作也會失敗。Burns 等人的研究顯示,C/C++ 的高效 A* 能在 30GB 以內解完該基準,因此我們決定繼續優化 Java 版本。
用 VisualVM 這類探查器檢視記憶體配置後發現,幾乎全部記憶體都被 Node 佔用,更具體說是其中的 TileState。
每個滑塊狀態原本用一個含 15 個整數的陣列記錄位置。其實可以把這 15 個位置打包進一個 64 位整數(Java 的 long)。放在 open 中的節點只需保存這個打包表示,每個節點即可省下 52 個位元組。求解最難實例約需保存 5.33 億個節點,光是這一項就能省下約 25GB 記憶體。
為保持通用性,我們擴充 SearchDomain 介面,加入打包與解包方法。節點進入 open 前先產生打包表示存入 Node,需要展開時再解包還原。
pack() 方法的 Java 原始碼public long pack(TileState s) {
long word = 0;
s.tiles[s.blank] = 0;
for (int i = 0; i < Ntiles; i++)
word = (word << 4) | s.tiles[i];
return word;
}
unpack() 方法的 Java 原始碼public void unpack(long packed, TileState state) {
state.h = 0;
state.blank = -1;
for (int i = numTiles - 1; i >= 0; i--) {
int t = (int) packed & 0xF;
packed >>= 4;
state.tiles[i] = t;
if (t == 0)
state.blank = i;
else
state.h += md[t][i];
}
}
由於打包表示是狀態的規範形式,closed 也可以直接存打包值。但 HashMap 無法存放基本型別,必須包成 Long 物件。表 1 第二列是套用打包後的結果:記憶體降低 55%,時間也有所縮短,但仍解不完整個基準。
把每個打包值再包進一個 Long,開銷顯然不小:既浪費記憶體,也容易觸發過度垃圾回收。JDK 1.5 加入的 autoboxing 會自動在 long 與 Long 之間轉換,而對大型集合而言,這些轉換會同時拖累記憶體與 CPU 表現。
同一版本引入的泛型也幫不上忙。Burns 等人指出,C++ 模板在實作啟發式搜索時帶來巨大效能優勢,但 Java 泛型採用型別抹除實作,編譯時所有型別資訊都被移除,執行期仍需型別檢查,大型集合下問題明顯。
HashMap 本身也有額外開銷:內部以陣列存放 HashMap$Entry 物件,每次新增元素就建立一個條目,每個條目通常含三個物件參照與一個 32 位整數,合計約 32 位元組。closed 中有 5.33 億個節點時,光是條目開銷就超過 15GB。
既然 closed 現在只存基本型別,就可以改用 HPPC(High Performance Primitive Collections)。這是一套替代集合框架,支援直接存放原生值,省下 JCF 伴隨的所有包裝成本。有別於 Java 泛型,HPPC 以類似 C++ 模板的技術在編譯期為每種集合與每個原生型別各產生一份實作,因此不必再用 Long、Integer 包裝,也省下大量強制轉型。
其他替代方案如 Apache Commons Primitive Collections 與 fastutils 也各有可取之處。我們認為 HPPC 在實作高效能演算法時有一項明顯優勢:它公開每個集合的內部資料儲存。能直接存取底層陣列,就有更多優化空間——例如若要把 open 或 closed 寫到磁碟,直接操作陣列遠比透過迭代器有效率。
改動相當簡單:closed 改用 LongOpenHashSet,因為只存原生值,不再需要覆寫 hashcode 與 equals;而 closed 本質上是集合(不含重複元素),只需存值、不需鍵值對。表 1 第三列是這步的結果:記憶體再降 27%,時間減少 33%。累計下來記憶體共減少 82%,終於能在限制內解完整個基準。
| 演算法 | 最大記憶體使用量 | 總執行時間 |
|---|---|---|
| HPPC | 30GB | 1,892 秒 |
| 嵌套桶隊列 | 30GB | 1,090 秒 |
| 避免垃圾收集 | 30GB | 925 秒 |
憑 HPPC,我們能在 30GB 內解完 100 題,但耗時仍超過 1,800 秒。接下來的優化針對另一個關鍵結構:open。
每次把元素加入 open 都需重新排序,PriorityQueue 的入列與出列為 O(log n)。排序效率雖高,但並非免費,特別是 n 很大時——最難的實例曾經把超過 5 億個節點放進 open。此外,由於本基準中所有操作成本相同,可能的 f 值範圍很窄,使用 PriorityQueue 的收益與開銷相比可能並不划算。
替代方案是桶式優先佇列。若操作成本落在狹窄範圍,可以為每個可能的 f 值預備一個桶:產生節點時直接放進對應的桶,取出時從 f 值最小的桶開始找。這種「一級桶優先佇列」支援常數時間的入列與出列。

但這樣做會失去用 g 值打破 f 值平手的優化能力——前面提過,這個優化是值得保留的。解法是嵌套桶優先佇列:一級桶表示 f 值範圍,巢狀層級表示 g 值範圍。

把 open 改為嵌套桶優先佇列後(完整實作見原始碼中的 BucketHeap.java),執行時間從 1,892 秒降到 1,090 秒,縮短近 58%。表 2 第二列即為此結果。
垃圾回收常被視為 Java 的罩門。關於 JVM 的 GC 調優已有大量優秀文獻,這裡不深入討論該主題,只談與 A* 直接相關的一項優化。
A* 會產生大量短命的狀態與邊物件,帶來可觀的 GC 負擔。最難的問題會產生 5.33 億個節點,而在每次迴圈中配置新邊與新狀態並非必要——我們可以在所有迭代中重複使用同一組狀態與邊物件。
要做到這點,需修改 Domain 介面:與其讓 apply() 回傳 Edge 實例,改為由呼叫端提供實例、由 apply() 就地修改。由於邊的欄位是被覆寫而非累加,傳入前不必理會其中原本的值;但 apply() 對狀態所做的修改是累加的,因此必須提供一個還原機制,才能在不複製狀態的前提下正確產生所有後繼。為此我們加入 undo() 方法。
Domain 介面public interface Domain {
...
public void apply(T state, Edge edge, int op);
public void undo(T state, Edge edge);
...
}
表 2 第三列是最終結果:透過物件回收再利用,執行時間再縮短超過 15%,來到 925 秒。對照 C/C++ 最佳實作的 27GB 與 540 秒,這個 Java 版本只慢約 1.7 倍,記憶體用量相當,成績已相當接近。
本文介紹了啟發式搜索與 A* 演算法,示範了一份直接的 Java 實作,指出它在記憶體與時間上的問題,並透過三個步驟逐步解決:以打包表示壓縮狀態、以 HPPC 取代 JCF、以嵌套桶優先佇列取代 PriorityQueue,最後藉由物件重用抑制垃圾回收。改進後的實作能在合理資源限制內解完標準基準,說明 Java 確實是實作啟發式搜索的可行選擇。
更重要的是,這些技術並不限於人造基準問題。任何需要保存大量原生值的 Java 應用,導入 HPPC 這類框架往往能立即獲得效能改善;而「減少配置、重用物件」的思路,在多數高吞吐場景中都適用。
| 描述 | 名稱 | 大小 |
|---|---|---|
| 範例程式碼 | j-ai-code.zip | 58KB |
注:相關網站建設技巧閱讀請移步到建站教程頻道。