了解啟發(fā)式搜索領(lǐng)域及其在人工智能上的應(yīng)用。本文作者展示了他們?nèi)绾纬晒τ?Java 實(shí)現(xiàn)了最廣為使用的啟發(fā)式搜索算法。他們的解決方案利用一個(gè)替代的 Java 集合框架，并使用最佳實(shí)踐來避免過多的垃圾收集。

通過搜尋可行解決方案空間來解決問題是人工智能中一項(xiàng)名為狀態(tài)空間搜索 的基本技術(shù)。 啟發(fā)式搜索 是狀態(tài)空 間搜索的一種形式，利用有關(guān)一個(gè)問題的知識(shí)來更高效地查找解決方案。啟發(fā)式搜索在各個(gè)領(lǐng)域榮獲眾多殊榮。在本文中，我們將向您介紹啟發(fā)式搜索領(lǐng)域，并展示 如何利用 Java 編程語言實(shí)現(xiàn) A*，即最廣為使用的啟發(fā)式搜索算法。啟發(fā)式搜索算法對(duì)計(jì)算資源和內(nèi)存提出了較高的要求。我們還將展示如何避免昂貴的垃圾收集，以及如何利用一個(gè)替代的高 性能 Java 集合框架 (JCF)，通過這些改進(jìn) Java 實(shí)現(xiàn)。本文的所有代碼都可以從 下載 部分獲得。

啟發(fā)式搜索

計(jì)算機(jī)科學(xué)中的許多問題可用一個(gè)圖形數(shù)據(jù)結(jié)構(gòu)表示，其中圖形中的路徑表示潛在的解決方案。查找最優(yōu)解決方案需要找到一個(gè)最短路徑。例如，以自主視頻游戲角色為例。角色做出的每個(gè)動(dòng)作都與圖形中的一個(gè)邊緣相對(duì)應(yīng)，而且角色的目標(biāo)是找到最短路徑，與對(duì)手角色交手。

深度優(yōu)先 搜索和廣度優(yōu)先 搜索等算法是流行的圖形遍歷算法。但它們被視為非啟發(fā)式 算法，而且常常受到它們可以解決的問題規(guī)模的嚴(yán)格限制。此外，不能保證深度優(yōu)先搜索能找到最優(yōu)解決方案（或某些情況下的任何解決方案），可以保證廣度優(yōu)先搜索僅能在特殊情況下找到最優(yōu)解決方案。相比之下，啟發(fā)式搜索是一種提示性 搜索，利用有關(guān)一個(gè)問題的知識(shí)，以啟發(fā)式 方式進(jìn)行編碼，從而更高效地解決問題。啟發(fā)式搜索可以解決非啟發(fā)式算法無法解決的很多難題。

視頻游戲?qū)ぢ肥菃l(fā)式搜索的一個(gè)受歡迎的領(lǐng)域，它還可以解決更復(fù)雜的問題。2007 年舉行的無人駕駛汽車比賽 “DARPA 城市挑戰(zhàn)賽” 的優(yōu)勝者就利用了啟發(fā)式搜索來規(guī)劃平坦的、直接的可行使路線。啟發(fā)式搜索在自然語言處理中也有成功應(yīng)用，它被用于語音識(shí)別中的文本和堆棧解碼句法解析。它 在機(jī)器人學(xué)和生物信息學(xué)領(lǐng)域也有應(yīng)用。與傳統(tǒng)的動(dòng)態(tài)編程方法相比較，使用啟發(fā)式搜索可以使用更少的內(nèi)存更快地解決多序列比對(duì) (Multiple Sequence Alignment, MSA)，這是一個(gè)經(jīng)過深入研究的信息學(xué)問題。

通過 Java 實(shí)現(xiàn)啟發(fā)式搜索

Java 編程語言不是實(shí)現(xiàn)啟發(fā)式搜索的一種受歡迎的選擇，因?yàn)樗鼘?duì)內(nèi)存和計(jì)算資源的要求很高。出于性能原因，C/C++ 通常是首選語言。我們將證明 Java 是實(shí)現(xiàn)啟發(fā)式搜索的一種合適的編程語言。我們首先表明，在解決受歡迎的基準(zhǔn)問題集時(shí)，A* 的 textbook 實(shí)現(xiàn)確實(shí)很緩慢，并且會(huì)耗盡可用內(nèi)存。我們通過重訪一些關(guān)鍵實(shí)現(xiàn)細(xì)節(jié)和利用替代的 JCF 來解決這些性能問題。

很多這方面的工作都是本文作者合著的一篇學(xué)術(shù)論文中發(fā)表的作品的一個(gè)擴(kuò)展。盡管原作專注于 C/C++  編程，但在這里，我們展示了適用于 Java 的許多同樣的概念。

廣度優(yōu)先搜索

熟悉廣度優(yōu)先搜索（一個(gè)共享許多相同概念和術(shù)語的更簡(jiǎn)單的算法）的實(shí)現(xiàn)，將幫助您理解實(shí)現(xiàn)啟發(fā)式搜索的細(xì)節(jié)。我們將使用廣度優(yōu)先搜索的一個(gè)以代理為中心 的視圖。在一個(gè)以代理為中心的視圖中，代理據(jù)說處于某種狀態(tài)，并且可從該狀態(tài)獲取一組適用的操作。應(yīng)用操作可將代理從其當(dāng)前狀態(tài)轉(zhuǎn)換到一個(gè)新的后繼 狀態(tài)。該視圖適用于多種類型的問題。

廣度優(yōu)先搜索的目標(biāo)是設(shè)計(jì)一系列操作，將代理從其初始狀態(tài)引導(dǎo)至一個(gè)目標(biāo)狀態(tài)。從初始狀態(tài)開始，廣度優(yōu)先搜索首先訪問最近生成的狀態(tài)。所有適用的操作在每個(gè)訪問狀態(tài)都可以得到應(yīng)用，生成新的狀態(tài)，然后該狀態(tài)被添加到未訪問狀態(tài)列表（也稱為搜索的前沿）。訪問狀態(tài)并生成所有后繼狀態(tài)的過程被稱為擴(kuò)展 該狀態(tài)。

您可以將該搜索過程看作是生成了一個(gè)樹：樹的根節(jié)點(diǎn)表示初始狀態(tài)，子節(jié)點(diǎn)由邊緣連接，該邊緣表示用于生成它們的操作。圖 1 顯示該搜索樹的一個(gè)圖解。白圈表示搜索前沿的節(jié)點(diǎn)?；胰Ρ硎疽颜归_的節(jié)點(diǎn)。

圖 1. 二叉樹上的廣度優(yōu)先搜索順序

搜索樹中的每一個(gè)節(jié)點(diǎn)表示某種狀態(tài)，但兩個(gè)獨(dú)特的節(jié)點(diǎn)可表示同一狀態(tài)。例如，搜索樹中處于不同深度的一個(gè)節(jié)點(diǎn)可以與樹中較高層的另一個(gè)節(jié)點(diǎn)具有同樣的狀態(tài)。這些重復(fù) 節(jié)點(diǎn)表示在搜索問題中達(dá)到同一狀態(tài)的兩種不同方式。重復(fù)節(jié)點(diǎn)可能存在問題，因此必須記住所有受訪節(jié)點(diǎn)。

清單 1 顯示廣度優(yōu)先搜索的偽代碼：

清單 1. 廣度優(yōu)先搜索的偽代碼

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) 

在清單1中，我們將搜索前沿保留在一個(gè) open 列表（第 2 行）中。將訪問過的節(jié)點(diǎn)保留在 closed 列表（第 3 行）中。closed 列表有助于確保我們不會(huì)多次重訪任何節(jié)點(diǎn)，從而不會(huì)重復(fù)搜索工作。僅當(dāng)一個(gè)節(jié)點(diǎn)不在 closed 列表中時(shí)才能將其添加到前沿。搜索循環(huán)持續(xù)至 open 列表為空或找到目標(biāo)為止。

在圖1中，您可能已經(jīng)注意到，在移至下一層之前，廣度優(yōu)先搜索會(huì)訪問搜索樹的每個(gè)深度層的所有節(jié)點(diǎn)。在所有操作具有相同成本的問題中，搜素樹中的所有邊緣具 有相同的權(quán)重，這樣可保證廣度優(yōu)先搜索能找到最優(yōu)解決方案。也就是說，生成的第一個(gè)目標(biāo)在從初始狀態(tài)開始的最短路徑上。

在某些域中，每個(gè)操作有不同的成本。對(duì)于這些域，搜索樹中的邊緣具有不統(tǒng)一的權(quán)重。在這種情況下，一個(gè)解決方案的成本是從根到目標(biāo)的路徑上所有邊緣 權(quán)重的總和。對(duì)于這些域，無法保證廣度優(yōu)先搜索能找到最優(yōu)解決方案。此外，廣度優(yōu)先搜索必須展開樹的每個(gè)深度層的所有節(jié)點(diǎn)，直至生成目標(biāo)。存儲(chǔ)這些深度層 所需的內(nèi)存可能會(huì)快速超過最現(xiàn)代的計(jì)算機(jī)上的可用內(nèi)存。這將廣度優(yōu)先搜索限制于很窄的幾個(gè)小問題。

Dijkstra 的算法是廣度優(yōu)先搜索的一個(gè)擴(kuò)展，它根據(jù)從初始狀態(tài)到達(dá)節(jié)點(diǎn)的成本對(duì)搜索前沿上的節(jié)點(diǎn)進(jìn)行排序（排列 open 列表）。不管操作成本是否統(tǒng)一（假設(shè)成本是非負(fù)值），它都確保可以找到最優(yōu)解決方案。然而，它必須訪問成本少于最優(yōu)解決方案的所有節(jié)點(diǎn)，因此它被限制于解 決較少的問題。下一節(jié)將描述一個(gè)能解決大量問題的算法，該算法能大幅減少查找最優(yōu)解決方案所需訪問的節(jié)點(diǎn)數(shù)量。

#p#

A* 搜索算法

A* 算法或其變體是最廣為使用的啟發(fā)式搜索算法之一。可以將 A* 看作是 Dijkstra 的算法的一個(gè)擴(kuò)展，它利用與一個(gè)問題有關(guān)的知識(shí)來減少查找一個(gè)解決方案所需的計(jì)算數(shù)量，同時(shí)仍然保證最優(yōu)的解決方案。A* 和 Dijkstra 的算法是最佳優(yōu)先 圖形遍歷算法的典型示例。它們是最佳優(yōu)先算法，是因?yàn)樗麄兪紫仍L問最佳的節(jié)點(diǎn)，即出現(xiàn)在通往目標(biāo)的最短路徑上的那些節(jié)點(diǎn)，直至找到一個(gè)解決方案。對(duì)于許多問題，找到最佳解決方案至關(guān)重要，這是讓 A* 這樣的算法如此重要的原因。

A* 與其他圖形遍歷算法的不同之處在于使用了啟發(fā)式估值。啟發(fā)式估值是有關(guān)一個(gè)問題的一些知識(shí)（ 經(jīng)驗(yàn)法則），該知識(shí)能讓您做出更好的決策。在搜索算法的上下文中，啟發(fā)式估值 有具體的含義：估算從特定節(jié)點(diǎn)到一個(gè)目標(biāo)的成本的一個(gè)函數(shù)。A* 可以利用啟發(fā)式估值來決定哪些節(jié)點(diǎn)是最應(yīng)該訪問的，從而避免不必要的計(jì)算。A* 嘗試避免訪問圖形中幾乎不通向最優(yōu)解決方案的節(jié)點(diǎn)，通?？捎帽确菃l(fā)式算法更少的內(nèi)存快速找到解決方案。

A* 確定最應(yīng)該訪問哪些節(jié)點(diǎn)的方式是為每個(gè)節(jié)點(diǎn)計(jì)算一個(gè)值（我們將其稱為 f 值），并根據(jù)該值對(duì) open 列表進(jìn)行排序。f 值是使用另外兩個(gè)值計(jì)算出來的，即節(jié)點(diǎn)的 g 值 和 h 值。一個(gè)節(jié)點(diǎn)的 g 值是從初始狀態(tài)到達(dá)一個(gè)節(jié)點(diǎn)所需的所有操作的總成本。從節(jié)點(diǎn)到目標(biāo)的估算成本是其 h 值。這一估算值是啟發(fā)式搜索中的啟發(fā)式估值。f 值最小的節(jié)點(diǎn)是最應(yīng)該訪問的節(jié)點(diǎn)。

圖 2 展示該搜索過程：

圖 2. 基于 f 值的 A* 搜索順序

在 圖 2 的示例中，前沿有三個(gè)節(jié)點(diǎn)。有兩個(gè)節(jié)點(diǎn)的 f 值是 5，一個(gè)節(jié)點(diǎn)的 f 值是 3。接下來展開 f 值最小的節(jié)點(diǎn)，該節(jié)點(diǎn)直接通往一個(gè)目標(biāo)。這樣一來 A* 就無需訪問其他兩個(gè)節(jié)點(diǎn)下的任何子樹，如圖 3 所示。這使得 A* 比廣度優(yōu)先搜索等算法要高效得多。

圖 3. A* 不必訪問 f 值較高的節(jié)點(diǎn)下的子樹

如果 A* 使用的啟發(fā)式估值是可接受的，那么 A* 僅訪問找到最優(yōu)解決方案所需的節(jié)點(diǎn)。為此 A* 很受歡迎。沒有其他算法能用可接受的啟發(fā)式估值，通過訪問比 A* 更少的節(jié)點(diǎn)保證找到一個(gè)最優(yōu)解決方案。要讓啟發(fā)式估算成為可接受的，它必須是一個(gè)下限值：一個(gè)小于或等于到達(dá)目標(biāo)的成本的值。如果啟發(fā)滿足另一個(gè)屬性，即一致性，那么將首次通過最優(yōu)路徑生成每個(gè)狀態(tài)，而且該算法可以更高效地處理重復(fù)節(jié)點(diǎn)。

與上一節(jié)的廣度優(yōu)先搜索一樣，A* 維護(hù)兩個(gè)數(shù)據(jù)結(jié)構(gòu)。已生成但尚未訪問的節(jié)點(diǎn)存儲(chǔ)在一個(gè) open 列表 中，而且訪問的所有標(biāo)準(zhǔn)節(jié)點(diǎn)都存儲(chǔ)在一個(gè) closed 列表 中。這些數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)以及使用它們的方式對(duì)性能有很大的影響。我們將在后面的一節(jié)中對(duì)此進(jìn)行詳細(xì)探討。清單 2 顯示 textbook A* 搜索的完整偽代碼。

清單 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) 

在清單 2 中，A* 從 open 列表中的初始節(jié)點(diǎn)入手。在每次循環(huán)迭代中，open 列表上的最佳節(jié)點(diǎn)被刪除。接下來，open 上 最佳節(jié)點(diǎn)的所有適用操作被應(yīng)用，生成所有可能的后繼節(jié)點(diǎn)。對(duì)于每個(gè)后繼節(jié)點(diǎn)，我們將通過檢查確認(rèn)它表示的狀態(tài)是否已被訪問。如果沒有，則將其添加到 open 列表。如果它已經(jīng)被訪問，則需要通過一個(gè)更好的路徑確定我們是否達(dá)到了這一狀態(tài)。如果是，則需要將該節(jié)點(diǎn)放在 open 列表上，并刪除次優(yōu)的節(jié)點(diǎn)。

我們可以使用有關(guān)要解決的問題的兩個(gè)假設(shè)簡(jiǎn)化這一段偽代碼：我們假設(shè)所有操作有相同的成本，而且我們有可接受的、一致的啟發(fā)式估值。因?yàn)閱l(fā)式估值 是一致的，且域中的所有操作具有相同的成本，那么我們永遠(yuǎn)無法通過一個(gè)更好的路徑重訪一個(gè)狀態(tài)。結(jié)果還表明，對(duì)于一些域，在 open 列表中放置重復(fù)節(jié)點(diǎn)比每次生成新節(jié)點(diǎn)時(shí)檢查是否有重復(fù)節(jié)點(diǎn)更高效。因此，我們可以通過將所有新后繼節(jié)點(diǎn)附加到 open 列表來簡(jiǎn)化實(shí)現(xiàn)，不管它們是否已經(jīng)被訪問。我們通過將 清單 2 中的最后四行組合為一行來簡(jiǎn)化偽代碼。我們?nèi)匀恍枰苊庋h(huán)，因此在展開一個(gè)節(jié)點(diǎn)之前，必須檢查是否有重復(fù)節(jié)點(diǎn)。我們可以省略掉 IMPROVE 函數(shù)的細(xì)節(jié)，因?yàn)樵诤?jiǎn)化版本中不再需要它。清單 3 顯示簡(jiǎn)化的偽代碼：

清單 3. A* 搜索的簡(jiǎn)化偽代碼

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) 

A* 的 Java textbook 實(shí)現(xiàn)

本節(jié)我們將介紹如何基于 清單 3 中簡(jiǎn)化的偽代碼完成 A* 的 Java textbook 實(shí)現(xiàn)。您會(huì)看到，這一實(shí)現(xiàn)無法解決 30GB 內(nèi)存限制下的一個(gè)標(biāo)準(zhǔn)啟發(fā)式搜索基準(zhǔn)。

我們希望我們的實(shí)現(xiàn)盡量大眾化，因此我們首先定義了一些接口來提取 A* 要解決的問題。我們想通過 A* 解決的任何問題都必須實(shí)現(xiàn) Domain接口。Domain 接口提供具有以下用途的方法：

• 查詢初始狀態(tài)
• 查詢一個(gè)狀態(tài)的適用操作
• 計(jì)算一個(gè)狀態(tài)的啟發(fā)式估值
• 生成后繼狀態(tài) 

清單 4 顯示了 Domain 接口的完整代碼：

清單 4. Domain 接口的 Java 源代碼

public interface Domain<T> { 
  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<T> apply (T state, int op); 
  public T copy(T state);   
} 

A* 搜索為搜索樹生成邊緣和節(jié)點(diǎn)對(duì)象，因此我們需要 Edge 和 Node 類。每個(gè)節(jié)點(diǎn)包含 4 個(gè)字段：節(jié)點(diǎn)表示的狀態(tài)、對(duì)父節(jié)點(diǎn)的引用，以及節(jié)點(diǎn)的 g 和 h 值。清單 5 顯示 Node 類的完整代碼：

#p#

清單 5. Node 類的 Java 源代碼

class Node<T> { 
  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; 
  } 
} 

每個(gè)邊緣有三個(gè)字段：邊緣的成本或權(quán)重、用于為邊緣生成后繼節(jié)點(diǎn)的操作，以及用于為邊緣生成父節(jié)點(diǎn)的操作。清單 6 顯示了 Edge 類的完整代碼：

清單 6. Edge 類的 Java 源代碼

public class Edge<T> { 
  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* 算法本身會(huì)實(shí)現(xiàn) SearchAlgorithm 接口，而且僅需要 Domain 和 Edge 接口。SearchAlgorithm 接口僅提供一個(gè)方法來執(zhí)行具有指定初始狀態(tài)的搜索。search() 方法返回 SearchResult 的一個(gè)實(shí)例。SearchResult 類提供搜索統(tǒng)計(jì)。SearchAlgorithm 接口的定義如清單 7 所示：

清單 7. SearchAlgorithm 接口的 Java 源代碼

public interface SearchAlgorithm<T> { 
  public SearchResult<T> search(T state);  
} 

用于 open 和 closed 列表的數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)重要的實(shí)現(xiàn)細(xì)節(jié)。我們將使用 Java 的 PriorityQueue 實(shí)現(xiàn) open 列表。PriorityQueue 是一個(gè)平衡的二進(jìn)制堆的實(shí)現(xiàn)，包含用于元素入列和出列的 O(log n) 時(shí)間、用于測(cè)試一個(gè)元素是否在隊(duì)列中的線性時(shí)間，以及用于訪問隊(duì)列頭的約束時(shí)間。二進(jìn)制堆是實(shí)現(xiàn) open 列表的一個(gè)流行數(shù)據(jù)結(jié)構(gòu)。稍后您會(huì)看到，對(duì)于一些域，可以使用一個(gè)名為桶優(yōu)先級(jí)隊(duì)列 的更高效的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn) open 列表。

我們必須實(shí)現(xiàn) Comparator 接口讓 PriorityQueue 合理地對(duì)節(jié)點(diǎn)進(jìn)行排序。對(duì)于 A* 算法，我們需要根據(jù) f 值對(duì)每個(gè)節(jié)點(diǎn)排序。在許多節(jié)點(diǎn)的 f 值相同的域中，一個(gè)簡(jiǎn)單的優(yōu)化是通過選擇 g 值較高的節(jié)點(diǎn)來打破平局。試著花點(diǎn)時(shí)間說服自己為何以這種方式打破平局能提高 A* 的性能（提示：h 是一個(gè)估算值；而 g 不是）。清單 8 包含完整的 Comparator 實(shí)現(xiàn)代碼：

清單 8. NodeComparator 類的 Java 源代碼

class NodeComparator implements Comparator<Node> { 
  public int compare(Node a, Node b) { 
    if (a.f == b.f) { 
      return b.g - a.g; 
    } 
    else { 
      return a.f - b.f; 
    } 
  }    
} 

我們需要實(shí)現(xiàn)的其他數(shù)據(jù)結(jié)構(gòu)是 closed 列表。對(duì)此的一個(gè)明顯的選擇是 Java 的 HashMap 類。HashMap 類是散列表的一個(gè)實(shí)現(xiàn)，只要我們提供一個(gè)好的散列函數(shù)，預(yù)期會(huì)有用于檢索和添加元素的恒定時(shí)間。我們必須重寫負(fù)責(zé)實(shí)現(xiàn)域狀態(tài)的類的 hashcode() 和 equals() 方法。我們將在下一節(jié)中探討該實(shí)現(xiàn)。

最后我們需要實(shí)現(xiàn) SearchAlgorithm 接口。為此，我們使用 清單 3 中的偽代碼實(shí)現(xiàn) search() 方法。清單 9 顯示了 A* search() 方法的完整代碼：

清單 9. A* search() 方法的 Java 源代碼

public SearchResult<T> search(T init) { 
  Node initNode = new Node(init, null, 0, 0 -1);    
  open.add(initNode); 
  while (!open.isEmpty() && path.isEmpty()) {  
    Node n = open.poll(); 
    if (closed.containsKey(n.state)) continue; 
    if (domain.isGoal(n.state)) { 
      for (Node p = n; p != null; p = p.parent) 
        path.add(p.state); 
      break; 
    } 
    closed.put(n.state, n); 
    for (int i = 0; i < domain.numActions(n.state); i++) { 
      int op = domain.nthAction(n.state, i); 
      if (op == n.pop) continue; 
      T successor = domain.copy(n.state); 
      Edge<T> edge = domain.apply(successor, op);      
      Node node = new Node(successor, n, edge.cost, edge.pop); 
      open.add(node); 
    } 
  } 
  return new SearchResult<T>(path, expanded, generated); 
} 

要評(píng)估我們的 A* 實(shí)現(xiàn)，需要對(duì)一個(gè)問題運(yùn)行該實(shí)現(xiàn)。在下一節(jié)中，我們將描述一個(gè)用于評(píng)估啟發(fā)式搜索算法的流行域。該域中的所有操作都具有相同的成本，而且我們使用的啟發(fā)式估值是可接受的，因此我們的簡(jiǎn)化實(shí)現(xiàn)是足夠的。

15 puzzle 基準(zhǔn)

本文中，我們側(cè)重于一個(gè)名為 15 puzzle 的 toy 域。這個(gè)簡(jiǎn)單的域有易于理解的屬性，是評(píng)估啟發(fā)式搜索算法的一個(gè) 標(biāo)準(zhǔn)基準(zhǔn)。（有人將這些拼圖稱為 AI 研究的 “果蠅”。）15 puzzle 是一種滑塊拼圖，在 4×4 網(wǎng)格上排列 15 個(gè)滑塊。一個(gè)滑塊有 16 個(gè)位置可供選擇，總有一個(gè)位置是空的。與空白位置相鄰的滑塊可從一個(gè)位置滑動(dòng) 到另一個(gè)位置。其目的是滑動(dòng)滑塊，直至達(dá)到拼圖的目標(biāo)布局。圖 4 顯示了隨機(jī)布局下的滑塊拼圖：

圖 4. 15 puzzle 的隨機(jī)布局

#p#

圖 5 顯示了目標(biāo)布局下的滑塊：

圖 5. 15 puzzle 的目標(biāo)布局

作為一個(gè)啟發(fā)式搜索基準(zhǔn)，我們希望通過盡量少的移動(dòng)從某個(gè)初始布局開始找到該拼圖的目標(biāo)布局。

我們將為該域使用的啟發(fā)式算法叫作曼哈坦距離 算法。一個(gè)滑塊的曼哈坦距離是滑塊到達(dá)目標(biāo)位置所需做出的垂直和水平移動(dòng)數(shù)量。要 計(jì)算一個(gè)狀態(tài)的啟發(fā)式估值，我們需要算出拼圖中所有滑塊的曼哈坦距離的總和，忽略空白位置。對(duì)于任何狀態(tài)，所有這些距離之和必須是達(dá)到拼圖目標(biāo)狀態(tài)所需成 本的下限值，因?yàn)槟肋h(yuǎn)無法通過減少移動(dòng)量將滑塊移動(dòng)到每個(gè)目標(biāo)布局。

一開始似乎不太直觀，但我們可以用圖形建模 15 puzzle，將滑塊的每個(gè)可能布局表示為節(jié)點(diǎn)。如果有一個(gè)操作將一個(gè)布局轉(zhuǎn)化為另一個(gè)布局，一個(gè)邊緣連接兩個(gè)節(jié)點(diǎn)。在該域中，一個(gè)操作將滑塊滑到空白區(qū)域。圖 4 展示了這一搜索圖：

圖 6. 15 puzzle 的狀態(tài)空間搜索圖

有 16! 種在網(wǎng)格上排列 15 個(gè)滑塊的可能方式，不過實(shí)際上 “只有” 16!/2 = 10,461,394,944,000 種 15 puzzle 的可達(dá)布局或狀態(tài)。這是因?yàn)槠磮D的物理約束讓我們剛好達(dá)到所有可能布局的一半。為了了解該狀態(tài)空間的大小，假設(shè)我們可以用一個(gè)字節(jié)表示一種狀態(tài)（這是不可 能的）。為了存儲(chǔ)整個(gè)狀態(tài)空間，我們需要超過 10TB 的內(nèi)存。這將遠(yuǎn)遠(yuǎn)超過最現(xiàn)代的計(jì)算機(jī)的內(nèi)存限制。我們將展示啟發(fā)式搜索如何在僅訪問一小部分狀態(tài)空間的同時(shí)以最佳方式解決這個(gè)難題。

運(yùn)行實(shí)驗(yàn)

我們的實(shí)驗(yàn)使用 15 puzzle 的一組著名起始布局，叫 Korf 100 集合。這一集合得名于 Richard E. Korf，他發(fā)布了首批結(jié)果，表明可以使用 A* 的一個(gè)迭代加深 變體，即 IDA*，解決隨機(jī)的 15 puzzle 布局。由于這些結(jié)果被發(fā)布，Korf 在其實(shí)驗(yàn)中使用的 100 個(gè)隨機(jī)實(shí)例在無數(shù)隨后的啟發(fā)式搜索實(shí)驗(yàn)中得到重用。我們還優(yōu)化了我們的實(shí)現(xiàn)，因而無需再使用迭代加深技術(shù)。

我們一次解決一個(gè)起始布局。每個(gè)起始布局都存儲(chǔ)在一個(gè)獨(dú)立的普通文本文件中。文件的位置在啟動(dòng)實(shí)驗(yàn)的命令行參數(shù)中指定。我們需要一個(gè) Java 程序入口點(diǎn)來處理命令行參數(shù)，生成問題實(shí)例，并運(yùn)行 A* 搜索。我們將這個(gè)入口點(diǎn)稱為 TileSolver 類。

在每次運(yùn)行結(jié)束時(shí)會(huì)將有關(guān)搜索性能的統(tǒng)計(jì)數(shù)據(jù)打印為標(biāo)準(zhǔn)輸出。我們最感興趣的統(tǒng)計(jì)數(shù)據(jù)是掛鐘時(shí)間（wall clock time）。我們將所有運(yùn)行的掛鐘時(shí)間加起來，得出該基準(zhǔn)測(cè)試的總運(yùn)行時(shí)間。

本文 源代碼 包含自動(dòng)完成實(shí)驗(yàn)的 Ant 任務(wù)。您可以使用以下代碼運(yùn)行整個(gè)實(shí)驗(yàn)：

ant TileSolver.korf100 -Dalgorithm="efficient" 

可以為 algorithm 指定 efficient 或 textbook。

ant TileSolver -Dinstance="12" -Dalgorithm="textbook" 

而且我們提供一個(gè) Ant 目標(biāo)來運(yùn)行基準(zhǔn)測(cè)試子集，其中不包括三個(gè)最難的實(shí)例：

ant TileSolver.korf97 -Dalgorithm="textbook" 

很可能您的計(jì)算機(jī)沒有足夠的內(nèi)存來使用 textbook 實(shí)現(xiàn)完成整個(gè)實(shí)驗(yàn)。為了避免存儲(chǔ)交換，您應(yīng)當(dāng)謹(jǐn)慎地限制 Java 進(jìn)程可用的內(nèi)存量。如果您要在 Linux 上運(yùn)行該實(shí)驗(yàn)，可以使用像 ulimit 這樣的 shell 命令來設(shè)置活動(dòng) shell 的內(nèi)存限制。

一開始沒有成功

表 1 顯示我們使用的所有技術(shù)的結(jié)果。Textbook A* 實(shí)現(xiàn)的結(jié)果在第一行。（在后面的章節(jié)中我們描述了 Packed states 和 HPPC 及其相關(guān)結(jié)果。）

表 1. 解決 97 個(gè) Korf 100 15 puzzle 基準(zhǔn)測(cè)試實(shí)例的三個(gè) A* 變體的結(jié)果

textbook 實(shí)現(xiàn)無法解決所有測(cè)試實(shí)例。我們未能解決三個(gè)最難的實(shí)例，而且對(duì)于我們可以解決的實(shí)例，我們花了超過 1,800 秒的時(shí)間。這些結(jié)果不算很好，因?yàn)?C/C++ 中最好的實(shí)現(xiàn)可在不到 600 秒的時(shí)間內(nèi)解決 100 個(gè)實(shí)例。

由于內(nèi)存約束我們未能解決最難的那三個(gè)實(shí)例。在每一次搜索迭代中，從 open 列表中刪除一個(gè)節(jié)點(diǎn)并展開它通常會(huì)導(dǎo)致生成更多的節(jié)點(diǎn)。隨著所生成節(jié)點(diǎn)數(shù)量的增加，在 open 列表中存儲(chǔ)它們所需的內(nèi)存量也在增加。但是，這一內(nèi)存需求不是 Java 實(shí)現(xiàn)所特有的；同等的 C/C++ 實(shí)現(xiàn)也會(huì)失敗。

Burns 等人在其論文中表明，A* 搜索的一個(gè)高效 C/C++ 實(shí)現(xiàn)可以用不到 30GB 的內(nèi)存解決該基準(zhǔn)測(cè)試，因此我們還沒打算放棄 Java A* 實(shí)現(xiàn)。我們還可以應(yīng)用后續(xù)章節(jié)中討論的其他技術(shù)，更高效地使用內(nèi)存。最終得出一個(gè)能夠快速解決整個(gè)基準(zhǔn)測(cè)試的高效的 A* Java 實(shí)現(xiàn)。

包裝狀態(tài)

在使用像 VisualVM 這樣的探查器檢查 A* 搜索的內(nèi)存使用情況時(shí)，我們看到所有內(nèi)存都被 Node 類占用，更直接地說由 TileState 類占用。為了降低內(nèi)存使用量，我們需要重訪這些類的實(shí)現(xiàn)。

每個(gè)滑塊狀態(tài)必須存儲(chǔ)所有 15 個(gè)滑塊的位置。為此我們將每個(gè)滑塊的位置存儲(chǔ)在一個(gè)包含 15 個(gè)整數(shù)的數(shù)組中。我們可以更簡(jiǎn)明地表示這些位置，將它們包裝成一個(gè) 64 位的整數(shù)（在 Java 中是 long）。當(dāng)我們需要在 open 列表中存儲(chǔ)一個(gè)節(jié)點(diǎn)時(shí)，可以僅存儲(chǔ)狀態(tài)的包裝表示。這么做會(huì)為每個(gè)節(jié)點(diǎn)節(jié)省 52 個(gè)字節(jié)。要解決基準(zhǔn)測(cè)試中最難的實(shí)例，需要存儲(chǔ)大約 5.33 億個(gè)節(jié)點(diǎn)。通過包裝狀態(tài)表示，我們可以節(jié)省 25GB 的內(nèi)存！

為了維護(hù)我們的實(shí)現(xiàn)的一般性，我們需要擴(kuò)展 SearchDomain 接口，使用包裝和拆裝狀態(tài)的方法。在 open 列表上存儲(chǔ)一個(gè)節(jié)點(diǎn)之前，我們將生成狀態(tài)的一個(gè)包裝表示，并將該包裝表示存儲(chǔ)在 Node 類（而非狀態(tài)指針）中。當(dāng)我們需要生成一個(gè)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)時(shí)，只需拆裝狀態(tài)。清單 10 顯示了 pack() 方法的實(shí)現(xiàn)：

#p#

清單 10. 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; 
} 

清單 11 顯示了 unpack() 方法的實(shí)現(xiàn)：

清單 11. 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]; 
  } 
} 

由于包裝表示是狀態(tài)的一種規(guī)范形式，我們可以將包裝表示存儲(chǔ)在 closed 列表中。我們無法將基元存儲(chǔ)在 HashMap 類中。需要將它們包裝在Long 類的一個(gè)實(shí)例中。

表 1 中的第二行顯示使用包裝狀態(tài)表示運(yùn)行實(shí)驗(yàn)的結(jié)果。通過使用包裝狀態(tài)表示，我們將內(nèi)存使用量減少了 55%，并縮短了運(yùn)行時(shí)間，但我們?nèi)匀粺o法解決整個(gè)基準(zhǔn)測(cè)試。

Java 集合框架的問題

如果您認(rèn)為將每個(gè)包裝狀態(tài)表示包裝在一個(gè) Long 實(shí)例中似乎需要很大開銷，那么您說得沒錯(cuò)。它浪費(fèi)內(nèi)存，而且可能導(dǎo)致過度的垃圾收集。JDK 1.5 增加了對(duì) autoboxing 的支持，autoboxing 會(huì)自動(dòng)轉(zhuǎn)換其對(duì)象表示的基元值（long 到 Long），反之亦然。對(duì)于大型集合，這些轉(zhuǎn)換可能會(huì)降低內(nèi)存和 CPU 性能。

JDK 1.5 還引入了 Java 泛型：一個(gè)通常相對(duì)于 C++ 模板的特性。Burns 等人表明，C++ 模板在實(shí)施啟發(fā)式搜索時(shí)提供了巨大的性能優(yōu)勢(shì)。泛型不提供這種優(yōu)勢(shì)。泛型是使用 type-erasure 實(shí)現(xiàn)的，這會(huì)在編譯時(shí)刪除（消除）所有類型信息。因此，必須在運(yùn)行時(shí)檢查類型信息，對(duì)于大型集合來說這會(huì)導(dǎo)致性能問題。

HashMap 類的實(shí)現(xiàn)揭露出一些其他內(nèi)存開銷。HashMap 存儲(chǔ)包含內(nèi)部 HashMap$Entry 類實(shí)例的一個(gè)數(shù)組。每當(dāng)我們將一個(gè)元素添加到 HashMap 時(shí)，都會(huì)有一個(gè)新條目被創(chuàng)建并添加到數(shù)組。該條目類的實(shí)現(xiàn)通常包含三個(gè)對(duì)象引用和一個(gè) 32 位整數(shù)的引用，每個(gè)條目總共 32 個(gè)字節(jié)。由于 closed 列表中有 5.33 億個(gè)節(jié)點(diǎn)，我們將有超過 15GB 的內(nèi)存開銷。

接下來，我們將介紹 HashMap 類的一個(gè)替代方法，該方法支持我們通過直接存儲(chǔ)基元進(jìn)一步減少內(nèi)存使用。

高性能的原生集合

由于我們現(xiàn)在僅在 closed 列表中存儲(chǔ)基元，我們可以利用高性能的原生集合（High Performance Primitive Collections，HPPC）。HPPC 是一個(gè)替代的集合框架，支持您直接存儲(chǔ)基元值，而沒有 JCF 帶來的所有那些開銷。與 Java 泛型相比，HPPC 使用了一種類似 C++ 模板的技術(shù)，在編譯時(shí)生成每個(gè)集合類和 Java 基元類型的獨(dú)立實(shí)現(xiàn)。這樣一來，在將基元值存儲(chǔ)到一個(gè)集合中時(shí)就無需使用 Long 和Integer 這樣的類包裝基元值。其另外一個(gè)作用是可以避免對(duì)于 JCF 來說必需的大量強(qiáng)制轉(zhuǎn)換。

另外還有用于存儲(chǔ)基元值的其他 JCF 替代方法。Apache Commons Primitive Collections 和 fastutils 就是兩個(gè)不錯(cuò)的示例。不過，我們認(rèn)為 HPPC 的設(shè)計(jì)在實(shí)現(xiàn)高性能算法時(shí)有一個(gè)顯著的優(yōu)勢(shì)：它為每個(gè)集合類公開內(nèi)部數(shù)據(jù)存儲(chǔ)。直接訪問這一存儲(chǔ)可以實(shí)現(xiàn)許多優(yōu)化。例如，如果我們想將 open 或 closed 列表存儲(chǔ)在磁盤上，直接訪問底層數(shù)據(jù)數(shù)組比通過一個(gè)迭代器間接訪問數(shù)據(jù)更有效。

我們可以修改 A* 實(shí)現(xiàn)，對(duì) closed 列表使用 LongOpenHashSet 類的一個(gè)實(shí)例。我們需要做的更改相當(dāng)簡(jiǎn)單。我們不再需要重寫 state class 的hashcode 和 equals 方法，因?yàn)槲覀儍H需存儲(chǔ)基元值。closed 列表是一個(gè)集合（它不包含重復(fù)元素），因此我們僅需要存儲(chǔ)值，而無需存儲(chǔ)鍵/值對(duì)。

表 1 中的第三行顯示了用 HPPC 取代 JCF 后運(yùn)行實(shí)驗(yàn)的結(jié)果。憑借 HPPC，我們將內(nèi)存使用量減少了 27%，將運(yùn)行時(shí)間減少了 33%。

既然內(nèi)存總共減少了 82%，我們就可以在內(nèi)存約束內(nèi)解決整個(gè)基準(zhǔn)測(cè)試了。結(jié)果顯示于表 2 中的第一行：

表 2. 解決全部 100 個(gè) Korf 100 基準(zhǔn)測(cè)試實(shí)例的三個(gè) A* 變體的結(jié)果

通過 HPPC，我們可以用 30GB 內(nèi)存解決全部 100 個(gè)實(shí)例，但所用時(shí)間超過 1,800 秒。表 2 中的其他結(jié)果反映了我們通過改進(jìn)其他重要數(shù)據(jù)結(jié)構(gòu)加速實(shí)現(xiàn)的方式：open 列表。

PriorityQueue 的問題

每次我們將一個(gè)元素添加到 open 列表時(shí)，都需要再次排隊(duì)。PriorityQueue 有 O(log(n)) 入列和出列操作時(shí)間。涉及到排序時(shí)，PriorityQueue 是高效的，但顯然是不自由的，特別在 n 值較大時(shí)。記得對(duì)于最難的問題實(shí)例，我們添加了超過 5 億個(gè)節(jié)點(diǎn)到 open 列表。此外，由于我們的基準(zhǔn)測(cè)試問題中的所有操作都具有相同的成本，可能的 f 值的范圍較小。因此使用 PriorityQueue 的優(yōu)勢(shì)與開銷相比可能得不償失。

另一個(gè)替代方法是使用基于桶的優(yōu)先級(jí)隊(duì)列。假設(shè)我們域中的操作成本在一個(gè)狹窄的值域內(nèi)，我們可以定義一個(gè)固定的存儲(chǔ)桶范圍：每個(gè) f 值一個(gè)存儲(chǔ)桶。當(dāng)我們生成一個(gè)節(jié)點(diǎn)時(shí)，只需將它放在與 f 值對(duì)應(yīng)的存儲(chǔ)桶中。當(dāng)我們需要訪問隊(duì)列頭時(shí)，可以首先從 f 值最小的存儲(chǔ)桶看起，直至我們找到一個(gè)節(jié)點(diǎn)。這種數(shù)據(jù)結(jié)構(gòu)叫作 1 級(jí)桶優(yōu)先級(jí)隊(duì)列，它支持恒定入列和出列操作。圖 7 展示了這一數(shù)據(jù)結(jié)構(gòu)：

圖 7. 1 級(jí)桶優(yōu)先級(jí)隊(duì)列

精明的讀者會(huì)注意到，如果我們實(shí)現(xiàn)這里描述的 1 級(jí)桶優(yōu)先級(jí)隊(duì)列，就失去了使用 g 值打破節(jié)點(diǎn)間關(guān)系的能力。您之前應(yīng)當(dāng)已經(jīng)意識(shí)到，以這種方式打破關(guān)系是一種值得的優(yōu)化。為了維持這一優(yōu)化，我們可以實(shí)現(xiàn)一個(gè)嵌套 桶優(yōu)先級(jí)隊(duì)列。1 級(jí)存儲(chǔ)桶用于表示 f 值的范圍，嵌套級(jí)別用于表示 g 值的范圍。圖 8 展示了這一數(shù)據(jù)結(jié)構(gòu)：

圖 8. 嵌套桶優(yōu)先級(jí)隊(duì)列

現(xiàn)在我們可以更新我們的 A* 實(shí)現(xiàn)，為 open 列表使用一個(gè)嵌套桶優(yōu)先級(jí)隊(duì)列。嵌套桶優(yōu)先級(jí)隊(duì)列的完整實(shí)現(xiàn)可在本文源代碼中包含的 BucketHeap.java 文件中找到（參見 下載 部分）。

表 2 的第二行顯示使用嵌套桶優(yōu)先級(jí)隊(duì)列運(yùn)行實(shí)驗(yàn)的結(jié)果。通過使用一個(gè)嵌套桶優(yōu)先級(jí)隊(duì)列，而非 PriorityQueue，我們將運(yùn)行時(shí)間縮短了將近 58%，所用時(shí)間是 1,000 多秒。我們可以再做一件事來縮短運(yùn)行時(shí)間。

#p#

避免垃圾收集

垃圾收集常被視為 Java 中的一個(gè)瓶頸。有許多關(guān)于 JVM 中垃圾收集調(diào)優(yōu)的優(yōu)秀文章可應(yīng)用于這里，因此我們不會(huì)詳細(xì)討論該主題。

A* 通常生成許多短暫的狀態(tài)和邊緣對(duì)象并招致大量昂貴的垃圾收集。通過重用對(duì)象，我們可以減少所需的垃圾收集量。為此我們可以做一些簡(jiǎn)單的更改。在 A* 搜索循環(huán)的每一次迭代中，我們分配一個(gè)新邊緣和一個(gè)新狀態(tài)（對(duì)于最難的問題是 5.33 億個(gè)節(jié)點(diǎn)）。與其每次分配新對(duì)象，我們可以在所有循環(huán)迭代中重用相同的狀態(tài)和邊緣對(duì)象。

為了擁有可重用的邊緣和狀態(tài)對(duì)象，我們需要修改 Domain 接口。 與其讓 apply() 方法返回 Edge 的一個(gè)實(shí)例，我們需要提供自己的實(shí)例，該實(shí)例通過調(diào)用 apply() 加以修改。對(duì) edge 的更改不是遞增的，因此在將其傳遞給 apply() 之前，我們無需擔(dān)心哪些值存儲(chǔ)在 edge 中。不過，apply() 對(duì) state 對(duì)象所做的更改是 遞增的。為了合理生成所有可能的后繼狀態(tài)，而無需復(fù)制狀態(tài)，我們需要一種撤銷所做更改的方式。為此，我們必須擴(kuò)展 Domain 接口，得到一個(gè) undo() 方法。清單 12 顯示 Domain 接口更改：

清單 12. 更新的 Domain 接口

public interface Domain<T> { 
  ... 
   public void apply(T state, Edge<T> edge, int op); 
   public void undo(T state, Edge<T> edge); 
  ...  
} 

表 2 中的第三行顯示最終實(shí)驗(yàn)的結(jié)果。通過循環(huán)利用我們的狀態(tài)和邊緣對(duì)象，我們可以避免昂貴的垃圾收集，并將運(yùn)行時(shí)間縮短超過 15%。利用我們高效的 A* Java 實(shí)現(xiàn)，我們現(xiàn)在可以僅用 30GB 的內(nèi)存在 925 秒內(nèi)解決整個(gè)基準(zhǔn)測(cè)試。鑒于最好的 C/C++ 實(shí)現(xiàn)需要 27GB 內(nèi)存且花費(fèi) 540 秒，這個(gè)結(jié)果已經(jīng)很好了。我們的 Java 實(shí)現(xiàn)僅比 C/C++ 實(shí)現(xiàn)慢 1.7 倍，且需要大約同樣的內(nèi)存量。

結(jié)束語

在本文中，我們向您介紹了啟發(fā)式搜索。我們提出了 A* 算法，并闡述了 Java textbook 實(shí)現(xiàn)。我們指出該實(shí)現(xiàn)存在性能問題，無法在合理的時(shí)間或內(nèi)存約束內(nèi)解決一個(gè)標(biāo)準(zhǔn)的基準(zhǔn)測(cè)試問題。我們利用 HPPC 和一些可降低內(nèi)存使用和避免昂貴的垃圾收集的技術(shù)解決了這些問題。我們改進(jìn)的實(shí)現(xiàn)能夠在適當(dāng)?shù)臅r(shí)間和內(nèi)存約束內(nèi)解決基準(zhǔn)測(cè)試，這證明了 Java 是實(shí)現(xiàn)啟發(fā)式搜索算法的一個(gè)不錯(cuò)選擇。此外，我們?cè)诒疚奶峁┑募夹g(shù)也可應(yīng)用于許多實(shí)際 Java 應(yīng)用程序。例如，在某些情況下，使用 HPPC 可以立即提高存儲(chǔ)大量基元值的任何 Java 應(yīng)用程序的性能。

下載

原文鏈接：http://www.ibm.com/developerworks/cn/java/j-ai-search/index.html

譯文鏈接：http://blog.jobbole.com/48554/