启发式搜索（A*与IDA*）_启发式搜索经典题目

一、A*算法

A* 算法指的是有估价函数优化的bfs。估价函数f(x) （即从当前状态x到终点T的估计代价）需要满足f(x)<=g(x)（g(x)指的是从x到T的真实代价）。

例题1：AcWing 178.第K短路

我们知道：求单源最短路的Dijkstra算法本质上是优先队列bfs，当某个点第一次从堆中取出时，就得到了起点到这个点的最短距离。那么我们很容易得到一个引理：当某个点第k次从堆中取出时，就得到了起点到这个点的k短路。若直接利用该结论求解，时间复杂度上界为O(K(N+M)log(N+M))，会T。但是如果我们采用A*算法，实际复杂度上界的常数会远小于K。由于这题是求第K短路，我们不难想到用x到T的最短路作为估价函数f(x)的值，这样不仅满足估价函数设计的基本原则，还能顺应g(x)的变化。
代码如下:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=1005,M=2e4+5;
int n,m;
int S,T,k;
int h[N],rh[N],ne[M],to[M],w[M],idx;
void add(int h[],int x,int y,int z){
   
    ne[++idx]=h[x];
    to[idx]=y;
    w[idx]=z;
    h[x]=idx;
}
int f[N],cnt[N];
typedef pair<int,int> PII;
bool st[N];
void dijkstra(){
   //在反图上跑dij来预处理出估价函数
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    memset(f,0x3f,sizeof f);
    heap.push({
   0,T});
    f[T]=0;
    while(heap.size()){
   
        PII t=heap.top();
        heap.pop();
        int ver=t.second,d=t.first;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=rh[ver];i;i=ne[i]){
   
            int j=to[i];
            if(f[j]>d+w[i]){
   
                f[j]=d+w[i];
                heap.push({
   f[j],j});
            }
        }
    }
}
typedef pair<int,PII> PIP;
int dist[N];
int Astar(){
   
    dijkstra();//计算估价函数
    priority_queue<PIP,vector<PIP>,greater<PIP> > heap;
    heap.push({
   f[S],{
   0,S}});
    while(heap.size()){
   
        PIP t=heap.top();
        heap.pop();
        int ver=t.second.second,d=t.second.first,fd=t.first;
        cnt[ver]++;
        if(cnt[T]==k) return d;
        for(int i=h[ver];i;i=ne[i]){
   
            int j=to[i];
            if(cnt[j]<k) heap.push({
   d+w[i]+f[j],{
   d+w[i],j}});
        }
    }
    return -1;
}
int main(){
   
    scanf("%d%d",&n,&m);
    while(m--){
   
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(h,x,y,z);
        add(rh,y,x,z);//反图
    }
    scanf("%d%d%d",&S,&T,&k);
    if(S==T) k++;//"路"最少包含一条边
    printf("%d",Astar());
    return 0;
}
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
84
85
86

例题2：AcWing 179.八数码

本题在排序算法一章中利用逆序对数量的奇偶性判定了八数码问题是否有解。但这题要求我们输出一个字典序最小的可行解，那么考虑使用A* 算法实现。
首先要利用逆序对的奇偶性判断询问输入数据是否有解。这样将大大提升效率。因为A*算法不能优化处理无解的情况，其复杂度会降至普通的优先队列bfs的复杂度。
这里很明显是用整个八数码图形作为状态，不断地扩展（这里需要用到STL里的有Hash表功能的unordered_map）。估价函数也比较好设计：直接取出当前状态上每一个数的坐标及其对应在最终状态上的数的坐标，计算每一个数的曼哈顿距离，求和即可。这个设计方法显然是正确的。设计思路很简单，关键在于代码实现：
P.S.:unordered_map的用法：
定义：
unordered_map<数组下标类型,数组值类型>

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<unordered_map>
using namespace std;
int f(string state){
   
    int res=0;
    for(int i=0;i<9;i++){
   
        if(state[i]!='x'){
   
            int t=state[i]-'1';
            res+=abs(i/3-t/3)+abs(i%3-t%3);
        } 
    }
    return res;
}
typedef pair<int,string> PIS;
unordered_map<string,int> dist;
unordered_map<string,bool> st;
unordered_map<string,pair<char,string>> pre;
priority_queue<PIS,vector<PIS>,greater<PIS> > heap;
int dx[4]={
   -1,1,0,0},dy[4]={
   0,0,-1,1};
char op[5]="udlr";
string bfs(string start){
   
    string end="12345678x";
    heap.push({
   f(start),start});
    dist[start]=0;
    while(heap.size()){
   
        PIS t=heap.top();
        heap.pop();
        string ver=t.second;
        int d=t.first;
        if(ver==end) break;
        if(st[ver]) continue;
        st[ver]=true;
        int x,y;
        for(int i=0;i<9;i++){
   
            if(ver[i]=='x'){
   
                x=i/
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