八数码问题

八数码问题的实验

结果的讨论

设计科目：_____________________

题目：_____________________

专业：_____________________

班级：_____________________

序号：_____________________

姓名：_____________________

日期：_____________________

指导老师：_____________________

系主任：_____________________

关于八数码的讨论

一：八数码问题解析

八数码，使用电脑自动求解，在一个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这几种类的了解和运用。对它

们各方面的差别，优缺点都有所了解，知道它们在那种方面使用最优。从八数码

问题的界面设计到代码编写，到使用五种不同的算法来解决并对比，期间遇到各

种问题都通过查找资料或讨论来解决，大大加深了对数据结构方面知识的掌握，

是一次提升。