IDA* （洛谷 P2324 [SCOI2005]骑士精神）

传送门：https://www.luogu.com.cn/problem/P2324

题目大意

前置知识

迭代加深

• 每次搜索开始时设定一个最大的搜索深度，使得搜索树的深度不超过限定的这个数
  
  一般在具有步数限定的情况下，或者搜索树深度较大，但是搜索所需的答案在较浅深度时使用
  
  (类似于BFS)

估值函数

• 对于一步搜索来说，可以对当前的搜索节点设定一个估价，以预计它未来的实际代价，适时排除非最优情况，从而达到有效的正确剪枝
  
  设：(g(n)) 为当前的代价，(h(n)) 为未来预估的最优化代价，则 (f(n)) 代表的估值函数为：(f(n) = g(n) + h(n))

ps

• (A*) 是对广度优先搜索结合估价函数的优化
  
  
• (IDA*) 是结合迭代加深，对深度优先搜索的优化
  

Solution

• 设置估价函数：最有情况下，交换黑色棋子与白色棋子的最有情况就是直接通过一步移动到空格子上，然后互换即可，那么显然，与目标格子颜色位置不相符的格子的数量即为该估价函数的值
  

• 结合迭代加深的方法直接进行深度优先搜索即可

Code

#include<iostream>
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const ll maxn=10;
ll t,n,sx,sy,ans,flag,kkk;
ll go[10][2]={{0,0},{2,1},{1,2},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
ll goal[10][10]={\最终结果图，进行快速比较
	{0,0,0,0,0,0},
	{0,1,1,1,1,1},
	{0,0,1,1,1,1},
	{0,0,0,2,1,1},
	{0,0,0,0,0,1},
	{0,0,0,0,0,0}
};
char a[maxn][maxn];
ll b[maxn][maxn];

inline ll gu()\估价函数
{
	register ll ret=0;
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=5;j++)
		{
			if(b[i][j]!=goal[i][j]) ret++;
		}
	}
	return ret;	
}

inline void dfs(ll step,ll x,ll y,ll maxx)
{
	if(step==maxx)
	{
		if(gu()==0) flag=1;
		return ;
	}
	for(int i=1;i<=8;i++)
	{
		ll tx=x+go[i][0];
		ll ty=y+go[i][1];
		if(tx<1||tx>5||ty<1||ty>5) continue;
		swap(b[x][y],b[tx][ty]);
		if(gu()+step<=maxx) dfs(step+1,tx,ty,maxx);
		swap(b[x][y],b[tx][ty]);
	}
}

int main(void)
{
	scanf("%lld",&t);
	while(t--)
	{
		flag=0;
		kkk=0;
		for(int i=1;i<=5;i++)
		{
			for(int j=1;j<=5;j++)
			{
				cin>>a[i][j];
				if(a[i][j]=='*')
				{
					b[i][j]=2;
					sx=i,sy=j;
				}
				else b[i][j]=a[i][j]-'0';
			}
		}
		
		for(int i=1;i<=15;i++)//迭代加深，限制搜索步数
		{
			dfs(0,sx,sy,i);
			if(flag==1)
			{
				printf("%lld
",i);
				kkk=1;
				break;
			}
		}
		if(kkk==0) printf("-1
");
	}
	
	return 0;
}