網(wǎng)站首頁 編程語言 正文
問題描述：
八數(shù)碼，在3×3的方格棋盤上，擺放著1到8這八個數(shù)碼，有1個方格是空的，其初始狀態(tài)如圖1所示，要求對空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個操作使得棋盤從初始狀態(tài)到目標狀態(tài)。（注：圖片給的例子無解。）
內(nè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*
先構(gòu)造一個優(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ù)組矩陣轉(zhuǎn)為一串數(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()) //隊空搜索結(jié)束
{
uu = u = Q.front();
Q.pop();
if (u == v)
return step[v];
for(int i=a-1;i>=0;i--) //把八字碼狀態(tài)的數(shù)字轉(zhuǎn)為數(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ù)
}實驗結(jié)果：
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ù)組轉(zhuǎn)為數(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()) //棧空即搜索結(jié)束
{
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ù)字轉(zhuǎn)換為數(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ù)
}實驗結(jié)果：
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ù)組轉(zhuǎn)為數(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表為空結(jié)束搜索
{
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;
}實驗結(jié)果：
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值小的方案構(gòu)造優(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ù)組轉(zhuǎn)為數(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é)果：
總結(jié)心得
廣度搜索從四周擴散式地搜索直到搜索到目標節(jié)點，比深度搜索效率要高；考慮到深度搜索要是不設置界限值可能要花很長時間才找到目標狀態(tài)節(jié)點，就采取了有界深度搜索，效率比深度搜索要高；啟發(fā)式搜索相對效率要更高一些，基于廣度搜索的算法，在代價函數(shù)估計值，找到最接近目標狀態(tài)的路徑去搜索到目標狀態(tài)。一個狀態(tài)表示成一維的形式，求出除0之外所有數(shù)字的逆序數(shù)之和，也就是每個數(shù)字前面比它大的數(shù)字的個數(shù)的和，稱為這個狀態(tài)的逆序。若兩個狀態(tài)的逆序奇偶性相同，則可相互到達，否則不可相互到達。
原文鏈接：https://blog.csdn.net/qq_43966552/article/details/112005269
相關推薦
- 2022-03-30 Android用動畫顯示或隱藏視圖_Android
- 2022-03-23 Unity3d實現(xiàn)跑馬燈廣播效果_C#教程
- 2023-01-23 Python+Qt身體特征識別人數(shù)統(tǒng)計源碼窗體程序(使用步驟)_python
- 2023-01-05 Python中glob類的使用方法_python
- 2022-04-17 C語言?動態(tài)內(nèi)存管理全面解析_C 語言
- 2022-11-17 Kotlin?StateFlow單數(shù)據(jù)更新熱流設計與使用介紹_Android
- 2022-05-17 Git 克隆指定分支的代碼
- 2022-08-10 Go語言反射獲取類型屬性和方法示例_Golang
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細win安裝深度學習環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速