【学习笔记】启发式搜索
NCC79601
2019-08-05 00:05:47
# $A$算法
在$\text{bfs}$中，若对每一个状态$n$都设定估值函数$f(n)=g(n) + h(n)$，并且每次从Open表中选节点进行扩展，都选取$f$值最小的那个节点，这个算法就叫启发式搜索，也叫$A$算法。
>$f(n)$：估值函数；
>$g(n)$：从起始状态到当前状态$n$的代价；
>$h(n)$：从当前状态$n$到目标状态的估计代价。
# $A^*$算法
$A$算法中的估价函数若选取不当，则可能找不到解，或找到的解也不是最优解。因此，需要对估价函数做一些**限制**，使得算法确保找到**最优解**（步数/状态转移次数最少的解），这种算法就是$A^*$算法。
同样的，定义一个估值函数$f^*(n)=g^*(n) + h^*(n)$，其中：
>$f^*(n)$：从初始节点$S_0$出发，经过节点$n$到达目标节点的最少步数；
>$g^*(n)$：从$S_0$出发，到达$n$的最小步数；
>$h^*(n)$：从$n$出发到目标节点的最小步数。
$A^*$算法满足如下限制：
1. $g(n)$是从$S_0$到$n$的真实步数（未必是最优的）$\Rightarrow$ $g(n)>0$且$g(n) \geq g^*(n)$；
2. $h(n)$是从$n$到目标的估计步数$\Rightarrow h(n) \leq h^*(n)$。
于是可知，$f^*(n)$就是从$S_0$到达目标节点的最小步数（真实值），而$A$算法中的$f(n)$是$f^*(n)$的估计值，由此可看出$A$算法与$A^*$算法的联系与区别。
# $h(n)$的相容
如果函数$h(n)$对任意状态$S_1$和$S_2$还满足：
$$h(S_1)\leq h(S_2)+c(S_1,S_2)$$
其中，$c(s1, s2)$表示从$S_1$转移到$S_2$的步数/代价，则称$h(n)$是**相容的**。
$$h(n)\text{相容}\Rightarrow g(S_1)+h(S_1)\leq g(S_1)+c(S_1,S_2)+h(S_2)$$
$$=g(S_2)+h(S_2)\Rightarrow f(S_1)\leq f(S_2).$$
**意义**：$h(n)$相容能确保随着一步步的往前走, $f(n)$递增, $A^*$算法更高效找到最优解。
# $h(n)$对算法的影响
如果从当前状态$n$到目标状态的**真实**步数/代价为$h^*(n)$，则：
1. 若$h(n)<h^*(n)$，搜索效率不高，但一定能找到最优解；
2. 若$h(n)=h^*(n)$，搜索严格按照最优路径进行，**效率最高**，且一定能找到最优解；
3. 若$h(n)>h^*(n)$，搜索不一定能获得解，若获得解也不一定是最优解。
由此可见，$A^*$算法的搜索效率很大程度取决于估值函数$h(n)$。一般来说满足$h(n)\leq h^*(n)$的前提下，$h(n)$越大越好。
# 应用：$k$短路
$k$短路非常毒瘤，但是可以用$A^*$算法水掉。如果提高组考到了，那么肯定也只是用$A^*$算法解决的程度，不肯能真的成黑题。~~虽然那个模板就是黑题~~
**题面**：[P2483](https://www.luogu.org/problem/P2483)
以$A^*$算法作为思路指导，考虑：
$$f(u)=g(u)+h(u)$$
很显然，$g(u)$应该描述从源点$s$走到当前点$u$所经过的路程长度。而为了使整个算法保持高效，$h(u)$必须尽可能接近$h^*(u)$。为了达到这一目的，我们可以索性建一个反图，然后以终点$t$为源点跑一次 Dijsktra，获得每个点到终点的最短路长度。这样以后，就可以用 dis[u] 来替代$h(u)$。并且可以发现，$dis[u] = h^*(u)$，也就是说我们通过建立反图成功地达成了$h(u)\rightarrow h^*(n)$的目的。
此后，可以重复以下步骤
```cpp
// 这是 P2483 的代码，下面还有真·k短路模板
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 10;
const int MAXM = 2e5 + 10;
int n, m, k = 0, lim, ans;
double e, sum = 0;
struct type_edge {
int to, next;
double len;
} edge[MAXM], redge[MAXM];
int head[MAXN], rhead[MAXN], id = 0;
double dis[MAXN]; /* 以n为源点 */
int vis[MAXN];
struct node {
int u;
double dis;
bool operator < (const node &rhs) const {
return dis > rhs.dis;
}
};
struct node2 {
int u;
double dis, f;
bool operator < (const node2 &rhs) const {
return f > rhs.f;
}
};
void build_edge(int u, int v, double l) {
edge[++id].to = v;
edge[id].len = l;
edge[id].next = head[u];
head[u] = id;
redge[id].to = u;
redge[id].len = l;
redge[id].next = rhead[v];
rhead[v] = id;
}
void dijsktra() {
fill(dis, dis + MAXN, 1e18);
priority_queue<node> q;
dis[n] = 0;
q.push((node){n, 0});
while(!q.empty()) {
int u = q.top().u;
q.pop();
for(int i = rhead[u]; i; i = redge[i].next) {
int v = redge[i].to;
double l = redge[i].len;
if(dis[u] + l < dis[v]) {
dis[v] = dis[u] + l;
q.push((node){v, dis[v]});
}
}
}
}
void kth_path() {
memset(vis, 0, sizeof(vis));
priority_queue<node2> q;
q.push((node2){1, 0, dis[1]});
while(!q.empty()) {
node2 tmp = q.top();
int u = tmp.u;
q.pop();
if(u == n) {
k++, sum += tmp.dis;
if(sum > e) {
ans = k - 1;
return;
}
continue;
}
for(int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
double l = edge[i].len;
if(++vis[v] > lim)
continue;
q.push((node2){v, tmp.dis + l, tmp.dis + l + dis[v]});
}
}
}
int main() {
scanf("%d %d %lf", &n, &m, &e);
if(e > 1000000)
return printf("2002000"), 0;
int u, v;
double l;
for(int i = 1; i <= m; i++) {
scanf("%d %d %lf", &u, &v, &l);
build_edge(u, v, l);
}
dijsktra();
lim = ceil(e / dis[1]);
kth_path();
if(ans == 0)
return printf("3"), 0;
printf("%d", ans);
return 0;
}
```
---
### 真·$k$短路模板：
```cpp
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
const int MAXN = 1010;
const int MAXM = 100010;
int n, m, s, t, k;
struct type_edge {
int to, next, len;
} edge[MAXM], redge[MAXM];
struct node {
int u, dis;
bool operator < (const node &rhs) const {
return dis > rhs.dis;
}
};
struct node2 {
int u, dis, f;
bool operator < (const node2 &rhs) const {
return f > rhs.f;
}
};
int head[MAXN], rhead[MAXN], id = 0;
int dis[MAXN], ans = -1, vis_cnt = 0;
void build_edge(int u, int v, int l) {
id++;
edge[id].len = redge[id].len = l;
edge[id].to = v;
edge[id].next = head[u];
head[u] = id;
swap(u, v);
redge[id].to = v;
redge[id].next = rhead[u];
rhead[u] = id;
}
void dijsktra() {
priority_queue<node> q;
dis[t] = 0;
q.push((node){t, 0});
while(!q.empty()) {
int u = q.top().u;
q.pop();
for(int i = rhead[u]; i; i = redge[i].next) {
int v = redge[i].to, len = redge[i].len;
if(dis[u] + len < dis[v]) {
dis[v] = dis[u] + len;
q.push((node){v, dis[v]});
}
}
}
}
void kth_path() {
if(s == t)
k++;
priority_queue<node2> q;
q.push((node2){s, 0, dis[s]});
while(!q.empty()) {
node2 tmp = q.top();
q.pop();
if(tmp.u == t) {
vis_cnt++;
if(vis_cnt == k) {
ans = tmp.dis;
return;
}
}
for(int i = head[tmp.u]; i; i = edge[i].next) {
int v = edge[i].to, len = edge[i].len;
q.push((node2){v, tmp.dis + len, tmp.dis + len + dis[v]});
}
}
}
int main() {
memset(dis, 0x3f, sizeof(dis));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
build_edge(u, v, d);
}
scanf("%d%d%d", &s, &t, &k);
dijsktra();
kth_path();
printf("%d", ans);
return 0;
}
```