大家好，又见面了，我是你们的朋友全栈君。
问题分析：
八数码问题是一个经典的BFS问题，把棋局看成一个状态图，共有9！种状态。从初始棋局开始，每次转移到下个状态，直到目标棋局为止。
仔细分析可知，八数码的关键是判重，如果不去除重复状态，程序会产生很多无效状态，从而复杂度大大增加
解决算法：
BFS + Cantor
案例分析：
（0表示空格所在位置）
初始棋局：
|1|2|3|
|0|8|4|
|7|6|5|
目标棋局：
|1|0|3|
|8|2|4|
|7|6|5|
1.先将空格和8交换得到：
|1|2|3|
|8|0|4|
|7|6|5|
2.再将空格和2交换得到目标棋局：
|1|0|3|
|8|2|4|
|7|6|5|
总共执行两次操作
C++代码：
#include <bits/stdc++.h>
using namespace std;
const int LEN = 362880; // 共9！种状态
struct node
{
int state[9]; // 记录八数码排列，即一个状态
int dis;
};
int dir[4][2] = {
//左，上，右，下顺时针方向
{
-1,0},
{
0,-1},
{
1,0},
{
0,1},
};
int visited[LEN] = {
0}; // cantor判重，若某状态访问过置为一
int start[9];
int goal[9];
long factory[] = {
1,1,2,6,24,120,720,5040,40320,362880}; // cantor判重用到的常数，从0！到9！
bool cantor(int str[], int n) {
long result = 0;
for(int i=0; i<n; ++i) {
int cnt = 0;
for(int j=i+1; j<n; ++j)
if(str[i] > str[j])
cnt++;
result += cnt*factory[n-i-1];
}
if(!visited[result]) {
visited[result] = 1;
return true;
}
else return false;
}
int bfs() {
node head;
memcpy(head.state, start, sizeof(head.state));
head.dis = 0;
queue<node> q;
cantor(head.state, 9);
q.push(head);
while(!q.empty()) {
head = q.front();
q.pop();
int z;
for(z=0; z<9; ++z)
if(head.state[z] == 0) //寻找元素0的位置
break;
// z的二维转换
int x = z%3;
int y = z/3;
// 向四个方向转移新状态
for(int i=0; i<4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
int nz = ny*3 + nx; // 二维化一维
if(nx >= 0 && nx <3 && ny >= 0 && ny < 3) {
//未越界
node nnode;
memcpy(&nnode, &head, sizeof(struct node));
swap(nnode.state[z], nnode.state[nz]);
nnode.dis++;
if(memcmp(nnode.state, goal, sizeof(goal)) == 0) //与目标状态比较
return nnode.dis;
if(cantor(nnode.state, 9)) //判重
q.push(nnode); //把新的状态放进队列
}
}
}
return -1; //没找到
}
int main() {
//freopen("in.txt", "r", stdin);
for(int i=0; i<9; ++i)
cin >> start[i];
for(int i=0; i<9; ++i)
cin >> goal[i];
int num = bfs();
if(num != -1)
cout << num << endl;
else
cout << "impossible" << endl;
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/158112.html原文链接：https://javaforall.net
