\(IDA^*\) 学习笔记
其实我也是现学现卖,就是觉得本人智商太低,参考了挺多资料才理解 IDA* ,想帮助其他像我一样的菜鸡(虽然我这么菜的可能不多)以及以后自己复习用,把抽象的 IDA* 和本题具体的结合起来,自以为可能更好理解一点qwq
我们用\(g(n)\)表示节点的实际步数,就是已经搜了几步。
\(h(n)\)表示节点的“咕价函数”,顾名思义,咕算大概(从当前节点到终点)还要搜几步, 并且保证实际代价不会比\(h(n)\)更小。 在本题中的体现为当前状态与最终状态有多少个不符的。(对了,这是树剖姐姐告诉窝的,在此鸣谢qwq
然后令
\[f(n)=g(n)+h(n)\]
那么本题的优化就出来了,\(f(n)\)显然是\(≤15\)的,然后搜就好啦!
(其实代码不用看的qwq,懂了思路就直接搜就好啦~
Code
#include<iostream>
#include<cstdio>
using namespace std;
const int inf = 1e9;
int T,ans;
char map[5][5],fin[5][5]=
{
{'1','1','1','1','1'},
{'0','1','1','1','1'},
{'0','0','*','1','1'},
{'0','0','0','0','1'},
{'0','0','0','0','0'}
};
int sx,sy;
int dx[8]={1,1,-1,-1,2,2,-2,-2};
int dy[8]={2,-2,2,-2,1,-1,1,-1};
int f()
{
int cnt=0;
for(int i=0;i<5;++i)
for(int j=0;j<5;++j)
if(map[i][j]!=fin[i][j])
++cnt;
return cnt;
}
void init()
{
string s[5];
for(int i=0;i<5;++i) cin>>s[i];
for(int i=0;i<5;++i)
{
for(int j=0;j<5;++j)
{
map[i][j]=s[i][j];
if(map[i][j]=='*') {sx=j;sy=i;}
}
}
}
void dfs(int x,int y,int fx,int fy,int g)
// (x,y) means the node where I am now, and g means the distance I have gone
{
int h=f();//F=g+h (not f()!!!
if(h+g>16) return;//Bao Xian QwQ
if(g>=ans) return;
if(h==0) {ans=g;return;}
for(int i=0;i<8;++i)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx<0||ny<0||nx>4||ny>4) continue;
if(nx==fx&&ny==fy) continue;//can't go back
swap(map[nx][ny],map[x][y]);
dfs(nx,ny,x,y,g+1);
swap(map[nx][ny],map[x][y]);
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
init();
ans=inf;
dfs(sy,sx,0,0,0);
if(ans==inf) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}