數碼迷題求解算法的比較及A*算法的簡單介紹

畢智超

摘 要：數碼謎題源于一古老的智力游戲，是人工智能領域中的經典問題。本文著眼于8數碼問題求解的具體實現。分析了數碼迷題求解的搜索策略。對三種搜索算法進行了比較權衡，并對經典啟發式搜索算法A*算法進行了簡單介紹，介紹了該算法框架下的啟發函數及Open表結構。

關鍵詞：數碼迷題；啟發式搜索；A*算法；定理化判斷

中圖分類號：O14 文獻標識碼：A 文章編號：1009-0118（2011）-03-0018-01

一、引言

8數碼迷題又稱重排九宮，問題描述如下：用數字1~8標注的棋子擺放在一個3×3共9個格子的棋盤上，空出一個格子使棋子能在盤內水平滑動，8個符號在棋盤上的排列稱為8數碼的狀態，游戲要求給定一個初始的狀態和一個終止狀態，且每次只能移動一個棋子，求從任一初始棋局變化到另一目標棋局是否有解，以及有解時的解法。

二、定理化判定可解性

按從左往右，從上到下的順序將棋局狀態表示為一個數列P=a1a2a3a4a5a6a7a8，ai為1,2…8八個數碼中的一個，P是1,2…8的一個排列，稱P是該棋局的狀態數列。在序列P中對iaj，則稱aj出現了一個逆序，元素aj的逆序數記為R(aj)。于是序列P的逆序數記為R(P)，定義為除元素0外所有元素的逆序個數之和。序列P的元素存放在數組S[1∽n×n]中。

三、搜索算法的分析比較

（一）三種搜索算法的數據結構分析。首先簡單介紹下Open表和Closed的動態數據結構，前者記錄當前未考察的結點，后者記錄考察過的結點。擴展所得子結點按其估值的大小插入Open表中合適的位置，每次從中選出估值最小的加以擴展。每個結點都保留父結點的信息，這保證了搜索完畢后，能通過Closed表返回完整的搜索路徑。

一般圖的搜索算法中，提高效率的關鍵在于Open表中結點的排列方式，若每次排在表首的結點都最終搜索到解的路徑上，則算法不需擴展任何多余的結點就可快速結束搜索。所以排列方式成為研究搜索算法的焦點，并由此形成了多種搜索策略。

（二）三種搜索算法的比較及適用范圍。對于，實際問題，深度優先搜索一般不能保證找到最優解，雖然通過與回溯結合可以找到最優解，但是在最壞的情況下，搜索空間等同于窮舉。而且對于許多問題，其狀態空間的搜索樹的深度可能無限深，或者可能至少要比某個可接受的解答序列的已知深度上限還要深。為了避免考慮太長的路徑，往往給出一個結點擴展的最大深度，稱深度界限。任何結點如果達到了深度界限，那么都將把它們作為后繼結點處理。即便應用了深度界限的規定，由于一個有解的問題樹可能含有無窮分支，深度優先搜索如果誤入無窮分支，或解出現在深度界限之外，則不可能找到目標結點。所以，深度優先搜索策略是不完備的。另外，應用此策略得到的解不一定是最佳解，如果深度限制過小的話，甚至得不到解。因此這里就有了一個如何定義深度的問題，太小得不到結果，太大就很容易引起“結點爆炸”。

三種搜索算法運用于八數碼問題的求解時，對于深度優先搜索有時候會得不到解答，而且具有不確定的時間效率；對于寬度優先搜索，雖然得到的都是最優解，但是由于生成了大量的結點，因此每次生成的結點要判斷是否為全新結點都要對已經生成的結點進行遍歷和比較，不但損失了空間效率，甚至還會影響時間效率；對于A*算法，理論上是能夠擴展最少的結點，最快的找到解答，但是如果評估函數選的不好，也會影響效率。因此對啟發式搜索的啟發函數的研究就顯得特別有意義了。

四、啟發式搜索策略A*算法的簡單介紹

（一）算法估價函數簡介。數碼重排最簡單的啟發函數h(n)就是計算當前狀態與目標狀態相比位置不符的數碼數目。該方法雖然計算量較小，但其結點擴展量大，搜索效率低。

所以將g(n)定義為從初始結點到n結點移動的數碼數目，即搜索樹中n結點的深度；h(n)定義為在n結點狀態下各數碼到達目標狀態的距離之和，即h(n)=∑(|xi1-xi2|+|yi1-yi2|)，xi1、xi2分別為數碼i在當前狀態和目標狀態下的橫坐標，同理y為縱坐標。

（二）算法的實現框架。A*算法是指滿足條件h(n)≤h*(n)的啟發式搜索，h*(n)為從n結點到目標結點的實際最優代價，多數情況下h*(n)無法計算，但要判定h(n)是否大于h*(n)是可能的。求解數碼的A*算法框架流程如下：

1、判斷問題可解性；若無解，則退出。

2、初始化，將初始結點放入Open表，令Closed表為空。

3、若Open表不為空，循環執行以下操作：

（1）選取Open表的表頭作為當前結點；若該結點是目標結點，跳轉至Step4。

（2）將當前結點從Open表中移除，放入Closed表中。

（3）求出當前結點的所有子結點。

（4）計算子結點的估價值。

（5）如果子結點不在Open表和Closed表中，將其插入到Open表。

（6）按照結點的估價值，以遞增順序重排Open表。

4、回溯得解。

五、結束語

本文對于問題首先直接應用定理進行可解化判定，其次對深度、廣度優先搜索與A*算法搜索進行了分析比較，得出三者的性能特點。最后著重于介紹啟發式搜索策略A*算法，為進一步研究奠定下堅實的基礎。由于筆者的能力有限，文章中有敘述不透徹的地方望各位讀者海涵，期待通過更加深入的研究和實驗能得到更好的掌握。

參考文獻：

[1]許精明.智能搜索中啟發函數的選擇及啟發能力分析[J].昆明理工大學學報,2007,32(5):31-34.

[2]黃沛杰.重排九宮問題的分析與實現[J].現代計算機,2003,(12).

[3]陳世福,陳兆乾.人工智能與知識工程[M].南京大學出版社,1997.