VS2008環境下八數碼問題的BFS算法設計與實現

摘要:針對八數碼求解問題，對寬度優先搜索算法進行分析，在VS2008開發環境下，設計并實現了解決八數碼難題的BSF算法。實驗結果表明，BSF算法具有可獲取最優解的優點。

關鍵詞:八數碼;寬度優先搜索;C#;VS2008

中圖分類號:TP312文獻標識碼:A文章編號:1009-3044(2009)26-7417-03

Desigh and Programming of Breadth-First Search Algorithm for Eight-Figure Puzzle Problem with VS2008

TAO Yang

(Nanchang Military Academy， Nanchang 330103， China)

Abstract: Aiming at solving the Eight-Figure Puzzle problem， the paper analyses the Breadth-First Search algorithm， and then proposes a method of design and programming of BSF algorithm with VS2008. The experimental results indicate that the BSF algorithm has an advantage to gain the best solution of Eight-Figure Puzzle problem.

Key words: eight-figure puzzle; breadth-first search; C#; VS2008

搜索是人工智能中的一個基本問題，也是模擬仿真中研究的一般性問題，是推理不可分割的一部分。現實世界中的大多數問題都是結構不良或非結構化的問題，一般不存在現成的求解方法，而只能利用已有的知識一步步地摸索著前進，如梵塔問題、MC問題、猴子摘香蕉、八數碼難題等。

八數碼難題一般描述:在3×3的方格棋盤上，分別放置標有數字1、2、3、4、5、6、7、8的八張牌，第九張牌不標數字，記為空格，給定一種初始狀態和目標狀態，通過移動空格，使得棋盤從初始狀態向目標狀態轉換(其中操作空格可用的操作有:左移、上移、右移、下移，但不能移出棋盤之外)，通過搜索策略尋找從初始狀態到目標狀態的解路徑。

解決八數碼問題的搜索策略有很多，歸納起來主要有三種:深度優先搜索(Depth First Search，DFS)、寬度優先搜索(Breadth First Search，BFS)、A*算法。前兩種是經典的盲目搜索算法，后一種是經典的啟發式搜索算法。對于八數碼問題，深度優先搜索一般不能保證得到最優解，A*算法又與其啟發式函數息息相關，也無法保證得到最優解。而寬度優先搜索算法可以得到從初始狀態到目標狀態的最短解路徑。雖然寬度搜索算法效率相對較低，搜索點數較多，但考慮到計算機技術的飛速發展，運算速度已經不是影響搜索效率的重要瓶頸了。因此，展開寬度優先搜索算法的研究，不但對解決八數碼難題有著實際的意義，而且對解決人工智能中的其它問題，也可以起到積極的參考作用。

本文從人工智能的角度分析八數碼問題，對解決八數碼問題的寬度優先搜索策略展開研究，給出算法的一般描述，通過對算法進行分析，指出了寬度優先搜索算法的優點，可以獲得最優的解路徑。最后，在VS2008開發環境下，設計并實現了寬度優先搜索算法，即BSF算法，通過實驗運行效果驗證了寬度優先搜索算法的優越性。

1 寬度優先搜索算法

1.1 算法一般描述

寬度優先搜索是—種先生成的節點先擴展的搜索策略，其一般過程是:從初始狀態節點開始逐層向下擴展，在第N層節點還沒有全部搜索結束之前，不進人第N+1層節點的搜索。

設TreeNodes表中的節點是根據生成的先后進行排序的，先進人TreeNodes表中的節點排在前面，后進入TreeNodes表的節點排后面，則算法可以進行一般描述:

1) 把初始節點StartState放入TreeNodes表中，作為當前節點;

2) 如果TreeNodes表中當前節點指向為空，則問題無解，失敗退出;

3) 把TreeNodes表的當前節點取出，并記該節點為CurrentState;

4) 檢查當前節點CurrentState是否為目標節點。若是，則得到問題的解，成功退出;否則進行第(5)步;

5) 若節點CurrentState無法擴展，設定TreeNodes的下一個節點為當前節點，轉第(2)步;

6) 對當前節點CurrentState進行擴展，將其子節點存放入TreeNodes表的尾部，并為每一個子節點設置指向父節點CurrentState的指針，然后設定TreeNodes的下一個節點為當前節點，轉第2)步。

1.2 針對八數碼問題的寬度優先搜索算法分析

對于求解八數碼問題，首先要給出一個起始狀態和結束狀態，如圖1所示。那么，寬度優先搜索算法的目標就是尋找一條從起始狀態到結束狀態的解路徑。

根據算法的一般描述，首先把起始狀態加入到TreeNodes表中，作為根節點0。然后，把0節點取出，和結束狀態比較，如圖1來看，明顯不是目標節點。所以對節點0進行擴展，根據空格上下左右移動，得到四個子節點，即節點1、2、3、4，并加入到TreeNodes表的尾部。再取出節點1作為當前節點，也不是目標節點，對其進行子節點擴展，得到2個節點，即節點5、6，并加入到TreeNodes表的尾部。然后，取出節點2作為當前節點，以此類推，進行下去，整個搜索節點過程，如圖2所示。

圖2 八數碼問題寬度優先搜索過程

圖2給出了搜索到節點12時，整個TreeNodes表的節點情況。然后繼續搜索節點13，根據算法過程，直到發現目標節點結束。這樣的搜索過程，就是寬度優先搜索算法。最壞情況下，該算法將搜索整個狀態空間，即搜索9!/2=181440個節點。但從圖2可以看出，只要從根節點到目標節點構建一個路徑，則該路徑一定是最短的一條解路徑。

2 八數碼問題的VS2008實現

2.1 編程環境簡介

我們的軟件實驗開發軟件選用了Visual Studio 2008，它是基于.NET框架的軟件開發平臺，.NET開發環境是流行的基于Windows平臺的編程平臺。Visual Studio 2008可以為項目指定.NET Framework 的版本:.NET Framework 2.0、3.0 或 3.5。應用程序的.NET Framework 目標是指為使該應用程序能夠在計算機上運行而需要在該計算機上安裝的 .NET Framework 版本。

Visual Studio 2008中的C#代碼編輯器提供了語句結束和快速信息功能，以支持C# 3.0中的下列新語言構造:

●隱式類型的局部變量

●查詢表達式

●擴展方法

●對象/集合初始值設定項

●匿名類型

●Lambda 表達式

●分部方法

C#語言簡單易學，C#3.0語言和編譯器引入了多種新的語言功能，為快速開發實現八數碼問題的BFS算法提供了方便。

2.2 界面設計

求解八數碼問題是一個智力型的游戲，基于這樣的考慮，給出界面設計如圖3所示。為了美觀，在不影響系統運行性能的情況下，引用了第三方皮膚控件IrisSkin2.dll。從界面可以看出，除了起始狀態和結束狀態之外，還給出了存放中間狀態的棋盤。另外一些關鍵的按鈕，如“隨機初始狀態”、“隨機結束狀態”、“無解判斷”、“寬度搜索”、“狀態演示”等，其按鈕作用比較明顯。

作為游戲，在設計上，考慮了手動移動空格的操作方法。在中間狀態情況下，棋盤上每個按鈕可以按下操作，按下空格的上下左右按鈕，如同空格的上移、下移、左移、右移。在信息記錄里面顯示操作步驟。游戲過程如圖4所示。

2.3 BFS算法設計

寬度優先搜索算法設計主要包括狀態編碼、狀態比較函數、無解判定、狀態樹構建算法、核心搜索算法等幾個部分。

由于界面設計采用了按鈕的形式，在狀態編碼上，按照順時針順序，使用整型數組存儲每個按鈕上的數字來表示某個狀態，代碼如下:

int[] astate = new int[9] { 0， 1， 2， 3， 4， 5， 6， 7， 8 };

空格對應于按鈕上無數字，在數組中值記為0。

通過狀態比較才能判定是否已經達到目標狀態。基于整型數組的狀態編碼方式，可以很方便進行狀態比較，只要檢查兩個狀態對應的數組是否相等即可。

無解判定可以避免無解的情況下盲目搜索。可以證明，八數碼問題有解的充分必要條件是兩個狀態的逆序列奇偶性相同。為此，無解判定問題轉化為計算兩個狀態的逆序列奇偶性問題，給出代碼如下:

private bool ExistAns(int[] start， int[] end)

{ int sequence_start = 0， sequence_end = 0;

for (int i = 0; i < start.Length; i++)

{ 計算start狀態的逆序列值sequence_start;

計算end狀態的逆序列值sequence_end;

}

return (sequence_start + sequence_end) % 2 == 0;

}

狀態樹構建問題主要是對當前節點構建其子節點的問題，分三種情況考慮:第一種情況，空格在棋盤中間;第二種情況，空格在棋盤的四個角上;第三種情況，空格在除前兩種情況之外的位置。每一種情況構建子節點的數量不同，具體算法中分不同的情況進行處理。

子節點構建完成之后，要考慮是否已經在狀態樹上存在該狀態，如果存在，則不加入到狀態樹中;否則，加入狀態樹中，作為一個新的節點存在。

寬度優先搜索算法是解決八數碼問題的關鍵，根據BFS算法的基本思想，使用alllist存放整個TreeNodes樹的所有節點，給出其算法代碼如下:

private void SearchByRoot(long p)

{

while (searchresult p < listtreecount)

{

取出當前節點狀態astate

if (checkstate(endstate， astate))//是否已經結束

{

算法已經找到結束狀態，完成!

}

listOpenTempcount = getStates(astate);//計算其可能的狀態

bool inhere = 1;

if (listOpenTempcount > 0)

{

循環取出可能的狀態

檢查是否已經在alllist列表中

如果在alllist列表中，則取下個可能狀態

如果不在列表中，把該可能狀態加入到alllist的尾部

}

取alllist的下一個節點為當前節點

p++;

}}

2.4 實驗結果

根據圖3所示的操作界面上的起始狀態和結束狀態，首先進行無解判斷，點擊“有解判斷”之后，程序提示是有解的。然后進行寬度優先搜索，界面顯示如圖5所示。

經過一段時時間之后，系統搜索完成，彈出界面，如圖6所示。

從搜索結果可以看出，此次八數碼問題的解路徑為20步，系統記錄了每個節點的父節點，通過指向連接，可搜索到整個路徑，點擊狀態演示后，最終界面如圖7所示。另外，為了進行算法比較，在實際實驗中實現了深度優先搜索算法，通過進行大量的實驗，從結果上看，對于每種有解的起始狀態和結束狀態，深度優先搜索算法的解路徑往往比寬度優先搜索算法多很多步。

3 結束語

從本文的實驗可以看出，寬度優先搜索是一種完備策略，即只要問題有解，它就一定可以找到解。并且，寬度優先搜索找到的解，還一定是路徑最短的解。這些都是寬度優先搜索的優點。當然，寬度優先搜索也存在很多缺點，主要缺點是盲目性較大，尤其是當目標行點距初始節點較遠時，將產生許多無用的節點，因此其搜索效率較低，雖然相對于計算機飛速發展的運算速度來講，這已經不是關鍵問題，但仍是下一步有待改進的方面。

參考文獻:

[1] 佘玉梅，段鵬.人工智能及其應用[M].上海:上海交通大學出版社，2007.

[2] 王萬森.人工智能原理及其應用[M].2版.北京:電子工業出版社，2007.

[3] 詹志輝，胡曉敏，張軍.通過八數碼問題比較搜索算法的性能[J].計算機工程與設計，2007，28(11):2505-2508.

[4] 劉浩，鮑遠律.A*算法在矢量地圖最優路徑搜索中的應用[J].計算機仿真，2008，25(4):253-257.

[5] 劉甲耀，嚴桂蘭.C#程序設汁教程[M].北京:電子工業出版社，2007.

[6] 余金山，陳建榮，王濤，等.C#2008開發入行真功夫[M].北京:電子工業出版社，2009.