欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法设计与分析】 优先队列搜索算法求解八数码问题(搜索算法)

程序员文章站 2022-05-20 20:21:30
...

【算法设计与分析】 优先队列搜索算法求解八数码问题(搜索算法)

【问题描述】
采用优先队列搜索算法求解八数码问题,用一最小堆来存储活结点表,其优先级是结点的估价函数值。估价函数值是状态的深度加上不在位的将牌数。采用heapq模块来实现最小堆。如果迭代3000次,还没有找到目标状态,则输出error。

【输入形式】
在屏幕上输入起始状态。

【输出形式】
如果找到目标状态,则显示从起始状态到目标状态的搜索路径;如果迭代3000次,还没有找到目标状态,则输出error。

【样例1输入】

2 8 3
1 6 4
7 0 5

【样例1输出】

2 8 3
1 6 4
7 0 5

2 8 3
1 0 4
7 6 5

2 0 3
1 8 4
7 6 5

0 2 3
1 8 4
7 6 5

1 2 3
0 8 4
7 6 5

1 2 3
8 0 4
7 6 5

【样例1说明】
输入:起始状态,0代表空格。
输出:可找到目标状态,显示从起始状态到目标状态的搜索路径,状态间空一行,末尾不空行。

【样例2输出】

1 2 3
4 5 6
7 8 0

【样例2输出】

error

【样例2说明】
输入:起始状态,0代表空格。
输出:迭代3000次,还没有找到目标状态,则输出error。

【题解代码】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
const int len=362880;//状态共9!=362880种 
using namespace std;

int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//四个方向 
int vis[len]={0};//状态访问标记 
int pre[len];//记录上一个状态,用于打印路径 
int start[9],goal[9]={1,2,3,8,0,4,7,6,5};//初始状态和目标状态 
long factory[10]={1,1,2,6,24,120,720,5040,40320,362880};//0到9的阶乘 

struct node//状态结点 
{
	int state[9];
	int dis;
};

int difnum(node a)//不在位的将牌数 
{
	int num=0;
	for(int i=0;i<9;i++)
		if(a.state[i]!=goal[i])
			num++;
	return num;
}

struct cmp//结点权值比较 
{
	bool operator()(node &a,node &b)
	{
		return a.dis+difnum(a)>b.dis+difnum(b);//估价函数值是状态的深度加上不在位的将牌数 
	}
};

int Cantor(int str[],int n)//康托展开 
{
	int res=0;
	for(int i=0;i<n;i++)
	{
		int count=0;
		for(int j=i+1;j<n;j++)
			if(str[i]>str[j])
				count++;
		res+=count*factory[n-i-1];
	}
	return res;
}

stack<int> ans;//存储路径 
void Traceback(int can)//存储路径 
{
	ans.push(can);
	if(can==Cantor(start,9))//回到初始状态 
		return;
	Traceback(pre[can]);
}

void Print()//逆康托展开,打印路径 
{
	while(!ans.empty())
	{
		int quo,res=ans.top(),state[9],vis[9]={0};
		ans.pop();
		for(int i=0;i<9;i++)
		{
			quo=res/factory[9-i-1];
			res=res%factory[9-i-1];
			for(int j=0;j<9;j++)
			{
				if(!vis[j]&&!(quo--))
				{
					state[i]=j;
					vis[j]=1;
					break;
				}
			}
		}
		for(int i=0;i<9;i++)
		{
			cout<<state[i]<<" ";
			if(i%3==2)
				cout<<endl;
		}
		cout<<endl;
	}
}

int bfs()
{
	node head;
	memcpy(head.state,start,sizeof(start));
	head.dis=0;
	priority_queue<node,vector<node>,cmp> q;
	Cantor(head.state,9);
	q.push(head);
	int time=0;
	while(!q.empty())
	{
		time++;
		head=q.top();
		q.pop();
		if(memcmp(head.state,goal,sizeof(goal))==0)//到达目标状态,返回步数dis 
			return head.dis;
		if(time>=3000)//迭代超过3000次 
			return -1;
		int x,y,z;
		for(z=0;z<9;z++)
			if(head.state[z]==0)//找到0的位置 
				break;
		x=z%3;y=z/3;//横纵坐标 
		for(int i=0;i<4;i++)
		{
			int newx=x+dir[i][0];
			int newy=y+dir[i][1];
			int nz=newx+3*newy;
			if(newx>=0&&newx<3&&newy>=0&&newy<3)
			{
				node newnode;
				memcpy(&newnode,&head,sizeof(struct node));
				swap(newnode.state[z],newnode.state[nz]);
				newnode.dis++;
				int newcan=Cantor(newnode.state,9);
				int precan=Cantor(head.state,9);
				if(!vis[newcan])//康托展开判重 
				{
					q.push(newnode);
					vis[newcan]=1;
					pre[newcan]=precan;
				}
			}
		}
	}
	return -1;//未找到 
}

int main()
{
	for(int i=0;i<9;i++)
		cin>>start[i];
	//for(int i=0;i<9;i++)
	//	cin>>goal[i];
	int num=bfs();
	//cout<<num<<endl;
	if(num==-1)
		cout<<"error"<<endl;
	else
	{
		Traceback(Cantor(goal,9));
		Print();
	}
	return 0;
}
相关标签: 算法 ACM