【C++】人工智能实验二 八数码问题(DFS/BFS/A*Search)(附完整代码与状态迁移图)_八数码问题状态空间图

一、问题描述

1.在图1，3*3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空。

2.如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态（图1左）到目标状态（图1右）。

3.可自行设计初始状态。目标状态为数字从小到大按顺时针排列。

4.分别用广度优先搜索策略、深度优先搜索策略和启发式搜索算法（A*算法）求解八数码问题；分析估价函数对启发式搜索算法的影响；探究各个搜索算法的特点。

二、DFS

1、状态表示的数据结构

//状态
struct State
{
	int arr[3][3];	//记录九宫格
	int zeroX;		//0所在的横坐标
	int zeroY;		//0所在的纵坐标
	int f;			//父节点的位置，根节点的父节点记为-1
	int d;			//与根节点的距离
}states[maxNum];
1
2
3
4
5
6
7
8
9

2、状态扩展规则的表示

①　对当前结点进行拓展，0点朝上下左右四个位置移动改变状态，若当前移动会超出边界则放弃朝该方向移动。为了避免沿着一条边无限拓展影响效率，规定超出一定层数之后不再拓展。
②　判断移动后的状态是否与之前已经拓展过或存储的结点状态重复，若重复则删除，反之把状态存入表中。
③　检查新状态是否与目标状态相同，若是则输出移动路径，搜索结束。反之指针指向open表中的下一个结点，重复①②③，直到当前节点为空，寻找结束，未搜索到路径。

3、搜索产生的状态空间图

以棋盘初始状态为283104765为例

4、实验结果

5、实验代码

DFS代码下载地址

三、BFS

1、状态表示的数据结构

//状态
struct State
{
	int arr[3][3];	//记录九宫格
	int zeroX;		//0所在的横坐标
	int zeroY;		//0所在的纵坐标
	int f;			//父节点的位置，根节点的父节点记为-1
	int d;			//与根节点的距离
}states[maxNum];
1
2
3
4
5
6
7
8
9

2、状态扩展规则的表示

①　对当前结点进行拓展，0点朝上下左右四个位置移动改变状态，若当前移动会超出边界则放弃朝该方向移动。
②　判断移动后的状态是否与之前已经拓展过或存储的结点状态重复，若重复则删除，反之把状态存入表中。
③　检查新状态是否与目标状态相同，若是则输出移动路径，搜索结束。反之指针指向open表中的下一个结点，重复①②③，直到当前节点为空，寻找结束，未搜索到路径。

3、搜索产生的状态空间图

以棋盘初始状态为283104765为例

4、实验结果

5、实验代码

BFS代码下载地址

四、A*搜索算法

1、状态表示的数据结构

// 八数码
typedef struct node
{
	int arr[N][N];		//数组记录
	int zeroX, zeroY;	//0的位置
	int d, w, f;		//搜索深度，曼哈顿距离代价，总代价
	struct node *father;//指向父节点的指针
}node, *pNode;


// 顺序表
typedef struct list
{
	pNode arr[maxSize];
	long len;
}list, *pList;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2、状态扩展规则的表示

①　对当前结点进行拓展，0点朝上下左右四个位置移动改变状态，若当前移动会超出边界则放弃朝该方向移动。
②　判断移动后的状态是否与之前已经拓展过或存储的结点状态重复，若重复则删除，反之把状态存入表中。
③　检查新状态是否与目标状态相同，若是则输出移动路径，搜索结束。反之将open表中的结点按照f生序排序，指针指向open表中的下一个结点，重复①②③，直到当前节点为空，寻找结束，未搜索到路径。

3、搜索产生的状态空间图

以棋盘初始状态为283164705为例

4、实验结果

5、实验代码

A*Search算法完整代码

五、总结

三种算法都找到了同一种最优解法，移动的步骤相同。BFS经过了35个状态找到了目标状态，DFS经过了272个状态找到了目标状态，A经过了12个状态找到了目标状态。
三者中DFS所花的时间最长，时间复杂度为O()，A所花时间最短，在本次实验中，A*算法明显优于其它两个算法。