八数码问题简单解决办法

八数码问题简单解决办法问题分析:八数码问题是一个经典的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)


相关推荐

  • SODA-大型活动大规模人群的识别和疏散:从公交2.0到公交3.0

    SODA-大型活动大规模人群的识别和疏散:从公交2.0到公交3.02019独角兽企业重金招聘Python工程师标准>>>…

  • Pycharm Pro 2021.12.13激活【2021.10最新】「建议收藏」

    (Pycharm Pro 2021.12.13激活)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~00…

  • java bufferedwriter 关闭_Java BufferedWriter.close()方法示例

    java bufferedwriter 关闭_Java BufferedWriter.close()方法示例JavaBufferedWriter.close()方法示例BufferedWriter的JavaBufferedWriter.close()方法的语法如下。publicvoidclose()throwsIOException示例在下面的代码中展示了如何使用BufferedWriter.close()方法。importjava.io.BufferedWriter;import…

  • 海量数据处理技巧

    海量数据处理技巧数据时代来临,数据量的爆炸式增长是最为显著的特征。当高性能硬件的普及还跟不上这样的数据大潮时,如何在有限的时空资源内处理海量数据成为了计算机科学以及数理统计等领域最大的挑战。所谓“数据处理”,在本文中特指通过计算机技术,对海量数据进行存储、统计、查询等操作。我将在下面介绍一些基本的海量数据处理的方法,供大家参考。需要明确的一点是,现实情况复杂多变,所以对于海量数据处理这样大的主题,是不可能用一…

  • vb.net listview_不VB思考VB数据表

    vb.net listview_不VB思考VB数据表控件:TEXTBOX   :1个     Name:txtJobNoBUTTON:    2个      Name:btnFilter,btnShowAllLISTVIEW: 1个      Name:lstvwJobNo Columns:JobNo,ContainerID,CartonID,PO,Style,Color,Size,ShipMent,Factory        

  • vue实现简单的分页功能[通俗易懂]

    vue实现简单的分页功能[通俗易懂]分页其实就是对一组数据分组!而vue又刚好是数据驱动,所以我们只需要关注数据层就行了!分页开始—>变量:data(){return{//假设这是后台传来的数据来源data:[],//所有页面的数据totalPage:[],//每页显示数量pageSize:5,…

发表回复

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

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