八数码问题简单解决办法

八数码问题简单解决办法问题分析:八数码问题是一个经典的BFS问题,把棋局看成一个状态图,共有9!种状态。从初始棋局开始,每次转移到下个状态,直到目标棋局为止。仔细分析可知,八数码的关键是判重,如果不去除重复状态,程序会产生很多无效状态,从而复杂度大大增加解决算法:BFS+Cantor案例分析:(0表示空格所在位置)初始棋局:|1|2|3||0|8|4||7|6|5|目标棋局:|1|0|…

大家好,又见面了,我是你们的朋友全栈君。

问题分析:

八数码问题是一个经典的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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/158112.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 数独解法Java实现「建议收藏」

    数独解法Java实现「建议收藏」数独问题描述标准的数独游戏是在一个9X9的棋盘上填写1–9这9个数字,规则是这样的:棋盘分成上图所示的9个区域(不同颜色做背景标出,每个区域是3X3的子棋盘),在每个子棋盘中填充1–9且不允许重复,下面简称块重复每一行不许有重复值,下面简称行重复每一列不许有重复值,下面简称列重复如上红色框出的子区域中的亮黄色格子

  • 相机参数标定(camera calibration)及标定结果如何使用「建议收藏」

    相机参数标定(camera calibration)及标定结果如何使用「建议收藏」一直都想写一写这个主题,但是,一直都感觉有点虚,也没有去整理。在网上搜了一下,发现大多数都是转来转去,看着也是似懂非懂的,让人很老火。所以,我就按照自己的理解,尽量简单易懂一点,也便于以后的应用。如有不足或者错误之处请指出,还请指出。1、相机标定的意义在机器视觉领域,相机的标定是一个关键的环节,它决定了机器视觉系统能否有效的定位,能否有效的计算目标物。相机的标定基本上可以分为两种,第一种是…

  • Qt编写GIF录屏工具(开源)「建议收藏」

    Qt编写GIF录屏工具(开源)「建议收藏」在平时的写作过程中,经常需要将一些操作动作和效果图截图成gif格式,使得涵盖的信息更全面更生动,有时候可以将整个操作过程和运行效果录制成MP4,但是文件体积比较大,而且很多网站不便于上传,基本上都支持gif动图,一般一个5秒左右的gif,800*600分辨率,可以很好的控制在500KB内,这样就比较完美的支持各大网站上传动图。最开始使用的是ScreenGif.exe,用了很久,感觉还可以,后面一…

  • Windows 桌面字体背景颜色取消 

    Windows 桌面字体背景颜色取消 

  • Method类的Invoke方法[通俗易懂]

    Method类的Invoke方法[通俗易懂]Dto:dto里面放的都是同一类型的字段/**Creation:2Dec2015*/packagecom.java.invoke;publicclassDto{privateIntegerCol1;privateIntegerCol2;privateIntegerCol3;privateIntegerCo

  • modelsim安装_Modelsim10.5安装教程

    modelsim安装_Modelsim10.5安装教程1.鼠标右击软件压缩包,选择“解压到modelsim-win64-10.5”。2.打开解压后的文件夹,鼠标右击“modelsim-win64-10.5”,选择“以管理员身份运行”。3.点击“下一步”。4.点击“浏览”选择软件的安装路径(建议安装在C盘以外的其他磁盘,且安装路径不要有中文),点击“下一步”。…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号