數(shù)碼迷題求解算法的比較及A*算法的簡(jiǎn)單介紹

畢智超

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

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

中圖分類號(hào)：O14 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-0118（2011）-03-0018-01

一、引言

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

二、定理化判定可解性

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

三、搜索算法的分析比較

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

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

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

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

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

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

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

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

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

2、初始化，將初始結(jié)點(diǎn)放入Open表，令Closed表為空。

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

（1）選取Open表的表頭作為當(dāng)前結(jié)點(diǎn)；若該結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，跳轉(zhuǎn)至Step4。

（2）將當(dāng)前結(jié)點(diǎn)從Open表中移除，放入Closed表中。

（3）求出當(dāng)前結(jié)點(diǎn)的所有子結(jié)點(diǎn)。

（4）計(jì)算子結(jié)點(diǎn)的估價(jià)值。

（5）如果子結(jié)點(diǎn)不在Open表和Closed表中，將其插入到Open表。

（6）按照結(jié)點(diǎn)的估價(jià)值，以遞增順序重排Open表。

4、回溯得解。

五、結(jié)束語

本文對(duì)于問題首先直接應(yīng)用定理進(jìn)行可解化判定，其次對(duì)深度、廣度優(yōu)先搜索與A*算法搜索進(jìn)行了分析比較，得出三者的性能特點(diǎn)。最后著重于介紹啟發(fā)式搜索策略A*算法，為進(jìn)一步研究奠定下堅(jiān)實(shí)的基礎(chǔ)。由于筆者的能力有限，文章中有敘述不透徹的地方望各位讀者海涵，期待通過更加深入的研究和實(shí)驗(yàn)?zāi)艿玫礁玫恼莆铡?/p>

參考文獻(xiàn)：

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

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

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