八數碼問題

八數碼問題的實驗

結果的討論

設計科目：_____________________

題目：_____________________

專業：_____________________

班級：_____________________

序號：_____________________

姓名：_____________________

日期：_____________________

指導老師：_____________________

系主任：_____________________

關于八數碼的討論

一：八數碼問題解析

八數碼，使用電腦自動求解，在一個3*3的矩陣中使12345678這幾個數

字在隨意的初始狀態中達到目標狀態，3*3矩陣總共有9！=362880種狀態，

不是每種初始狀態都可以達到目標狀態。有無解狀態，要判斷他們的逆序狀態的

奇偶性是否相同。初始狀態的矩陣數字逆序狀態與目標狀態的矩陣數字的奇偶性

一致，那么就有解。要求出有解狀態并實現最優解，用Dictionary、List、

SortedList、SortedDictionary和Hashtable五種存儲方式來訪問節點，實

現算法。

二：設計過程：

3*3的棋盤有9個方格子，例如下圖

462

15

873

上圖的棋盤可以衍生四種狀態，如下圖：

（A）（B）(C)(D)

同時，圖（A）、（B）、(C)、(D)又各自能衍生三個圖，形成一種類似樹狀結構，

一直搜索到目標狀態才休止。

其中免不了出現重復的狀態，為了避免訪問重復狀態，需要用存儲方式來記錄已

訪問過的狀態，把每個訪問過的棋盤狀態放在集合中，并用來判斷。集合隨著搜

索過程增長而曾大，訪問節點越來越慢，所以使用不同的存儲方式使用的時間也

不一樣。

三：五種算法的分析

1、使用Dictionary存儲方式實現算法：

Dictionary是C#內置的類，它提供快速的基于兼職的元素查找。當程序中有很

多元素的時候可以使用Dictionary。它包含在c名

空間中。Dictionary本身有集合的功能，可以把它看成數組，結構是這樣的：

Dictionary<[鍵],[值]>，存入對象是需要與[鍵]值一一對應的存入該泛型，通過

某一個一定的[鍵]去找到對應的值。Key是惟一的Dictionary泛型類提供了從

一組鍵到一組值的映射。字典中的每個添加項都由一個值及其相關聯的鍵組成。

通過鍵來檢索值的速度是非常快的，是因為Dictionary類是作為一個哈希表來

實現的。

以下是程序運行時得到的數據：

廣度優先搜索算法求解：

Dictionary用時：0.037771秒

訪問節點：133058個

初始編碼：478261536

關鍵代碼實現：

DictionaryCodeSetDic;來存儲已訪問過的棋盤局面，已訪問過的棋

盤狀態就不再重復出現。

在BFS_AI:IEightNumAI類里面

GetAIResult方法，廣度優先遍歷隊列的初始化為25000個元素和已訪問節點的

哈希表初始化為181440個元素，并將根節點的信息加入哈希表。用While{for{}}

循環來廣度優先遍歷元素。

GetPartFormNode方法，指定節點在哈希表中回溯以尋找整條路徑。

2、使用List存儲方式實現算法：

List數組是固定大小的，不能伸縮，要有整數下標才能訪問特定的元素，所以

使用List存儲方式來便利各種可能出現的狀態，花時間肯定很多。

以下是程序運行時得到的數據：

廣度優先搜索算法求解：

List用時：68.76545秒

訪問節點：133058個

初始編碼：478261536

關鍵代碼實現：

在BFS_AI:IEightNumAI類里面ListCodeSetList;來存儲已訪問過的

棋盤局面，已訪問過的棋盤狀態就不再重復出現。

List與Dictionary的差別：

List隊列就只有一個值，是有序元素集合，只能儲存整型，用起來要聲明大量元

素類型，八數碼程序用到大量的計算，各種數據類型，數據處理，用到索引集合，

List則需要轉換、拆裝，花時間很多。

Directory字典是以鍵值對的形式使用，在數據類型為值類型的情況下，用到鍵

值集合，對比圻List來，它可以存儲的不只是字符串，它的值可以是任意數據類

型,包括字符串,整數,對象,甚至其它的dictionary，避免了各個元素類型聲

明和數據的裝箱和拆箱，從而運行起來減少大量時間。

3、使用SortedList存儲方式實現算法：

SortedList，命名空間的List類表示鍵/值對的集合，

這些鍵值對按鍵排序并可按照鍵和索引訪問。SortedList在內部維護兩個數組

以存儲列表中的元素；即，一個數組用于鍵，另一個數組用于相關聯的值。每個

元素都是一個可作為DictionaryEntry對象進行訪問的鍵/值對。

關鍵代碼實現：

在BFS_AI:IEightNumAI類里面SortedListCodeSetSL;

來存儲已訪問過的棋盤局面，已訪問過的棋盤狀態就不再重復出現。

以下是程序運行時得到的數據：

廣度優先搜索算法求解：

SortedList用時：3.94478秒

訪問節點：133058個

初始編碼：478261536

SortedList與List，Dictionary的差別：

SortedList與List相對于Dictionary來說，屬性大致一樣，SortedList具有

O(logn)的檢索運算復雜度，允許通過相關聯鍵或通過索引對值進行訪問，可

提供更大的靈活性，比List更適合解決八數碼問題，可以自動增加容量，并且

可以自動排序，SortedList的隨機查找比Dictionary和ListHashtable還要

快.。Dictionary泛型類提供了從一組鍵到一組值的映射。字典

中的每個添加項都由一個值及其相關聯的鍵組成。通過鍵來檢索值的速度是非常

快的，使用內存方面，SortedList是最吝嗇的，

4、SortedDictionary

SortedDictionary每個鍵必須是唯一的，泛型類是檢索運算復

雜度為O(logn)的二叉搜索樹，其中n是字典中的元素數。它與SortedList

泛型類相似。這兩個類具有相似的對象模型，并且都具有O(log

n)的檢索運算復雜度。可對未排序的數據執行更快的插入和移除操作。重查找

最值、按順序遍歷元素或插入、刪除操作的程序，就用先考慮SortedDictionary。

關鍵代碼實現：

在BFS_AI:IEightNumAI類里面SortedDictionaryCodeSetSD;來

存儲已訪問過的棋盤局面，已訪問過的棋盤狀態就不再重復出現。

以下是程序運行時得到的數據：

廣度優先搜索算法求解：

SortedDictionary用時：3.94478秒

訪問節點：133058個

初始編碼：478261536

SortedDictionary與SortedList、List、Dictionary的差別：

SortedDictionary在八數碼計算最優解的速度上，比SortedList和List更快一

籌，比Dictionary慢。與SortedList的差別在于這兩個類內存的使用以及插入

和移除元素的速度，查詢速度比SortedList和List慢。所以SortedList，List

在查詢已經出現的棋盤畫面這一塊比SortedDictionary更適合。

5、Hashtable

Hashtable是tions命名空間提供的一個容器，用于處理和表現

類似key/value的鍵值對，其中key通常可用來快速查找，同時key是區分大

小寫；value用于存儲對應于key的值。Hashtable中key/value鍵值對均為

object類型，所以Hashtable可以支持任何類型的key/value鍵值對。

Hashtable與Dictionary采用的是不同的數據結構，Dictionary支持泛型，而

Hashtable不支持。

關鍵代碼實現：

在BFS_AI:IEightNumAI類里面HashtableCodeSetHt;來存儲已訪問過的棋

盤局面，已訪問過的棋盤狀態就不再重復出現。

以下是程序運行時得到的數據：

廣度優先搜索算法求解：

Hashtable用時：0.1875秒

訪問節點：133058個

初始編碼：478261536

以上幾種存儲方式的差別小結：

八數碼程序球最優解的運算速度上，Hashtable僅次于Dictionary，比

SortedDictionary、SortedList和List快很多，hashtable里存的對象全部

是object類型,所有對象存進去都被轉成object類型,讀取出來每次都需要轉換

類型,hashtable對存入的類型沒有限制,且在讀取轉換類型時容易出錯，

dictionary只能存入定義時指定的類型,而且不像hashtable會把類型轉換成

object,存取起來比前者方便,效率更高,因為不需要轉換類型,所以不會出現

hashtable里的轉換類型錯誤而報出程序異常的問題，這也說明了Dictionary

存儲當時無疑是解決八數碼問題的最佳選擇。而且之前的對比，沒有比

Dictionary更優的了，Dictionary性能最佳。

實驗小結：

通過使用Dictionary、List、SortedList、SortedDictionary和Hashtable五

種存儲方式來訪問節點實現算法，解決八數碼問題實驗中，通過實驗和以上分析，

查找資料，加深我了對Dictionary，SortedList這幾種類的了解和運用。對它

們各方面的差別，優缺點都有所了解，知道它們在那種方面使用最優。從八數碼

問題的界面設計到代碼編寫，到使用五種不同的算法來解決并對比，期間遇到各

種問題都通過查找資料或討論來解決，大大加深了對數據結構方面知識的掌握，

是一次提升。