八數碼問題解法效率比較及改進研究 

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

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

關鍵詞：八數碼；深度優先搜索；寬度優先搜索；A*算法；曼哈頓距離

DOIDOI：10.11907/rjdk.161867

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2016）009004105

基金項目基金項目：

作者簡介作者簡介：付宏杰（1973-），女，吉林公主嶺人，博士，吉林工程技術師范學院信息工程學院副教授，研究方向為人工智能、群體智能、機器學習。

1問題描述

八數碼問題就是在一個大小為3×3的九宮格上，放置8塊編號為1～8的木塊，九宮格中有一個空格，周圍（上下左右）的木塊可以和空格交換位置。對于問題，給定一個初始狀態（如圖1（a）初始狀態），目標狀態（如圖1（b）目標狀態）是期望達到1～8順序排列的序列，并且空格在右下角，問題的實質就是尋找一個合法的移動序列。

2問題分析和模型表示

2.1模型建立

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

2.2分析解的存在性

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

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

3搜索策略

搜索算法本質上是一棵將初始節點作為根節點的四叉樹。從初始節點開始，以空白格向4個方向的移動作為分支。求解的過程就是尋找一條從根節點到目標結點的路徑的過程。

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

3.1深度優先搜索算法（Depth-First-Search）

深度優先搜索策略是擴展當前結點，生成的子節點總是置于擴展棧的前端，這樣搜索向縱深方向發展。

3.1.1算法策略

①將起始結點S加入棧中，如果此結點是目標結點，則得到解；②如果棧為空，則無解，失敗退出，否則繼續執行步驟Ⅲ；③將棧頂元素（記作結點N）從棧中取出；④如果結點N的深度等于最大深度，則轉向步驟Ⅱ；⑤擴展結點N的所有結點，產生其全部的后繼結點，并壓入棧；⑥如果后繼結點中有任一結點為目標結點，則求得解，否則轉向步驟Ⅱ。

3.1.2搜索圖解

搜索圖解如圖3所示。

3.1.3算法優缺點分析

深度優先算法在解決八數碼問題時有一個致命缺點，就是必須設置一個深度界限，否則，搜索會一直沿著縱深方向發展，會一直無法搜索到解路徑。

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

缺點：如果目標節點不在搜索進入的分支上，而該分支又是一個無窮分支，就得不到解，因此該算法是不完備的。

優點：如果目標節點在搜索進入的分支上，則可以較快得到解。

3.2寬度優先搜索算法（Breadth-First-Search）

寬度優先算法將擴展結點置于擴展隊列的末端，使得搜索向橫向發展。

3.2.1算法策略

①將起始結點放入隊列中，如果該起始結點為一目標結點，則得到解；②如果隊列為空，則無解，失敗退出，否則繼續步驟Ⅲ；③將第一個結點（記作結點N）放入隊列中，并將它放入已擴展結點的隊列中；④擴展結點N，如果沒有后繼結點，則轉向步驟Ⅱ；⑤將N的所有后繼結點放到隊列末端，并提供從這些后繼結點回到結點N的指針；⑥如果N的任一后繼結點是個目標結點，則找到一個解（反向追蹤得到從目標結點到起始結點的路徑），成功退出，否則轉向步驟Ⅱ。

寬度優先搜索對于八數碼問題的解決情況，相較于深度優先搜索好，對于解決步數在20～30步的初始狀態，可以在300～500ms內解決。

3.2.2搜索圖解

搜索圖解如圖5所示。

3.2.3算法優缺點分析

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

缺點：當目標節點距離初始節點較遠時會產生許多無用的節點，搜索效率低，只能適用于到達目標結點步數較少的情況，如果步數超過15步，運行時間太長，則不再起作用。

優點：只要問題有解，則總可以得到解，而且是最短路徑的解。

3.3A*算法

A*算法的基本思想與廣度優先算法相同，但是在擴展出一個結點后，要計算它的估價函數，并根據估價函數對待擴展的結點排序，從而保證每次擴展的結點都是估價函數最小的結點。

3.3.1算法思想

A*算法是一種常用的啟發式搜索算法。在A*算法中，一個結點位置的好壞用估價函數來對它進行評估：

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

這里，f（n）是估價函數，g（n）是起點到終點的最短路徑值（也稱為最小耗費或最小代價），h（n）是n到目標的最短路經的啟發值。由于這個f（n）其實是無法預先知道的，因而實際上使用的是如下估價函數：

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

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

估價函數中，主要是計算h，對于不同的問題，h有不同的含義。這里的h（n）代表的是當前結點狀態與目標結點狀態相比沒有到位的棋子數，是最簡單的估價函數。

3.3.2算法策略

①建立一個隊列，計算初始結點的估價函數f，并將初始結點入隊，設置隊列頭和尾指針；②取出隊列頭（隊列頭指針所指）的結點，如果該結點是目標結點，則輸出路徑，程序結束。否則對結點進行擴展；③檢查擴展出的新結點是否與隊列中的結點重復，若與不能再擴展的結點重復，則將它拋棄，若新結點與待擴展的結點重復，則比較兩個結點的估價函數中g的大小，保留較小g值的結點。跳至Ⅴ；④如果擴展出的新結點與隊列中的結點不重復，則按照其估價函數f的大小將它插入隊列中的頭結點之后待擴展結點的適當位置，使它們按從小到大的順序排列，最后更新隊列尾指針；⑤如果隊列頭的結點還可以擴展，直接返回步驟②，否則將隊列頭指針指向下一結點，再返回步驟②。

3.3.3搜索圖解

搜索圖解如圖7所示。

3.3.4算法優缺點分析

優點：A*算法在絕大多數的情況下，在性能方面都遠遠優與DFS和BFS。算法的主要運行性能，取決于估價函數f的選取。

缺點：由于算法本身的特點，因此根據估價函數找到的解路徑不一定是最優解路徑。

初始狀態： 5 6 8 4 0 1 2 3 7。運行結果圖8所示。

4算法改進

4.1狀態表示方法壓縮

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

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

4.2哈希函數去重

高效避免訪問同一個狀態，最直接的方法是記錄每一個狀態訪問與否，然后在衍生狀態時不衍生那些已經訪問的狀態?；舅枷胧?，給每個狀態標記一個flag，若該狀態flag = true則不衍生，若為false則衍生并修改flag為true。

每一次移動產生新狀態時，先判斷它是否已在兩個鏈表中，若存在，則不衍生；若不存在，將其放入活鏈表。對于被衍生的那個狀態，放入死鏈表。

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

4.3估價函數改進

通過找出不在位置的棋格個數形成的簡單估價函數，不足以描述該結點到目標節點的路徑長度。因此本文采用一種更為科學合理的距離函數，來描述兩個狀態結點之間的差距。設距離函數為h2（n），其函數值為當前結點狀態不在位置的棋格，到它目標結點需要移動的距離：

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

使用此函數，對于A*算法的估價函數進行改進，能夠取得比較明顯的改進效果。

5效率比較

5.1概念

首先給出幾個用來進行效率比價的變量：①步數（L）：從初始節點到達目標的路徑長度；②時間（T）：搜索程序運行的時間，單位毫秒（ms）；③結點數（N）：整個過程中生成的節點總數（不包括初始節點）；④外顯率（P）：搜索工程中，從初始節點向目標節點進行搜索的區域的寬度。

P=LN；P∈（0，1]

5.2實驗數據分析

數據說明：①環境為Windows系統，語言為Java，使用控制臺命令輸出算法時間；②目標狀態 1 2 3 4 5 6 7 8 9 0；③由于運行時間受系統影響很大，具有一定的隨機性，因而每個狀態執行3次，取中位數作為最終結果時間；④“長度”為該初始狀態對應的最短路徑的長度。實驗數據及結論如表1～表5、圖9～圖12所示。

（1）八數碼問題解路徑長度比較。

（2）八數碼問題解決時間比較。

（4）八數碼問題外顯率比較。

5.3研究結論

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

參考文獻參考文獻：

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

[2]唐朝舜.董玉德.八數碼的啟發式搜索算法及實現[J].安徽職業技術學院學報，2004，3（3）：912.

[3]陶陽.VS2008環境下八數碼問題的BFS算法設計與實現[J].電腦知識與技術，2009（26）：1417.

[4]張信一.黎燕.基于A*算法的八數碼問題的程序求解[J].現代計算機，2003，5（14）：1418.

[5]賀計文，宋承祥，劉弘.基于遺傳算法的八數碼問題的設計及實現[J].計算機技術與發展，2010（3）：2023.

[6]姚全珠，趙雙瑞.基于狀態空間搜索的ETL過程優化[J].計算機工程與應用，2007（26）：4446.

責任編輯（責任編輯：孫娟）