八数码问题的实验结果的讨论
设计科目：_____________________
题 目：_____________________
专 业：_____________________
班 级：_____________________
序 号：_____________________
中国人民公安大学报考条件姓 名：_____________________
日 期：_____________________
指导老师：_____________________
系 主 任：_____________________
关于八数码的讨论
一：八数码问题解析
八数码，使用电脑自动求解，在一个3*3的矩阵中使12345678这几个数字在随意的初始状态中达到目标状态，3*3矩阵总共有9！=362880种状态，不是每种初始状态都可以达到目
标状态。有无解状态，要判断他们的逆序状态的奇偶性是否相同。初始状态的矩阵数字逆序状态与目标状态的矩阵数字的奇偶性一致，那么就有解。要求出有解状态并实现最优解，用Dictionary、List、SortedList 、SortedDictionary和Hashtable 五种存储方式来访问节点，实现算法。
二：设计过程：
3*3的棋盘有9个方格子，例如下图
4 | 6 | 总有一种记忆值得珍藏 2 | 互相帮助英文
1 | | 5 |
8 | 7 | 3 |
| | |
上图的棋盘可以衍生四种状态，如下图：
（A） （B） (C) (D)
同时，图（A）、（B）、 (C)、(D)又各自能衍生三个图，形成一种类似树状结构，一直搜索到目标状态才休止。
其中免不了出现重复的状态，为了避免访问重复状态，需要用存储方式来记录已访问过的状态，把每个访问过的棋盘状态放在集合中，并用来判断。集合随着搜索过程增长而曾大，访问节点越来越慢，所以使用不同的存储方式使用的时间也不一样。
三：五种算法的分析
1、使用Dictionary存储方式实现算法：
Dictionary是C#内置的类，它提供快速的基于兼职的元素查找。当程序中有很多元素的时候可以使用Dictionary。它包含在System.Collections.Generic名空间中。Dictionary本身有集合的功能，可以把它看成数组，结构是这样的：Dictionary<[键], [值]>，存入对象是需要与[键]值一一对应的存入该泛型，通过某一个一定的[键]去找到对应的值。Key是惟一的河北省科技馆Dictionary 泛型类提供了从一组键到一组值的映射。字典中的每个添加项都由一个值及其
相关联的键组成。通过键来检索值的速度是非常快的，是因为 Dictionary 类是作为一个哈希表来实现的。
以下是程序运行时得到的数据：
广度优先搜索算法求解：
Dictionary用时：0.037771 秒
访问节点：133058个
初始编码：478261536
关键代码实现：
Dictionary<int, int> CodeSetDic; 来存储已访问过的棋盘局面，已访问过的棋盘状态就不再重复出现。
在 BFS_AI : IEightNumAI类里面
GetAIResult方法，广度优先遍历队列的初始化为25000个元素和已访问节点的哈希表初始
化为181440个元素，并将根节点的信息加入哈希表。用While{for{}}循环来广度优先遍历元素。
GetPartFormNode方法，指定节点在哈希表中回溯以寻找整条路径。
2、使用List存储方式实现算法：
List 数组是固定大小的，不能伸缩，要有整数下标才能访问特定的元素，所以使用List存储方式来便利各种可能出现的状态，花时间肯定很多。
以下是程序运行时得到的数据：
广度优先搜索算法求解：
List用时：68.76545 秒
访问节点：133058个
初始编码：478261536
关键代码实现：
在 BFS_AI : IEightNumAI类里面 List<int> CodeSetList;来存储已访问过的棋盘局面，已访问过的棋盘状态就不再重复出现。
List与Dictionary的差别：
List队列就只有一个值，是有序元素集合，只能储存整型，用起来要声明大量元素类型，八数码程序用到大量的计算，各种数据类型，数据处理，用到索引集合，List则需要转换、拆装，花时间很多。
Directory字典是以键值对的形式使用，在数据类型为值类型的情况下，用到键值集合
，对比圻List来，它可以存储的不只是字符串，它的值可以是任意数据类型, 包括字符串, 整数, 对象, 甚至其它的 dictionary，避免了各个元素类型声明和数据的装箱和拆箱，从而运行起来减少大量时间。
3、使用SortedList存储方式实现算法：
SortedList，命名空间的System.Collections.SortedList类表示键/值对的集合，这些键值对
张九龄简介
按键排序并可按照键和索引访问。SortedList 在内部维护两个数组以存储列表中的元素；即，一个数组用于键，另一个数组用于相关联的值。每个元素都是一个可作为 DictionaryEntry 对象进行访问的键/值对。
关键代码实现：
在 BFS_AI : IEightNumAI类里面 SortedList<int, int> CodeSetSL;
来存储已访问过的棋盘局面，已访问过的棋盘状态就不再重复出现。
以下是程序运行时得到的数据：
广度优先搜索算法求解：
SortedList用时：3.94478 秒
访问节点：133058个
初始编码：478261536
春剑和春兰的区别SortedList与List，Dictionary的差别：
SortedList与List相对于Dictionary来说，属性大致一样，SortedList具有 O(log n) 的检索运算复杂度，允许通过相关联键或通过索引对值进行访问，可提供更大的灵活性，比List更适合解决八数码问题，可以自动增加容量，并且可以自动排序，SortedList 的随机查找比 Dictionary 和 格字成语List Hashtable还要快.。Dictionary <Key, Value> 泛型类提供了从一组键到一组值的映射。字典中的每个添加项都由一个值及其相关联的键组成。通过键来检索值的速度是非常快的，使用内存方面，SortedList是最吝啬的，
4、SortedDictionary
SortedDictionary <Key, Value> 每个键必须是唯一的，泛型类是检索运算复杂度为 O(log n) 的二叉搜索树，其中 n 是字典中的元素数。它与 SortedList <Key, Value> 泛型类相似。这两个类具有相似的对象模型，并且都具有 O(log n) 的检索运算复杂度。可对未排序的数据执行更快的插入和移除操作。重查找最值、按顺序遍历元素或插入、删除操作的程序，就用去公园玩的日记先考虑SortedDictionary。
