利用C++求解八数码问题实例代码

所谓八数码问题是指这样一种游戏,将分别标有数字1，2，3，…,8的八块正方形数码牌任意地放在一块3×3的数码盘上,放牌时要求不能重叠,下面这篇文章主要给大家介绍了关于利用C++求解八数码问题的相关资料,需要的朋友可以参考下

问题描述：

八数码，在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。（注：图片给的例子无解。）

内容提要：

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

实验步骤：

1.随机生成一个八数码问题分布，设计一个可解的目标状态（要求棋盘9个位置都不同）。

2.分别用广度优先搜索策略、深度优先搜索策略和至少两种启发式搜索算法求解八数码问题。

实验步骤

1.广度优先搜索

先从空白格周围开始搜索，上下左右四个方向找到了可交换的位置，就把位置交换之后的状态放入队列中，再从队列中取出队头元素，重复以上步骤。

2.有界深度搜索

先设定一个搜索的界限值，从空白格的四周开始搜索，找到了可交换的位置，就把该状态放进栈中，交换位置之后继续搜索，直到搜索到了界限值并且四周都搜索完毕没有可交换的位置，该状态出栈，取出栈顶元素继续重复以上步骤搜索。

3.启发式搜索

从空白格的四周开始搜索，把空白格放进open表中，从open表中取出表头，找出该层中上下左右四个方向搜索到可交换的位置，放进close表中，并计算出该状态与目标状态不同的格子数为id值，找出该层中最小id值的状态，再把这些状态放入open表中，重复上述步骤。

4.启发式搜索A*

先构造一个优先级队列，从空白格四周开始搜索，把空白格放入open表中，并计算出该状态的id值即层数加该状态不同格子与移动到目标状态最小位移数，取出open表中表头元素放进close表，搜索可以交换的位置放进open，重复该步骤。

分析说明（包括核心代码及解释）

1.广度优先搜索

#include #include #include #include using namespace std; queueQ; mapvis;     //记录该状态是否被访问过 mapstep;      //记录层数 mapparent;     //记录该状态的上一个状态 stackout; int dis[4][2] = { -1,0,0,1,1,0,0,-1 };     //左、上、右、下 int u, v; int change(int** p, int a, int b)   //把数组矩阵转为一串数字 { int t = 0; for (int i = 0; i =0;i--)       //把八字码状态的数字转为数组 for (int j = b - 1; j >= 0; j--) { p[i][j] = uu % 10, uu = uu / 10; if (p[i][j] == 0)     //标记空格位置 x = i, y = j; } for (int i = 0; i <4; i++)     //空格四周搜索 { int nu; if (!(x == 0 && i == 0) && !(y == b - 1 && i == 1) && !(x == a - 1 && i == 2) && !(y == 0 && i == 3))   //当空格所走位置合理 { p[x][y] = p[x + dis[i][0]][y + dis[i][1]], p[x + dis[i][0]][y + dis[i][1]] = 0;     //交换空格位置 nu = change(p, a, b); if (!vis[nu])      //若该状态没有被访问过 { Q.push(nu);      //入队 vis[nu] = 1; step[nu] = step[u] + 1;     //层数在上一个状态层数上加一 parent[nu] = u;          //记录该状态的父状态 } p[x + dis[i][0]][y + dis[i][1]] = p[x][y], p[x][y] = 0;      //还原空格位置继续搜索 } } } return -1; } int main() { cout << "广度搜索" << endl; int m, n, s, t; int** mau, ** mav; cout << "输入m*n；" << endl; cin >> m >> n; mau = new int* [n], mav = new int* [n]; for (int i = 0; i > mau[i][j]; cout << "最终状态:" << endl; for (int i = 0; i > mav[i][j]; u = change(mau, m, n), v = change(mav, m, n); s = bfs(mau, m, n); if (s != -1)       //返回层数 { cout << "到达目标状态需要 " << s << " 步" << endl; t = v; while (t)        //把所有的父状态入栈 { out.push(t); t = parent[t]; } while (out.size())      //输出目标状态的八字码求解过程 { int** o; t = out.top(); out.pop(); o = new int* [n]; for (int i = 0; i = 0; i--) for (int j = n - 1; j >= 0; j--) o[i][j] = t % 10, t /= 10; for (int i = 0; i

实验结果：

2.有界深度搜索

#include #include #include #include using namespace std; int m, n, k; mapvis;     //记录是否被访问 mapstep;     //记录层数 mapd;      //记录访问方向 mapparent;      //记录该状态的上一个状态 stackzhan; stackout; int fx[4][2] = { 0,-1,-1,0,0,1,1,0 };      //左，上，右，下 int change(int** q)    //将数组转为数字 { int s=0; for (int i = 0; i =0;i--)      //把八字码状态的数字转换为数组 for (int j = n-1; j >=0; j--) { p[i][j] = s % 10; s = s / 10; if (p[i][j] == 0)      //标记空格所在位置 x0 = i, y0 = j; } switch (d[now])       //根据记录的方向次数移动空格位置 { case 1: x = x0 + fx[0][0], y = y0 + fx[0][1]; break;   //左 case 2: x = x0 + fx[1][0], y = y0 + fx[1][1]; break;   //上 case 3: x = x0 + fx[2][0], y = y0 + fx[2][1]; break;   //右 case 4: x = x0 + fx[3][0], y = y0 + fx[3][1]; break;   //下 } if (x >= 0 && x = 0 && y  4||step[find]==k-1)     //若该状态所有方向搜索完毕或者已经到达了深搜的界限，该状态值出栈 zhan.pop(); } return -1; } int main() { cout << "有界深度搜索" << endl; int u, v, t; int** mau, ** mav;      //初始八字码状态、目标八字码状态 cout << "输入m*n：" << endl; cin >> m >> n; cout << "输入界：" << endl; cin >> k; mau = new int* [n]; mav = new int* [n]; for (int i = 0; i > mau[i][j]; cout << "输入最终状态：" << endl; for (int i = 0; i > mav[i][j]; u = change(mau), v = change(mav); if (dfs(u, v) >= 0)     //返回了正确的层数 { cout << "到达目标状态需要 " << dfs(u, v) << " 步：" << endl; t = v; while (t)    //把该状态的父状态压入栈 { out.push(t); t = parent[t]; } while (out.size())     //输出栈中八字码求解状态过程 { int** o; t = out.top(); out.pop(); o = new int* [n]; for (int i = 0; i = 0; i--) for (int j = n - 1; j >= 0; j--) o[i][j] = t % 10, t /= 10; for (int i = 0; i

实验结果：

3.启发式搜索

#include #include #include #include using namespace std; mapvis; mapstep; mapid; mapparent; queueopen; queueclose; queuenclose; stackout; int m, n; int dir[4][2] = { 0,-1,-1,0,0,1,1,0 };     //左、上、右、下 int change(int**p)    //把数组转为数字 { int s = 0; for(int i=0;i= 0; i--)       //找到空白格位置 for (int j = n - 1; j >= 0; j--) { r[i][j] = q % 10, q = q / 10; if (r[i][j] == 0) { x = i, y = j;        //标记空白格位置 } } for (int i = 0; i <4; i++)     //搜索该状态的四个方向 { newx = x + dir[i][0], newy = y + dir[i][1]; if (newx >= 0 && newx = 0 && newy > m >> n; mau = new int* [n], mav = new int* [n]; for (int i = 0; i > mau[i][j]; cout << "输入最终状态：" << endl; for (int i = 0; i > mav[i][j]; u = change(mau), v = change(mav); if (A(u, v) != -1) { cout << "到达目标状态需要 " << A(u, v) << " 步" << endl; t = v; while (t) { out.push(t); t = parent[t]; } while (out.size())    //输出到达目标状态的过程 { int** o; t = out.top(); out.pop(); o = new int* [n]; for (int i = 0; i = 0; i--) for (int j = n - 1; j >= 0; j--) o[i][j] = t % 10, t /= 10; for (int i = 0; i

实验结果：

4.启发式搜索A*

#include #include #include #include using namespace std; int m, n; int dir[4][2] = { 0,-1,-1,0,0,1,1,0 };     //左、上、右、下 struct A { int data; int id; friend bool operator <(A a,A b)    //按照id值小的方案构造优先级队列 { return a.id > b.id; } }; priority_queueopen; queueclose; stackout; mapvis; mapstep; mapparent; int change(int **q)    //把数组转为数字 { int s=0; for (int i = 0; i =0;i--) for (int j = n-1; j >=0; j--) { q[i][j] = a % 10, w[i][j] = b % 10; a = a / 10, b = b / 10; } for(int i=0;i=0; i--)      //找到空白格位置 for (int j = n-1; j >=0; j--) { w[i][j] = nq % 10, nq /= 10; if (w[i][j] == 0)      //标记空白格位置 x = i, y = j; } for (int i = 0; i <4; i++)        //搜索四个方向 { A z; int e; newx = x + dir[i][0], newy = y + dir[i][1]; if (newx >= 0 && newx = 0 && newy > m >> n; mau = new int* [n], mav = new int* [n]; for (int i = 0; i > mau[i][j]; cout << "输入最终状态：" << endl; for (int i = 0; i > mav[i][j]; u.data = change(mau), v.data = change(mav); if (Aplus(u, v) != -1) { cout << "达到目标状态需要： " << Aplus(u, v) << " 步" << endl; t = v.data; while (t) { out.push(t); t = parent[t]; } while (out.size()) { int** o; t = out.top(); out.pop(); o = new int* [n]; for (int i = 0; i = 0; i--) for (int j = n - 1; j >= 0; j--) o[i][j] = t % 10, t /= 10; for (int i = 0; i

实验结果：

总结心得

广度搜索从四周扩散式地搜索直到搜索到目标节点，比深度搜索效率要高；考虑到深度搜索要是不设置界限值可能要花很长时间才找到目标状态节点，就采取了有界深度搜索，效率比深度搜索要高；启发式搜索相对效率要更高一些，基于广度搜索的算法，在代价函数估计值，找到最接近目标状态的路径去搜索到目标状态。一个状态表示成一维的形式，求出除0之外所有数字的逆序数之和，也就是每个数字前面比它大的数字的个数的和，称为这个状态的逆序。若两个状态的逆序奇偶性相同，则可相互到达，否则不可相互到达。

到此这篇关于利用C++求解八数码问题的文章就介绍到这了,更多相关C++求解八数码问题内容请搜索0133技术站以前的文章或继续浏览下面的相关文章希望大家以后多多支持0133技术站！

以上就是利用C++求解八数码问题实例代码的详细内容，更多请关注0133技术站其它相关文章！