八數(shù)碼問題解法效率比較及改進(jìn)研究 

付宏杰王雪瑩周健周孫靜朱珠張俊余

摘要：八數(shù)碼問題是人工智能中的一個(gè)典型問題，目前解決八數(shù)碼問題的搜索求解策略主要有深度優(yōu)先搜索、寬度優(yōu)先搜索、啟發(fā)式A*算法。對(duì)這些算法進(jìn)行研究，重點(diǎn)對(duì)A*算法進(jìn)行適當(dāng)改進(jìn)，使用曼哈頓距離對(duì)估價(jià)函數(shù)進(jìn)行優(yōu)化。對(duì)使用這些算法解決八數(shù)碼問題的效率進(jìn)行比較，從步數(shù)、時(shí)間、結(jié)點(diǎn)數(shù)、外顯率等各參數(shù)，通過具體的實(shí)驗(yàn)數(shù)據(jù)分析，進(jìn)一步驗(yàn)證各算法的特性。

關(guān)鍵詞：八數(shù)碼；深度優(yōu)先搜索；寬度優(yōu)先搜索；A*算法；曼哈頓距離

DOIDOI：10.11907/rjdk.161867

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2016）009004105

基金項(xiàng)目基金項(xiàng)目：

作者簡(jiǎn)介作者簡(jiǎn)介：付宏杰（1973-），女，吉林公主嶺人，博士，吉林工程技術(shù)師范學(xué)院信息工程學(xué)院副教授，研究方向?yàn)槿斯ぶ悄?、群體智能、機(jī)器學(xué)習(xí)。

1問題描述

八數(shù)碼問題就是在一個(gè)大小為3×3的九宮格上，放置8塊編號(hào)為1～8的木塊，九宮格中有一個(gè)空格，周圍（上下左右）的木塊可以和空格交換位置。對(duì)于問題，給定一個(gè)初始狀態(tài)（如圖1（a）初始狀態(tài)），目標(biāo)狀態(tài)（如圖1（b）目標(biāo)狀態(tài)）是期望達(dá)到1～8順序排列的序列，并且空格在右下角，問題的實(shí)質(zhì)就是尋找一個(gè)合法的移動(dòng)序列。

2問題分析和模型表示

2.1模型建立

對(duì)于棋格，每個(gè)位置給定一個(gè)編號(hào)，從左上角開始順序編號(hào)（見圖2），對(duì)于任意的狀態(tài)，記為p = s[0]s[1]s[2]s[3]s[4]s[5]s[6]s[7]s[8]，圖1初始狀態(tài)中的狀態(tài)可以表示為 p=2 8 3 1 6 4 7 0 5，圖2目標(biāo)狀態(tài)中的狀態(tài)可以表示為 p = 1 2 3 4 5 6 7 8 0。

2.2分析解的存在性

不是每一個(gè)給定的初始狀態(tài)都存在解，在分析之前，引入線性代數(shù)逆序和逆序數(shù)的概念：在一個(gè)排列中，如果一對(duì)數(shù)的前后位置和大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就成為一個(gè)逆序；排列中逆序的總數(shù)就成為這個(gè)排列的逆序數(shù)。例如，排列p=2 8 3 1 6 4 7 0 5的逆序數(shù)為1+6+1+0+2+0+1=11（不可解）。

使用線性代數(shù)理論可以論證，對(duì)于任意目標(biāo)狀態(tài)，只有初始狀態(tài)的逆序數(shù)和目標(biāo)狀態(tài)的逆序數(shù)的奇偶性相同才有解（逆序數(shù)計(jì)算不包括0的逆序數(shù)）。例如p=1 2 3 4 5 6 7 0 8的逆序數(shù)為0，與p的逆序數(shù)奇偶性相同，因此是可解狀態(tài)。

3搜索策略

搜索算法本質(zhì)上是一棵將初始節(jié)點(diǎn)作為根節(jié)點(diǎn)的四叉樹。從初始節(jié)點(diǎn)開始，以空白格向4個(gè)方向的移動(dòng)作為分支。求解的過程就是尋找一條從根節(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑的過程。

為了方便論述，取目標(biāo)狀態(tài)為：p=1、2、3、4、5、6、7、8、0，本文用上、右、下、左分別表示空格的向上、向右、向下、向左4種操作。

3.1深度優(yōu)先搜索算法（Depth-First-Search）

深度優(yōu)先搜索策略是擴(kuò)展當(dāng)前結(jié)點(diǎn)，生成的子節(jié)點(diǎn)總是置于擴(kuò)展棧的前端，這樣搜索向縱深方向發(fā)展。

3.1.1算法策略

①將起始結(jié)點(diǎn)S加入棧中，如果此結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，則得到解；②如果棧為空，則無(wú)解，失敗退出，否則繼續(xù)執(zhí)行步驟Ⅲ；③將棧頂元素（記作結(jié)點(diǎn)N）從棧中取出；④如果結(jié)點(diǎn)N的深度等于最大深度，則轉(zhuǎn)向步驟Ⅱ；⑤擴(kuò)展結(jié)點(diǎn)N的所有結(jié)點(diǎn)，產(chǎn)生其全部的后繼結(jié)點(diǎn)，并壓入棧；⑥如果后繼結(jié)點(diǎn)中有任一結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)，則求得解，否則轉(zhuǎn)向步驟Ⅱ。

3.1.2搜索圖解

搜索圖解如圖3所示。

3.1.3算法優(yōu)缺點(diǎn)分析

深度優(yōu)先算法在解決八數(shù)碼問題時(shí)有一個(gè)致命缺點(diǎn)，就是必須設(shè)置一個(gè)深度界限，否則，搜索會(huì)一直沿著縱深方向發(fā)展，會(huì)一直無(wú)法搜索到解路徑。

即使加了限制條件，搜索到了解路徑，解路徑也不一定是最優(yōu)解路徑。

缺點(diǎn)：如果目標(biāo)節(jié)點(diǎn)不在搜索進(jìn)入的分支上，而該分支又是一個(gè)無(wú)窮分支，就得不到解，因此該算法是不完備的。

優(yōu)點(diǎn)：如果目標(biāo)節(jié)點(diǎn)在搜索進(jìn)入的分支上，則可以較快得到解。

3.2寬度優(yōu)先搜索算法（Breadth-First-Search）

寬度優(yōu)先算法將擴(kuò)展結(jié)點(diǎn)置于擴(kuò)展隊(duì)列的末端，使得搜索向橫向發(fā)展。

3.2.1算法策略

①將起始結(jié)點(diǎn)放入隊(duì)列中，如果該起始結(jié)點(diǎn)為一目標(biāo)結(jié)點(diǎn)，則得到解；②如果隊(duì)列為空，則無(wú)解，失敗退出，否則繼續(xù)步驟Ⅲ；③將第一個(gè)結(jié)點(diǎn)（記作結(jié)點(diǎn)N）放入隊(duì)列中，并將它放入已擴(kuò)展結(jié)點(diǎn)的隊(duì)列中；④擴(kuò)展結(jié)點(diǎn)N，如果沒有后繼結(jié)點(diǎn)，則轉(zhuǎn)向步驟Ⅱ；⑤將N的所有后繼結(jié)點(diǎn)放到隊(duì)列末端，并提供從這些后繼結(jié)點(diǎn)回到結(jié)點(diǎn)N的指針；⑥如果N的任一后繼結(jié)點(diǎn)是個(gè)目標(biāo)結(jié)點(diǎn)，則找到一個(gè)解（反向追蹤得到從目標(biāo)結(jié)點(diǎn)到起始結(jié)點(diǎn)的路徑），成功退出，否則轉(zhuǎn)向步驟Ⅱ。

寬度優(yōu)先搜索對(duì)于八數(shù)碼問題的解決情況，相較于深度優(yōu)先搜索好，對(duì)于解決步數(shù)在20～30步的初始狀態(tài)，可以在300～500ms內(nèi)解決。

3.2.2搜索圖解

搜索圖解如圖5所示。

3.2.3算法優(yōu)缺點(diǎn)分析

寬度優(yōu)先搜索，在搜索過程中，遵循一層一層往下搜索的搜索策略，它是一個(gè)完備的算法，找到的解一定是最優(yōu)解。

缺點(diǎn)：當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)會(huì)產(chǎn)生許多無(wú)用的節(jié)點(diǎn)，搜索效率低，只能適用于到達(dá)目標(biāo)結(jié)點(diǎn)步數(shù)較少的情況，如果步數(shù)超過15步，運(yùn)行時(shí)間太長(zhǎng)，則不再起作用。

優(yōu)點(diǎn)：只要問題有解，則總可以得到解，而且是最短路徑的解。

3.3A*算法

A*算法的基本思想與廣度優(yōu)先算法相同，但是在擴(kuò)展出一個(gè)結(jié)點(diǎn)后，要計(jì)算它的估價(jià)函數(shù)，并根據(jù)估價(jià)函數(shù)對(duì)待擴(kuò)展的結(jié)點(diǎn)排序，從而保證每次擴(kuò)展的結(jié)點(diǎn)都是估價(jià)函數(shù)最小的結(jié)點(diǎn)。

3.3.1算法思想

A*算法是一種常用的啟發(fā)式搜索算法。在A*算法中，一個(gè)結(jié)點(diǎn)位置的好壞用估價(jià)函數(shù)來(lái)對(duì)它進(jìn)行評(píng)估：

f（n）=g（n）+h（n）

這里，f（n）是估價(jià)函數(shù)，g（n）是起點(diǎn)到終點(diǎn)的最短路徑值（也稱為最小耗費(fèi)或最小代價(jià)），h（n）是n到目標(biāo)的最短路經(jīng)的啟發(fā)值。由于這個(gè)f（n）其實(shí)是無(wú)法預(yù)先知道的，因而實(shí)際上使用的是如下估價(jià)函數(shù)：

f（n）=g（n）+h（n）

其中，g（n）是從初始結(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)，h（n）是從結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)的最佳路徑的估計(jì)代價(jià)。在這里主要是h（n）體現(xiàn)了搜索的啟發(fā)信息，因?yàn)間（n）是已知的。用f（n）作為f（n）的近似，也即用g（n）代替g（n），h（n）代替h（n）。這樣必須滿足兩個(gè)條件：①g（n）≥g（n）（大多數(shù)情況下都是滿足的，可以不用考慮），且f必須保持單調(diào)遞增；②h必須小于等于實(shí)際的從當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最小耗費(fèi)h（n）≤h（n）。第二點(diǎn)特別重要，可以證明應(yīng)用這樣的估價(jià)函數(shù)可以找到最短路徑。

估價(jià)函數(shù)中，主要是計(jì)算h，對(duì)于不同的問題，h有不同的含義。這里的h（n）代表的是當(dāng)前結(jié)點(diǎn)狀態(tài)與目標(biāo)結(jié)點(diǎn)狀態(tài)相比沒有到位的棋子數(shù)，是最簡(jiǎn)單的估價(jià)函數(shù)。

3.3.2算法策略

①建立一個(gè)隊(duì)列，計(jì)算初始結(jié)點(diǎn)的估價(jià)函數(shù)f，并將初始結(jié)點(diǎn)入隊(duì)，設(shè)置隊(duì)列頭和尾指針；②取出隊(duì)列頭（隊(duì)列頭指針?biāo)福┑慕Y(jié)點(diǎn)，如果該結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，則輸出路徑，程序結(jié)束。否則對(duì)結(jié)點(diǎn)進(jìn)行擴(kuò)展；③檢查擴(kuò)展出的新結(jié)點(diǎn)是否與隊(duì)列中的結(jié)點(diǎn)重復(fù)，若與不能再擴(kuò)展的結(jié)點(diǎn)重復(fù)，則將它拋棄，若新結(jié)點(diǎn)與待擴(kuò)展的結(jié)點(diǎn)重復(fù)，則比較兩個(gè)結(jié)點(diǎn)的估價(jià)函數(shù)中g(shù)的大小，保留較小g值的結(jié)點(diǎn)。跳至Ⅴ；④如果擴(kuò)展出的新結(jié)點(diǎn)與隊(duì)列中的結(jié)點(diǎn)不重復(fù)，則按照其估價(jià)函數(shù)f的大小將它插入隊(duì)列中的頭結(jié)點(diǎn)之后待擴(kuò)展結(jié)點(diǎn)的適當(dāng)位置，使它們按從小到大的順序排列，最后更新隊(duì)列尾指針；⑤如果隊(duì)列頭的結(jié)點(diǎn)還可以擴(kuò)展，直接返回步驟②，否則將隊(duì)列頭指針指向下一結(jié)點(diǎn)，再返回步驟②。

3.3.3搜索圖解

搜索圖解如圖7所示。

3.3.4算法優(yōu)缺點(diǎn)分析

優(yōu)點(diǎn)：A*算法在絕大多數(shù)的情況下，在性能方面都遠(yuǎn)遠(yuǎn)優(yōu)與DFS和BFS。算法的主要運(yùn)行性能，取決于估價(jià)函數(shù)f的選取。

缺點(diǎn)：由于算法本身的特點(diǎn)，因此根據(jù)估價(jià)函數(shù)找到的解路徑不一定是最優(yōu)解路徑。

初始狀態(tài)： 5 6 8 4 0 1 2 3 7。運(yùn)行結(jié)果圖8所示。

4算法改進(jìn)

4.1狀態(tài)表示方法壓縮

有許多表示方法，比如一個(gè)3*3的八數(shù)碼盤可以壓縮成一個(gè)int值表示，但不適用于格子大于9的問題（如十五謎問題）。如果對(duì)空間要求很高，則還可以再壓縮。本文采用整數(shù)（int）表示的方法。

表示方法如下：由于int的大小是32位（范圍是[-2147483648-2147483648]），取一個(gè)int的低9位。為了方便尋找空格的位置，int的個(gè)位用來(lái)放空格的位置（1-9）。而前8位，按照行從上到下，列從左到右的順序依次記錄對(duì)應(yīng)位置上的數(shù)字。

4.2哈希函數(shù)去重

高效避免訪問同一個(gè)狀態(tài)，最直接的方法是記錄每一個(gè)狀態(tài)訪問與否，然后在衍生狀態(tài)時(shí)不衍生那些已經(jīng)訪問的狀態(tài)。基本思想是，給每個(gè)狀態(tài)標(biāo)記一個(gè)flag，若該狀態(tài)flag = true則不衍生，若為false則衍生并修改flag為true。

每一次移動(dòng)產(chǎn)生新狀態(tài)時(shí)，先判斷它是否已在兩個(gè)鏈表中，若存在，則不衍生；若不存在，將其放入活鏈表。對(duì)于被衍生的那個(gè)狀態(tài)，放入死鏈表。

為了記錄每一個(gè)狀態(tài)是否被訪問過，需要有足夠的空間。八數(shù)碼問題一共有9！，這個(gè)數(shù)字并不是很大，采用哈希函數(shù)的方法，使復(fù)雜度減為O（1）。

4.3估價(jià)函數(shù)改進(jìn)

通過找出不在位置的棋格個(gè)數(shù)形成的簡(jiǎn)單估價(jià)函數(shù)，不足以描述該結(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑長(zhǎng)度。因此本文采用一種更為科學(xué)合理的距離函數(shù)，來(lái)描述兩個(gè)狀態(tài)結(jié)點(diǎn)之間的差距。設(shè)距離函數(shù)為h2（n），其函數(shù)值為當(dāng)前結(jié)點(diǎn)狀態(tài)不在位置的棋格，到它目標(biāo)結(jié)點(diǎn)需要移動(dòng)的距離：

h2（n）=|x-x0|+|y-y0|

使用此函數(shù)，對(duì)于A*算法的估價(jià)函數(shù)進(jìn)行改進(jìn)，能夠取得比較明顯的改進(jìn)效果。

5效率比較

5.1概念

首先給出幾個(gè)用來(lái)進(jìn)行效率比價(jià)的變量：①步數(shù)（L）：從初始節(jié)點(diǎn)到達(dá)目標(biāo)的路徑長(zhǎng)度；②時(shí)間（T）：搜索程序運(yùn)行的時(shí)間，單位毫秒（ms）；③結(jié)點(diǎn)數(shù)（N）：整個(gè)過程中生成的節(jié)點(diǎn)總數(shù)（不包括初始節(jié)點(diǎn)）；④外顯率（P）：搜索工程中，從初始節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)進(jìn)行搜索的區(qū)域的寬度。

P=LN；P∈（0，1]

5.2實(shí)驗(yàn)數(shù)據(jù)分析

數(shù)據(jù)說明：①環(huán)境為Windows系統(tǒng)，語(yǔ)言為Java，使用控制臺(tái)命令輸出算法時(shí)間；②目標(biāo)狀態(tài) 1 2 3 4 5 6 7 8 9 0；③由于運(yùn)行時(shí)間受系統(tǒng)影響很大，具有一定的隨機(jī)性，因而每個(gè)狀態(tài)執(zhí)行3次，取中位數(shù)作為最終結(jié)果時(shí)間；④“長(zhǎng)度”為該初始狀態(tài)對(duì)應(yīng)的最短路徑的長(zhǎng)度。實(shí)驗(yàn)數(shù)據(jù)及結(jié)論如表1～表5、圖9～圖12所示。

（1）八數(shù)碼問題解路徑長(zhǎng)度比較。

（2）八數(shù)碼問題解決時(shí)間比較。

（4）八數(shù)碼問題外顯率比較。

5.3研究結(jié)論

通過研究，可得結(jié)論如下：①DFS的解路徑長(zhǎng)度趨于搜索深度界限（本文界限是30），搜索效率受深度影響很大，并且搜索結(jié)點(diǎn)冗余多、速度慢；②BFS找到的一定是最優(yōu)解，但是在算法效率上，雖然比DFS好，卻遠(yuǎn)遠(yuǎn)不如A*算法，同時(shí)BFS在搜索深度較深時(shí)，產(chǎn)生的冗余結(jié)點(diǎn)較多；③A*算法在效率上相對(duì)最優(yōu)，時(shí)間和空間上都比DFS和BFS更優(yōu)，但缺點(diǎn)是，找到的解不一定是最優(yōu)解；④改進(jìn)的A*算法在時(shí)間復(fù)雜度和效率上都更優(yōu)，空間利用率（外顯率）與A*算法差距不大?？傮w而言，改進(jìn)的算法取得了較好效果。

參考文獻(xiàn)參考文獻(xiàn)：

[1]蔡自興.徐光.人工智能及其應(yīng)用[M].北京：清華大學(xué)出版社，1996.

[2]唐朝舜.董玉德.八數(shù)碼的啟發(fā)式搜索算法及實(shí)現(xiàn)[J].安徽職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2004，3（3）：912.

[3]陶陽(yáng).VS2008環(huán)境下八數(shù)碼問題的BFS算法設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2009（26）：1417.

[4]張信一.黎燕.基于A*算法的八數(shù)碼問題的程序求解[J].現(xiàn)代計(jì)算機(jī)，2003，5（14）：1418.

[5]賀計(jì)文，宋承祥，劉弘.基于遺傳算法的八數(shù)碼問題的設(shè)計(jì)及實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010（3）：2023.

[6]姚全珠，趙雙瑞.基于狀態(tài)空間搜索的ETL過程優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2007（26）：4446.

責(zé)任編輯（責(zé)任編輯：孫娟）