人工智能实验报告.docx

人工智能实验报告
人工智能实验报告
人工智能实验报告
人工智能
九宫格重移——搜索
成员：赵春杰 2009210665
羊森 2009210653
黄鑫 2009210
周成兵 2009210664
王素娟 2009210644
文档
人工智能实验报告
人工智能实验报告
人工智能实验报告
问题描述：
八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有
1 至 8
的某一数字， 不同棋子上标的数字不相同。 棋盘上还有一个空格， 与空格相邻的棋子可以移
到空格中。 要求解决的问题是： 给出一个初始状态和一个目标状态， 找出一种从初始转变成
目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆
法。棋子移动后， 状态就会发生改变。 解八数码问题实际上就是找出从初始状态到达目标状
态所经过的一系列中间过渡状态。
九宫重移有无答案检查（逆序数）
我们把每个 9 宫格横向展开，如第一个 123456789，我们把左边数大于右边
数的组数称为这个九宫格的逆序数，显然 123456789的逆序数为 0；考虑横向平
移，那么逆序数的增量为 2 或 0 或-2 ；纵向平移，逆序数的增量为 4 或 0 或 -4 ；
但 147258369 的逆序数为奇数。 所以 147258369 是无解的情况。由此也可以类推当将 9 宫格展开后，如果数据序列的逆序数为奇数， 则此数据序列对应的九宫格是无解的。
算法
队列： Queue open = new Queue(); 存放待扩展的节点
List ： List<Bfstr> closed = new List<Bfstr>(); 存放已被扩展过的节点
ArrayList map = new ArrayList();// 存放答案
HashTale ： Hashtable table = new Hashtable(); 构造哈希表以方便查找
人工智能实验报告
人工智能实验报告
人工智能实验报告
文档
人工智能实验报告
人工智能实验报告
人工智能实验报告
． BFS算法介绍
广度优先搜索算法 BFS基本思想： 从图中某顶点 v 出发，逐层对节点进行拓展， 并考察
是否为目标节点，在第 n 层节点没有全部扩展并考察前，不对第 n+1 层节点进行扩展。
对九宫重排问题， 即构造广度优先搜索树， 从初始状态， 利用广度优先搜索算法逐步找
到目标状态的节点。
．状态空间表示
状态空间用一维数组表示， 每个节点存放在 Bfstr 结构体中的字符 now 中，从第一行开
始从左往右给九宫格标号 0 8，字符串 now 元素下标代表格子位置，而 now 数组中对应
数组的值代表九宫格中存放的数码，用数值 9 代表空格。
．搜索树
2 8 3
1 6 4
1
7
5
2
3
4
2 8 3
2 8 3
2 8 3
1 6 4
1
4
1 6 4
7 5
7 6 5
7 5
5
6
8
9
7
2 8 3
2 8 3
2
3
2 8 3
2 8 3
6 4
1 4
1 8 4
1 4
1 6
1 7 5
7 6 5
7 6 5
7 6 5
7 5 4
．算法步骤
搜索：
1）把初始节点 S0 放入 OPEN表。
2）如果 OPEN表为空，则问题无解，退出。
3）把 OPEN表的第一个节点（记为节点n）取出放入 CLOSE表。