利用C++求解八數(shù)碼問題實例代碼
更新時間：2022年11月24日 09:17:02 作者：Wen'
所謂八數(shù)碼問題是指這樣一種游戲,將分別標有數(shù)字1，2，3，…,8的八塊正方形數(shù)碼牌任意地放在一塊3×3的數(shù)碼盤上,放牌時要求不能重疊,下面這篇文章主要給大家介紹了關于利用C++求解八數(shù)碼問題的相關資料,需要的朋友可以參考下
問題描述：
八數(shù)碼，在3×3的方格棋盤上，擺放著1到8這八個數(shù)碼，有1個方格是空的，其初始狀態(tài)如圖1所示，要求對空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個操作使得棋盤從初始狀態(tài)到目標狀態(tài)。（注：圖片給的例子無解。）
內容提要：
分別用廣度優(yōu)先搜索策略、深度優(yōu)先搜索策略和啟發(fā)式搜索算法（至少兩種）求解八數(shù)碼問題；分析估價函數(shù)對啟發(fā)式搜索算法的影響；探究討論各個搜索算法的特點。
實驗步驟：
1.隨機生成一個八數(shù)碼問題分布，設計一個可解的目標狀態(tài)（要求棋盤9個位置都不同）。
2.分別用廣度優(yōu)先搜索策略、深度優(yōu)先搜索策略和至少兩種啟發(fā)式搜索算法求解八數(shù)碼問題。
實驗步驟
1.廣度優(yōu)先搜索
先從空白格周圍開始搜索，上下左右四個方向找到了可交換的位置，就把位置交換之后的狀態(tài)放入隊列中，再從隊列中取出隊頭元素，重復以上步驟。
2.有界深度搜索
先設定一個搜索的界限值，從空白格的四周開始搜索，找到了可交換的位置，就把該狀態(tài)放進棧中，交換位置之后繼續(xù)搜索，直到搜索到了界限值并且四周都搜索完畢沒有可交換的位置，該狀態(tài)出棧，取出棧頂元素繼續(xù)重復以上步驟搜索。
3.啟發(fā)式搜索
從空白格的四周開始搜索，把空白格放進open表中，從open表中取出表頭，找出該層中上下左右四個方向搜索到可交換的位置，放進close表中，并計算出該狀態(tài)與目標狀態(tài)不同的格子數(shù)為id值，找出該層中最小id值的狀態(tài)，再把這些狀態(tài)放入open表中，重復上述步驟。
4.啟發(fā)式搜索A*
先構造一個優(yōu)先級隊列，從空白格四周開始搜索，把空白格放入open表中，并計算出該狀態(tài)的id值即層數(shù)加該狀態(tài)不同格子與移動到目標狀態(tài)最小位移數(shù)，取出open表中表頭元素放進close表，搜索可以交換的位置放進open，重復該步驟。
分析說明（包括核心代碼及解釋）
1.廣度優(yōu)先搜索
#include<iostream>
#include<map>
#include<queue>
#include<stack>
using namespace std;
queue<int>Q;
map<int, int>vis; //記錄該狀態(tài)是否被訪問過
map<int, int>step; //記錄層數(shù)
map<int,int>parent; //記錄該狀態(tài)的上一個狀態(tài)
stack<int>out;
int dis[4][2] = { -1,0,0,1,1,0,0,-1 }; //左、上、右、下
int u, v;
int change(int** p, int a, int b) //把數(shù)組矩陣轉為一串數(shù)字
{
int t = 0;
for (int i = 0; i < a; i++)
for (int j = 0; j < b; j++)
t = t * 10 + p[i][j];
return t;
}
int bfs(int** p, int a, int b) //廣度搜索
{
int x, y, uu; //x,y--空格所在的行列號，uu--隊頭八字碼狀態(tài)
Q.push(u); //把初始狀態(tài)放入隊列
vis[u] = 1; //被訪問過標記為1
step[u] = 0; //初始層數(shù)為0
while (Q.size()) //隊空搜索結束
{
uu = u = Q.front();
Q.pop();
if (u == v)
return step[v];
for(int i=a-1;i>=0;i--) //把八字碼狀態(tài)的數(shù)字轉為數(shù)組
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]) //若該狀態(tài)沒有被訪問過
{
Q.push(nu); //入隊
vis[nu] = 1;
step[nu] = step[u] + 1; //層數(shù)在上一個狀態(tài)層數(shù)上加一
parent[nu] = u; //記錄該狀態(tài)的父狀態(tài)
}
p[x + dis[i][0]][y + dis[i][1]] = p[x][y], p[x][y] = 0; //還原空格位置繼續(xù)搜索
}
}
}
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 < n; i++)
mau[i] = new int[m], mav[i] = new int[m];
cout << "初始狀態(tài):" << endl;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> mau[i][j];
cout << "最終狀態(tài):" << endl;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> mav[i][j];
u = change(mau, m, n), v = change(mav, m, n);
s = bfs(mau, m, n);
if (s != -1) //返回層數(shù)
{
cout << "到達目標狀態(tài)需要 " << s << " 步" << endl;
t = v;
while (t) //把所有的父狀態(tài)入棧
{
out.push(t);
t = parent[t];
}
while (out.size()) //輸出目標狀態(tài)的八字碼求解過程
{
int** o;
t = out.top();
out.pop();
o = new int* [n];
for (int i = 0; i < n; i++)
o[i] = new int[m];
for (int i = m - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)
o[i][j] = t % 10, t /= 10;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
cout << o[i][j] << " ";
cout << endl;
}
cout << "======" << endl;
}
}
else cout << "無解" << endl; //沒有返回層數(shù)
}實驗結果：
2.有界深度搜索
#include<iostream>
#include<queue>
#include<stack>
#include<map>
using namespace std;
int m, n, k;
map<int,int>vis; //記錄是否被訪問
map<int, int>step; //記錄層數(shù)
map<int, int>d; //記錄訪問方向
map<int, int>parent; //記錄該狀態(tài)的上一個狀態(tài)
stack<int>zhan;
stack<int>out;
int fx[4][2] = { 0,-1,-1,0,0,1,1,0 }; //左，上，右，下
int change(int** q) //將數(shù)組轉為數(shù)字
{
int s=0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
s = s * 10 + q[i][j];
return s;
}
int dfs(int u,int v) //有界深度搜索
{
int now, find; //now--現(xiàn)在的八字碼狀態(tài)，find--移動空格之后的八字碼狀態(tài)
int** p;
zhan.push(u); //先把初始狀態(tài)放進棧里
vis[u] = 1; //訪問過的狀態(tài)標記為1
step[u] = 0; //初始層數(shù)為0
p = new int* [n];
for (int i = 0; i < n; i++)
p[i] = new int[m];
while (zhan.size()) //?？占此阉鹘Y束
{
int s, x0, y0, x=-1, y=-1; //x0，y0--空格所在的行號、列號；x,y--空格移動后所在的行號、列號
s = now = zhan.top();
if (now == v) //找到目標狀態(tài)，返回層數(shù)
return step[v];
d[now]++;
for(int i=m-1;i>=0;i--) //把八字碼狀態(tài)的數(shù)字轉換為數(shù)組
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]) //根據(jù)記錄的方向次數(shù)移動空格位置
{
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 < m && y >= 0 && y < n) //當空格移動的位置合理
{
p[x0][y0] = p[x][y], p[x][y] = 0; //交換位置
find = change(p);
if (!vis[find]) //若該八字碼狀態(tài)沒有被訪問過
{
zhan.push(find); //將該狀態(tài)壓入棧
vis[find] = 1;
step[find] = step[now] + 1; //層數(shù)在上一曾基礎上加一
parent[find] = now;
if (find == v)
return step[v];
}
}
if (d[now] > 4||step[find]==k-1) //若該狀態(tài)所有方向搜索完畢或者已經(jīng)到達了深搜的界限，該狀態(tài)值出棧
zhan.pop();
}
return -1;
}
int main()
{
cout << "有界深度搜索" << endl;
int u, v, t;
int** mau, ** mav; //初始八字碼狀態(tài)、目標八字碼狀態(tài)
cout << "輸入m*n：" << endl;
cin >> m >> n;
cout << "輸入界：" << endl;
cin >> k;
mau = new int* [n];
mav = new int* [n];
for (int i = 0; i < n; i++)
mau[i] = new int[m], mav[i] = new int[m];
cout << "輸入初始狀態(tài)：" << endl;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> mau[i][j];
cout << "輸入最終狀態(tài)：" << endl;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> mav[i][j];
u = change(mau), v = change(mav);
if (dfs(u, v) >= 0) //返回了正確的層數(shù)
{
cout << "到達目標狀態(tài)需要 " << dfs(u, v) << " 步：" << endl;
t = v;
while (t) //把該狀態(tài)的父狀態(tài)壓入棧
{
out.push(t);
t = parent[t];
}
while (out.size()) //輸出棧中八字碼求解狀態(tài)過程
{
int** o;
t = out.top();
out.pop();
o = new int* [n];
for (int i = 0; i < n; i++)
o[i] = new int[m];
for (int i = m - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)
o[i][j] = t % 10, t /= 10;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
cout << o[i][j] << " ";
cout << endl;
}
cout << "======" << endl;
}
}
else cout << "無解" << endl; //沒有返回層數(shù)
}實驗結果：
3.啟發(fā)式搜索
#include<iostream>
#include<queue>
#include<map>
#include<stack>
using namespace std;
map<int, int>vis;
map<int, int>step;
map<int, int>id;
map<int, int>parent;
queue<int>open;
queue<int>close;
queue<int>nclose;
stack<int>out;
int m, n;
int dir[4][2] = { 0,-1,-1,0,0,1,1,0 }; //左、上、右、下
int change(int**p) //把數(shù)組轉為數(shù)字
{
int s = 0;
for(int i=0;i<m;i++)
for (int j = 0; j < n; j++)
s = s * 10 + p[i][j];
return s;
}
void getid(int a,int b) //獲取與目標狀態(tài)不同的格子數(shù)
{
int c;
c = a;
for (int i = 0; i < m * m; i++)
{
if ((a % 10) != (b % 10))
id[c]++;
a = a / 10, b = b / 10;
}
}
int A (int u,int v) //啟發(fā)式搜索
{
open.push(u); //把初始狀態(tài)放進open表中
vis[u] = 1; //標記該狀態(tài)已被訪問
getid(u, v); //獲取該狀態(tài)與目標狀態(tài)不同的格子數(shù)
while (open.size()) //open表為空結束搜索
{
int q, p, w, x, y, newx, newy, size;
if (open.front() == v) //找到目標狀態(tài)
return step[v];
size = open.size();
for(int i=0;i<size;i++) //找出該層數(shù)中，最小的id值
{
int** r;
w=q=open.front(); //取出表頭元素
open.pop();
r = new int* [n];
for (int i = 0; i < n; i++)
r[i] = new int[m];
for (int i = m - 1; 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++) //搜索該狀態(tài)的四個方向
{
newx = x + dir[i][0], newy = y + dir[i][1];
if (newx >= 0 && newx < m && newy >= 0 && newy < n) //若該位置可交換
{
r[x][y] = r[newx][newy]; //交換空白格位置
r[newx][newy] = 0;
p = change(r);
if (!vis[p]) //該狀態(tài)沒有被訪問過
{
close.push(p); //把該狀態(tài)放進close表
nclose.push(p);
vis[p] = 1;
step[p] = step[w] + 1; //層數(shù)在原來狀態(tài)上加一
parent[p] = w; //標記父狀態(tài)
getid(p, v);
}
r[newx][newy] = r[x][y]; //變回原來狀態(tài)
r[x][y] = 0;
}
}
}
if (close.size()) //若close表不為空
{
int csize = close.size(), min;
min = id[nclose.front()];
for (int i = 0; i < csize; i++) //找出close表中id的最小值
if (id[nclose.front()] < min)
{
min = id[nclose.front()];
nclose.pop();
}
else nclose.pop();
for (int i = 0; i < csize; i++) //把close表中id最小值的狀態(tài)放進open表中
if (id[close.front()] == min)
{
open.push(close.front());
close.pop();
}
else close.pop();
}
}
return -1;
}
int main()
{
cout << "A搜索" << endl;
int u, v, t;
int** mau, ** mav;
cout << "輸入m*n：" << endl;
cin >> m >> n;
mau = new int* [n], mav = new int* [n];
for (int i = 0; i < n; i++)
mau[i] = new int[m], mav[i] = new int[m];
cout << "輸入初始狀態(tài)：" << endl;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> mau[i][j];
cout << "輸入最終狀態(tài)：" << endl;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> mav[i][j];
u = change(mau), v = change(mav);
if (A(u, v) != -1)
{
cout << "到達目標狀態(tài)需要 " << A(u, v) << " 步" << endl;
t = v;
while (t)
{
out.push(t);
t = parent[t];
}
while (out.size()) //輸出到達目標狀態(tài)的過程
{
int** o;
t = out.top();
out.pop();
o = new int* [n];
for (int i = 0; i < n; i++)
o[i] = new int[m];
for (int i = m - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)
o[i][j] = t % 10, t /= 10;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
cout << o[i][j] << " ";
cout << endl;
}
cout << "======" << endl;
}
}
else cout << "無解" << endl;
}實驗結果：
4.啟發(fā)式搜索A*
#include<iostream>
#include<queue>
#include<stack>
#include<map>
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值小的方案構造優(yōu)先級隊列
{
return a.id > b.id;
}
};
priority_queue<A>open;
queue<A>close;
stack<int>out;
map<int, int>vis;
map<int, int>step;
map<int, int>parent;
int change(int **q) //把數(shù)組轉為數(shù)字
{
int s=0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
s = s * 10 + q[i][j];
return s;
}
void getid(A &u,A v) //獲取id值
{
int** q, ** w;
int a, b, s=0;
a = u.data, b = v.data;
q = new int* [n], w = new int* [n];
for (int i = 0; i < n; i++)
q[i] = new int[m], w[i] = new int[m];
for(int i=m-1;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<m;i++) //該狀態(tài)不同的格子數(shù)移動到目標狀態(tài)所需要的最小位移數(shù)
for(int j=0;j<n;j++)
if (q[i][j] != 0 && q[i][j] != w[i][j])
for (int k = 0; k < m; k++)
for (int l = 0; l < n; l++)
if (q[i][j] == w[k][l])
s = s + abs(k - i) + abs(l - j);
s = s + step[u.data]; //加上層數(shù)
u.id = s;
}
int Aplus(A u,A v)
{
vis[u.data] = 1; //標記初始狀態(tài)已被訪問過
step[u.data] = 0; //初始層數(shù)為0
getid(u, v);
open.push(u); //把初始狀態(tài)放入open表中
while (open.size())
{
int q, nq, x, y, newx, newy;
int** w;
w = new int* [n];
for (int i = 0; i < n; i++)
w[i] = new int[m];
close.push(open.top()); //把要搜索的狀態(tài)放入close表中
open.pop();
nq = q = close.front().data;
if (close.front().data == v.data) //找到目標狀態(tài)
return step[v.data];
for (int i = m-1; 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 < m && newy >= 0 && newy < n) //若搜索的位置可以交換
{
w[x][y] = w[newx][newy], w[newx][newy] = 0; //交換空白格位置
e = change(w);
if (!vis[e]) //若該狀態(tài)沒有被訪問過
{
z.data = e;
vis[z.data] = 1; //標記訪問
step[z.data] = step[q] + 1; //層數(shù)在原來狀態(tài)層數(shù)上加一
parent[z.data] = q; //標記父狀態(tài)
getid(z, v); //獲取id值
open.push(z); //把搜索的狀態(tài)放入open表中
}
w[newx][newy] = w[x][y], w[x][y] = 0;
}
}
close.pop();
}
return -1;
}
int main()
{
cout << "A*算法：" << endl;
A u, v;
int t;
int** mau, ** mav;
cout << "輸入m*n：" << endl;
cin >> m >> n;
mau = new int* [n], mav = new int* [n];
for (int i = 0; i < n; i++)
mau[i] = new int[m], mav[i] = new int[m];
cout << "輸入初始狀態(tài)：" << endl;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> mau[i][j];
cout << "輸入最終狀態(tài)：" << endl;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> mav[i][j];
u.data = change(mau), v.data = change(mav);
if (Aplus(u, v) != -1)
{
cout << "達到目標狀態(tài)需要： " << 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 < n; i++)
o[i] = new int[m];
for (int i = m - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)
o[i][j] = t % 10, t /= 10;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
cout << o[i][j] << " ";
cout << endl;
}
cout << "======" << endl;
}
}
else cout << "無解" << endl;
}實驗結果：
總結心得
廣度搜索從四周擴散式地搜索直到搜索到目標節(jié)點，比深度搜索效率要高；考慮到深度搜索要是不設置界限值可能要花很長時間才找到目標狀態(tài)節(jié)點，就采取了有界深度搜索，效率比深度搜索要高；啟發(fā)式搜索相對效率要更高一些，基于廣度搜索的算法，在代價函數(shù)估計值，找到最接近目標狀態(tài)的路徑去搜索到目標狀態(tài)。一個狀態(tài)表示成一維的形式，求出除0之外所有數(shù)字的逆序數(shù)之和，也就是每個數(shù)字前面比它大的數(shù)字的個數(shù)的和，稱為這個狀態(tài)的逆序。若兩個狀態(tài)的逆序奇偶性相同，則可相互到達，否則不可相互到達。
到此這篇關于利用C++求解八數(shù)碼問題的文章就介紹到這了,更多相關C++求解八數(shù)碼問題內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C語言預處理宏定義#define，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-10-10
這篇文章主要為大家詳細介紹了基于Qt的TCP實現(xiàn)通信，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
C++ using namespace std 用法深入解析
以下是對C++中using namespace std的用法進行了詳細的分析介紹，需要的朋友可以過來參考下2013-07-07
C++中不但可以用define定義常量還可以用const定義常量，下面這篇文章主要給大家分析介紹了關于C++中const與#define的利弊，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友可以參考下2018-05-05
c++ 類函數(shù)作為模板參數(shù)實現(xiàn)方式詳解
這篇文章主要介紹了c++ 類函數(shù)作為模板參數(shù)實現(xiàn)方式,在實現(xiàn)中加入增強邏輯，這種方式對代碼侵入性過高，而且無法控制該邏輯是否需要，如果不需要的話又得重新修改代碼實現(xiàn)，需要的朋友可以參考下2023-03-03
猜數(shù)字小游戲是我們小時候喜歡我們一個經(jīng)典小游戲。本文將用C語言實現(xiàn)這一經(jīng)典游戲，文中的示例代碼講解詳細，感興趣的可以了解一下2022-08-08
這篇文章主要介紹了C++中的string類型，在C++當中，除了char 類型，還有專門的字符串類型，就叫做string，下面文字將圍繞其相關資料展開詳細內容,需要的朋友可以參考一下，希望對你有所幫助2021-11-11
這篇文章主要介紹了如何理解C++ 臨時變量的常量性，幫助大家更好的理解和學習c++ 變量，感興趣的朋友可以了解下2020-08-08
這篇文章主要介紹了C++?DLL注入工具的相關資料,并向大家分享了完整的源碼，具有一定的參考價值，希望對正在工作或學習的你有所幫助2022-02-02
C語言實現(xiàn)通用數(shù)據(jù)結構之通用椎棧
這篇文章主要為大家詳細介紹了C語言實現(xiàn)通用數(shù)據(jù)結構之通用椎棧，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11