1028 - 搜索（3种写法） - 八数码难题（luogu P1379）

传送门

Analysis

介绍三种版本的搜索，都蛮好用的

TYPE 1 双向Bfs

通常情况下，当我们明确了初始状态和目标状态的时候双向Bfs的效率就会远高于单向Bfs
而这道题就恰好很适用
我们从初末状态同时往前Bfs，如果有一个状态它的下一个状态是被末状态搜索过（或初状态，总之这两个是被不同方向Bfs到的），那么这两个状态就是连接初末的纽带
我们的答案也就出来了（由于是Bfs（广搜），我们第一次得到的纽带就是我们的最优答案（走的步数最少））

Code

#include<bits/stdc++.h>
using namespace std;
int end=123804765,sta;
map<int,int> vis,ans;
queue<int> q;
int fx,fy,i,j,now,cur;
int a[4][4];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void solve(){
	q.push(sta);
	q.push(end);
	vis[sta]=1;vis[end]=2;
	ans[sta]=0;ans[end]=1;
	while(!q.empty()){
		now=q.front();q.pop();
		cur=now;
		for(i=3;i>=1;--i)//change numbers into matrix
		for(j=3;j>=1;--j){
			a[i][j]=now%10;now/=10;
			if(a[i][j]==0) fx=i,fy=j;
		}
		for(i=0;i<4;++i){
			now=0;
			int xx=fx+dx[i];
			int yy=fy+dy[i];
			if(xx>3||xx<=0||yy>3||yy<=0) continue;
			swap(a[xx][yy],a[fx][fy]);
			for(int k=1;k<=3;++k)//change matrix into numbers
			for(j=1;j<=3;++j){
				now=now*10+a[k][j];
			}
			if(vis[now]==vis[cur]){
				swap(a[xx][yy],a[fx][fy]);
				continue;
			}
			if(vis[now]+vis[cur]==3){//bond
				printf("%d",ans[now]+ans[cur]);
				exit(0);
			}
			vis[now]=vis[cur];
			ans[now]=ans[cur]+1;
			q.push(now);
			swap(a[xx][yy],a[fx][fy]);
		}
	}
	
}
int main(){
	scanf("%d",&sta);
	if(sta==end) return printf("0"),0;
	solve();
	return 0;
}

TPYE 2 IDA*

IDA^*就是迭代加深+A^*
感觉优化的力度比较大

在这里我们的A^*估价函数设置为
当前状态还有多少个位置与目标状态不对应
若当前步数+估价函数值>枚举的最大步数 则直接返回
当然这只是基本思路，搜索还可以有很大优化
我们在搜索中再加入最优性剪枝， 显然当前枚举下一个状态时如果回到上一个状态肯定不是最优， 所以我们在枚举下一状态时加入对这种情况的判断

Code

#include<bits/stdc++.h>
using namespace std;
int sta,end=123804765,ok=0;
int dx[4]={0,1,-1,0};//注意状态对称
int dy[4]={1,0,0,-1};
int a[4][4],ans[4][4];
int k;
bool check(){
	for(int i=1;i<=3;++i)
		for(int j=1;j<=3;++j)
			if(a[i][j]!=ans[i][j]) return 0;
	return 1;
}
bool eval(int stp){
	int num=0;
	for(int i=1;i<=3;++i)
		for(int j=1;j<=3;++j)
			if(a[i][j]!=ans[i][j])
			{
				++num;
				if(num+stp>k) return 0;
			}	
	return 1;
}
void A_star(int dep,int x,int y,int pre){
	if(dep==k) {if(check()) ok=1;return;}
	if(ok) return;
	for(int i=0;i<4;++i){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<=0||xx>3||yy<=0||yy>3||pre+i==3) continue;
		swap(a[xx][yy],a[x][y]);
		if(eval(dep)&&!ok) A_star(dep+1,xx,yy,i);
		swap(a[xx][yy],a[x][y]);
	}
}
int main(){
	scanf("%d",&sta);
	if(sta==end) return printf("0"),0;
	int now=sta,fx,fy;
	for(int i=3;i>=1;--i)
		for(int j=3;j>=1;--j)
		{
			a[i][j]=now%10;now/=10;
			ans[i][j]=end%10;end/=10;
			if(!a[i][j]) fx=i,fy=j;
		}
	for(k=1;;k++){//迭代的深度限制 
		A_star(0,fx,fy,-1);
		if(ok){
			printf("%d",k);
			break;
		} 
	}
	return 0;
}

TPYE 3 康托展开&A*

戳这里