2.八数码II(搜索进阶 IDA*估价函数 + 迭代加深)

八数码II

↑ 题目链接

题目

在一个 \(3×3\) 的网格中，\(1∼8\) 这 8 个数字和一个 X 恰好不重不漏地分布在这 \(3×3\) 的网格中。

例如：

1 2 3
X 4 6
7 5 8

在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。

把 X 与上下左右方向数字交换的行动记录为 u、d、l、r。

现在，给你一个初始网格状态，并希望你将其变换为一个目标网格状态，请你找到所需行动次数最少的方案。

我们用一行字符串来描述一种网格状态。

例如，网格：

1 2 3 
X 4 6 
7 5 8 

用 123X46758 来表示。

输入格式

第一行包含整数 \(T\) ，表示共有 \(T\) 组测试数据。
每组数据占两行，第一行包含一个字符串表示初始网格状态，第二行包含一个字符串表示目标网格状态。
保证给定状态合法，并且一定有解。

输出格式

每组数据输出占两行，第一行输出 Case x: y，其中 x 为组别编号（从 1 开始），y为所需最少行动次数。
第二行输出具体行动方案，如果方案不唯一，则输出字典序最小的方案。

数据范围
\(1≤T≤200\)

输入样例：

2
12X453786
12345678X
564178X23
7568X4123

输出样例：

Case 1: 2
dd
Case 2: 8
urrulldr

思路

本题需要最小字典序，并且有多组样例。应该使用 \(IDA^{∗}\) 解题：

估值函数的选择：

• 每个点与目标点曼哈顿距离差的和。

在何时选择 \(A^{∗}\) 或 \(IDA^{∗}\) ：

• 需要最小字典序时，状态表示很大，指数增长较快时，使用 \(IDA^{∗}\)
• 若状态容易表示，指数增长较慢时，使用 \(A^{∗}\)（注意需要最小字典序时不能用 \(A^{∗}\) ，因为它不是按照顺序搜索的）

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
string s1,s2;
int pos[12];
int path[N];
string op="dlru";
int dx[]={1,0,0,-1};
int dy[]={0,-1,1,0};

//估值函数，当前状态和目标状态每个点的曼哈顿距离差的和
int f()
{
	int res=0;
	for(int i=0;i<9;i++)
	{
	    if(s1[i]!='X')
	    {
	        int num=s1[i]-'0';
	        res+=abs(i/3-pos[num]/3)+abs(i%3-pos[num]%3);
	    }
	}
	
	return res;
}

bool dfs(int u,int depth)
{
    //如果当前深度 + 估值深度 > 最大深度，直接回溯
	if(f()+u>depth)return false;
	
	//找到答案，返回true
	if(s1==s2)return true;
	
	
	//存X当前的位置序号
	int k;
	for(int i=0;i<9;i++)
		if(s1[i]=='X')
		{
			k=i;
			break;
		}
	
	int x=k/3,y=k%3;
	
	for(int i=0;i<4;i++)
	{
		int a=x+dx[i],b=y+dy[i];
		if(a<0||a>=3||b<0||b>=3)continue;
		
		 //避免往回走(至少走了1步,且上一步和当前一步和为3)
        //d+u=0+3=3  l+r=1+2=3
        //下(d):0 左(l):1 右(r):2 上(u):3
		if(u>0&&i+path[u-1]==3)continue;
		
		swap(s1[k],s1[a*3+b]);
		path[u]=i;//保存路径
		
		if(dfs(u+1,depth))return true;//找到答案，一路返回true
		swap(s1[k],s1[a*3+b]);
	}
	
	
	return false;
}

int main()
{
	int T;
	cin>>T;
	for(int i=1;i<=T;i++)
	{
		cin>>s1>>s2;
		
		for(int i=0;i<9;i++)
			if(s2[i]!='X')
				pos[s2[i]-'0']=i;
		
		 //迭代加深IDA*
		int depth=0;
		while(!dfs(0,depth))depth++;
		
		printf("Case %d: %d\n",i,depth);
		
		for(int i=0;i<depth;i++)
			printf("%c",op[path[i]]);
		
		puts("");
	}
	
	
	return 0;
}