搜索例题——八数码难题 luoguP1379

八数码难题

题目描述

解法一：bfs双向搜索

同时把开始和结束状态放入队列搜索，用map去重和记录步数答案

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
inline int read(){
	char c=getchar();ll x=0,f=1;
	while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x*f;
}
int s,t=123804765;
queue<int> q;
map<int,int> vis;//去重，0表示没访问过，1表示正序，2表示逆序搜 
map<int,int> ans;//记录答案
int a[4][4];
int nx,ny,fx,fy;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int main(){
//	freopen("B.in","r",stdin);
//	freopen("B.out","w",stdout);
	s=read();
	if(s==t){
		puts("0");
		return 0;
	}
	q.push(s);
	q.push(t);
	ans[s]=0;
	ans[t]=1;
	vis[s]=1;
	vis[t]=2;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		int now=u;
		for(int i=3;i>=1;i--){//数字转数组 
			for(int j=3;j>=1;j--){
				a[i][j]=now%10;
				now/=10;
				if(a[i][j]==0){
					fx=i;
					fy=j;//记录空格子位置 
				}
			}
		}
		for(int i=0;i<4;i++){
			nx=fx+dx[i];
			ny=fy+dy[i];//走哪个
			if(nx<1||nx>3||ny<1||ny>3) continue;
			swap(a[nx][ny],a[fx][fy]);
			now=0;
			for(int l=1;l<=3;l++){
				for(int r=1;r<=3;r++){
					now=now*10+a[l][r];
				}
			} //数组转数字 
		if(vis[now]==vis[u]){
			swap(a[nx][ny],a[fx][fy]);
			continue;//已经搜过，不继续搜了 
		}
		if(vis[now]+vis[u]==3){//两边都搜过了 
			printf("%d",ans[now]+ans[u]);
			return 0;
		}
		ans[now]=ans[u]+1;//维护这个状态的步数 
		vis[now]=vis[u];//方向相同 
		q.push(now);
		swap(a[fx][fy],a[nx][ny]);
		//回溯 
		}
	}
	return 0;
}

解法二：迭代加深+启发式搜索

何为迭代加深：
适用于搜索可能深度很大，但答案深度很小的搜索
限制每次搜索的深度，每次加大深度，直到搜到答案
何为启发式搜索：
应用一自定义的估价函数，描述当前搜索状态和目标状态的差别大小
优先搜索差距小的，大大减小复杂度。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
int t[4][4]=
{
	{0,0,0,0},
	{0,1,2,3},
	{0,8,0,4},
	{0,7,6,5}};
int a[5][5];
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
int flag;
char ss[15];
int dep;
int tx,ty,nx,ny;
bool check(){//判断当前状态是否为目标状态 
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(t[i][j]!=a[i][j]){
				return 0;
			}
		}
	}
	return 1;
}
bool test(int step){//本题定义估价函数为当前状态与目标状态不相同的位置总数 
	int sum=0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(t[i][j]!=a[i][j]){
				if(++sum+step>dep){//若不相同数加已走步数大于当前搜索深度，估价不合法 
					return 0;
				}
			}
		}
	}
	return 1;
} 
void Astar(int step,int x,int y,int pre){//step为当前深度，xy为当前空格位置，pre为上次向哪里走 
	if(step==dep){
		if(check()){
			flag=1;
		}
		return;
	}
	if(flag) return;
	for(int i=0;i<4;i++){
		nx=x+dx[i];
		ny=y+dy[i];
		if(nx<1||ny<1||nx>3||ny>3) continue;
		if(pre+i==3) continue;//最优性剪枝，若回到前一个状态肯定不优
		swap(a[x][y],a[nx][ny]);
		if(test(step)&&flag==0){
			Astar(step+1,nx,ny,i);//估价合法再搜，A*关键核心 
		}
		swap(a[x][y],a[nx][ny]);//回溯 
	}
}
int main(){
//	freopen("B.in","r",stdin);
//	freopen("B.out","w",stdout);
	scanf("%s",ss);
	for(int i=0;i<9;i++){
		a[i/3+1][i%3+1]=ss[i]-'0';
		if(a[i/3+1][i%3+1]==0){
			tx=i/3+1;
			ty=i%3+1;//记录初始空格位置 
		}
	}
	if(check()){
		printf("0\n");
		return 0;//特判初始为终止 
	}
	while(++dep){//迭代加深 ,dep为搜索深度 
		Astar(0,tx,ty,-1);
		if(flag){
			printf("%d\n",dep);
			return 0;
		}
	}
	return 0;
}