@[Mon3_ter](/user/1025259)
估价函数是在启发式搜索中对当前状态与答案距离的估计。设计估价函数的目的是为了帮助搜索算法更准确的找到答案，而不是盲目的随便搜索（估价可以意识到某些搜索方法正在远离答案，以停止这部分的搜索）。
估价函数的设计需要从快捷性和准确定两方面考虑。
快捷性：估价函数必须要足够快，且尽量不要使用多余内存空间。否则如果一位进行估价造成程序运行速度大幅度变慢就不好了。
准确性：在保证快捷性的基础上尽量准确，在进行迭代加深搜索时必须保证估价值不比真实值大，否则可能无解
by robertuu @ 2023-10-05 20:34:17
当然，估价函数肯定是越准确越好
by robertuu @ 2023-10-05 20:36:00
```cpp
#include<bits/stdc++.h>
using namespace std;
char ed[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'}
},a[5][5];
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};
int dep,x,y,res;
int gj()
{
int ans=0;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
{
if(a[i][j]=='*'){
x=i;
y=j;
}
if(a[i][j]!=ed[i][j]) ++ans;
}
return ans;
}
bool dfs(int now)
{
int cnt=gj(),nowx=x,nowy=y;
if(now+cnt>dep+3) return 0;
if(!cnt)
{
res=min(res,now);
return 1;
}
for(int i=0;i<8;i++)
{
int nx=nowx+dx[i],ny=nowy+dy[i];
if(nx<0||nx>4||ny<0||ny>4) continue;
swap(a[nowx][nowy],a[nx][ny]);
if(dfs(now+1)) return 1;
swap(a[nowx][nowy],a[nx][ny]);
}
return 0;
}
signed main()
{
std::ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--)
{
res=1e9;dep=0;
for(int i=0;i<5;i++) cin>>a[i];
while(dep<=15&&!dfs(0)) ++dep;
if(res>=16) cout<<-1<<'\n';
else cout<<res<<'\n';
}
}
```
这样写比较有容错性，就是如果不知道应该到那里时加一个<=3或2的数。记录中间结果而不以深度作答案。
~~很没有创意看来~~
by Kopicy_sama @ 2023-10-05 20:40:49