畢智超

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

關鍵詞：數(shù)碼迷題；啟發(fā)式搜索；A*算法；定理化判斷

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

一、引言

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

二、定理化判定可解性

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

三、搜索算法的分析比較

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

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

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

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

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

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

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

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

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

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

3、若Open表不為空，循環(huán)執(zhí)行以下操作：

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

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

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

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

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

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

4、回溯得解。

五、結束語

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

參考文獻：

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

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

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