搜索专题——A*算法_a*算法例题

什么是A*算法？

A*算法是一种结合了启发函数的宽搜算法，当搜索空间巨大时，我们可以为宽搜加上一个启发函数，来降低搜索的时空复杂度。

A*算法的原理是什么？

在A*算法中：

定义 $F(n)$ 为搜索树上节点的估计函数，我们根据估价的大小选择节点扩展的优先级（例如，在K短路算法中，估价值越小，越优先）

定义 $G(n)$ 为根节点到每个节点的实际代价值（例如，在K短路算法中，该函数的意义为起始点到每个点的路径长度）

定义 $H(n)$ 为当前节点到目标节点的一个启发式估计值，作为我们优化宽搜的一个关键参考（例如，在K短路算法中，该函数的意义为当前节点到目标节点的最短距离）

因此：$$F(n)=G(n)+H(n)$$

Attention1：启发函数唯一的作用，只是改变了状态的搜索顺序，优先搜索最有可能趋近于答案的状态，从而减小搜索空间

Attention2：启发函数必须要可采纳，什么样的启发函数是可采纳的呢？即启发函数的值必须要小于等于当前节点到目标节点的一个实际值（简单理解一下，如果启发函数值大于实际值，则启发函数反而帮了倒忙，可能会造成错误，我们宁可使用朴素算法，也不能出现错误）

Attention3：启发函数的选择很重要，在可采纳的前提下，一个启发函数越相似于真实值，越有效。

例题1：K短路

注解1：首先不考虑时间和空间，我们怎样求解K短路？

在Dijkstra中，我们用 $st[ver]$ 数组控制节点的扩展次数，由贪心思想可知，当节点第一次出堆时，此时一定时最短路（可以用贪心的思想简单理解一下，严格的数学证明可以啃算导，好像是数学归纳法证明）。同理，我们去掉 $st$ 数组，允许一个节点多次扩展，则节点第 $K$ 次出堆就是 $K$ 短路（也可以用贪心思想理解，即当前的路径值是非减的（无负权前提），初学者没必要花大量时间去严格证明）

注解2：求解K短路用启发函数优化的合理性是什么？
为什么加上这个启发函数能够保证正确性？首先，我们选取当前节点到目标节点的距离作为启发函数，根据启发函数的可采纳性，我们知道这样是正确的。还是不放心？那我们结合本题来想象一个场景：我们可以根据时间顺序，把出堆的节点从前到后排成一排，则对于其中的 $T$ 节点（所有的 $H(T)=0$），则前面的 $T$ 节点的 $G(T)$ 的值一定小于等于后面的，所以一定是 $K$ 短路。

注解3：看了好多题解，以及算法进阶指南上的剪枝说法也是错的（即非终点节点扩展K次后不再扩展，这种做法是错的，不用严格证明，简单理解一下也感觉没得科学性，也是宁缺勿错）

注解4：所以本题，在反图上跑Dijkstra，用终点到当前节点的距离作为启发函数。

易错点：
1.当 $S==T$ 时，根据题目要求要 $K++$
2.当 $S$ 与 $T$ 之间不连通时，要特判，否则死循环
3.由于启发函数只是针对 $T$ 节点的，所以别的出堆次数并不能反映其的 $K$ 短路情况！！！（而朴素算法是可以的）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>

#define me(x,y) memset(x,y,sizeof x)
#define rep(i,x,y) for(i=x;i<=y;++i)
#define lowbit(x) -x&x
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define cu(x) cout<<x<<"--"<<endl
#define ex exit(0)
#define pn puts("")

using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> vc;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

struct edge
{
    int to,nxt,val;
};

struct pii
{
    int tag,fx,gx;  //fx为估价值，gx为从起点到当前点的真实值，fx=gx+hx
};

bool operator>(const pii& z1,const pii& z2)         //注意，小根堆要重载大于号
{
    if(z1.fx==z2.fx)    return z1.gx>z2.gx;
    return z1.fx>z2.fx;
}

const int N =1010,M=2e4+10;
int n,m,s,t,k,idx;

int head[N],headf[N];
edge table[M];          //有向边，但是要建立反向图
int dist[N];            //dijkstra跑的反向图
bool st[N];

inline void add(int head[],int& u,int& v,int& w)
{
    table[++idx].nxt=head[u];
    head[u]=idx;
    table[idx].to=v;
    table[idx].val=w;
}

void dijkstra()
{
    int u,v,e,w;
    
    priority_queue<PII,vector<PII>,greater<PII>>q;
    me(dist,0x3f);
    dist[t]=0;
    q.push(PII{0,t});
    
    while(!q.empty())
    {
        auto x=q.top();
        q.pop();
        u=x.second;
        
        if(st[u])   continue;
        st[u]=true;
        
        for(e=headf[u];e;e=table[e].nxt)
        {
            v=table[e].to;
            w=table[e].val;
            
            if(dist[v]>dist[u]+w)
            {
                dist[v]=dist[u]+w;
                q.push(PII{dist[v],v});
            }
        }
    }
}

int A_star()
{
    int u,v,e,w,cnt=0;
    
    if(dist[s]==inf)    return -1;
    
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({s,dist[s],0});
    
    while(!q.empty())
    {
        auto x=q.top();
        q.pop();
        u=x.tag,w=x.gx;
        
        if(u==t)    ++cnt;
        if(cnt==k)  return w;
        
        for(e=head[u];e;e=table[e].nxt)
        {
            v=table[e].to;
            q.push({v,w+table[e].val+dist[v],w+table[e].val});
        }
    }
    
    return -1;
}

int main()
{
    int i,u,v,w;
    
    n=read(),m=read();
    rep(i,1,m)
    {
        u=read(),v=read(),w=read();
        add(head,u,v,w);
        add(headf,v,u,w);
    }
    s=read(),t=read(),k=read();
    if(s==t)    ++k;
    
    dijkstra();
    printf("%d",A_star());
	
	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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145