继续来学启发式搜索

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

例题

洛谷上的p2324骑士精神

题目描述

主要就是说有个空格，然后所有马都走日，没有马脚，只能跳到空格里面去，然后问你是否能在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;
}

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