继续来学启发式搜索

多的其实没啥好讲了的,因为概念问题在前一篇博文已经讲的很清楚了。主要就是训练寻找估值函数,多点题目练习能应对不通场景下的启发式搜索。

例题

洛谷上的p2324骑士精神

题目描述

1

主要就是说有个空格,然后所有马都走日,没有马脚,只能跳到空格里面去,然后问你是否能在15步以内达到。如果可以则输出最短步数,否则输出-1,因为空格只有一个我们不考虑跳马,考虑跳空格。

递归最大深度15层能确定了,但是任意一个状态可以延伸出最少2中最多八种情况。15作为指数时间上还是遭不住,考虑启发式搜索。那么估值函数需要怎么写呢?

估值函数

这里再补充点估值函数的知识。

f(n)=g(n)+h(n)

估值函数一般表达式如上,g(n)为当前状态,h(n)为未来最优状态产生的花费,或者是其它。估值函数为两者和,由于当前状态我们很容易获取,所以算出未来最优状态即可等于获得了估值函数。可能前面讲的有点小问题,但是还是不妨碍的,因为我们平时写也基本是

1
2
3
if(f(n)+value>ans){
dfs(n+1);
}

所以问题不大。

题目分析

在本题中,我们的估值函数应该是算能到达目的状态的最小步数。那么这个怎么去考虑呢,其实可以拿当前状态与目标状态相比较,如果有两个点不符合目标状态,那么它们最优能达成目标状态一定是1,这里的最优指的是所有的这个情况下能达成目的状态的最小值。因为如果两个不符合的点不形成“日”字的关系,那么它们可能就不止需要1步了,但是估值并不是真的去计算真正的实际情况,估值函数需要尽可能的方便计算,这点很重要。

那么如果我们有三个点不一样那情况如何呢?那考虑最好的情况那还得是2步解决。所以我们很容易可以发现,假如当前状态与目标状态有n个点不一样,那么它最少需要n-1步来完成。

所以我们很容易可以写出估值函数

1
2
3
4
5
6
7
int f(){
int tot=0;
for(int i=0;i<25;i++){
tot+=!!(qipan[i/5][i%5]^goal[i/5][i%5]);
}
return tot;
}

当估值函数返回-1的时候说明当前已经符合目标状态了,那么这个将作为搜索终止条件,并更新最优解。

剩下的就是终归中距的dfs了。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
int goal[5][5]={
1,1,1,1,1,
0,1,1,1,1,
0,0,2,1,1,
0,0,0,0,1,
0,0,0,0,0
};
int qipan[5][5];
int dx[]={-2,-2,-1,-1,1,1,2,2},dy[]={-1,1,-2,2,-2,2,-1,1};
int ans=0x7fffffff;
int f(){
int tot=0;
for(int i=0;i<25;i++){
tot+=!!(qipan[i/5][i%5]^goal[i/5][i%5]);
}
return tot;
}
void search(int x,int y,int step){
//printf("1");
if(step>15)return ;
if(!f()){
ans=min(ans,step);
return ;
}
for(int i=0;i<8;i++){
int new_x=x+dx[i],new_y=y+dy[i];
if(new_x<0||new_x>=5||new_y<0||new_y>=5)continue;
swap(qipan[new_y][new_x],qipan[y][x]);
if(step+f()<=min(ans,15)){
search(new_x,new_y,step+1);
}
swap(qipan[new_y][new_x],qipan[y][x]);
}
}

void solve(){
string s;
int start_x,start_y;
ans=0x7fffffff;
for(int i=0;i<5;i++){
cin>>s;
for(int j=0;j<5;j++){
switch(s[j]){
case '0':
;
case '1':
qipan[i][j]=s[j]-'0';
break;
case '*':
qipan[i][j]=2;
start_x=j;
start_y=i;
break;
default:
;
perror("input error");
exit(0);
}
}
}
search(start_x,start_y,0);
if(ans==0x7fffffff){
printf("-1\n");
}
else{
printf("%d\n",ans);
}
}


int main(){
int t;
cin>>t;
getchar();
while(t--){
solve();
}
return 0;
}

好像不开氧气优化会被卡掉,我只能%氧气优化了,因为我实在不知道咋优化了。