一种启发式搜索
和暴搜的差别是多了一个估值函数,每次取出一个估算最优的状态以期更高效完成任务
重点在于估值函数 \(\text{h*(n)}\) 的设计,若实际代价为 \(\text{h(n)}\),则
若 \(\text{h*(n)=h(n)}\),设计得非常好
若 \(\text{h*(n)<h(n)}\),跑得更快,只是可能搜不出来正确答案
若 \(\text{h*(n)>h(n)}\),慢是慢些,但正确性还有保证
例如 \(k\) 短路
暴搜的话就是找出所有路径,取第 \(k\) 短
但实际上若精准预估当前状态到终止状态的代价,每次取出最小代价状态,
那么 \(k\) 次到达终止状态后,前 \(k\) 短路就已经被搜出来了
显然,估值函数就定为当前状态到终止状态的最短路
这个可以反向建图 \(\text{dijkstra}\) 预处理
P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院
\(\text{code}\)
#include <cstdio> #include <queue> #define RE register #define IN inline using namespace std; const int N = 5005, M = 2e5 + 5, INF = 1e18; int n, m, cnt[N]; double e; struct node{ int id; double f, v; bool operator < (const node &c) const{return f > c.f;} }; priority_queue<node> Q; struct graph{ struct edge{int to, nxt; double w;}e[M]; int tot, h[N], vis[N]; double dis[N]; IN void add(int u, int v, double w){e[++tot] = edge{v, h[u], w}, h[u] = tot;} IN void getdis() { for(RE int i = 1; i < n; i++) dis[i] = INF, vis[i] = 0; vis[n] = 0, Q.push(node{n, 0}); while (!Q.empty()) { node x = Q.top(); Q.pop(); if (vis[x.id]) continue; vis[x.id] = 1; for(RE int i = h[x.id]; i; i = e[i].nxt) { int v = e[i].to; if (dis[v] > dis[x.id] + e[i].w) Q.push(node{v, dis[v] = dis[x.id] + e[i].w}); } } } }e1, e2; int main() { scanf("%d%d%lf", &n, &m, &e); int u, v; double w; for(RE int i = 1; i <= m; i++) scanf("%d%d%lf", &u, &v, &w), e1.add(u, v, w), e2.add(v, u, w); e2.getdis(), Q.push(node{1, 0}); int k = (int)e / e2.dis[1], ans = 0; while (!Q.empty()) { node x = Q.top(); Q.pop(); ++cnt[x.id]; if (x.id == n) { e -= x.v; if (e <= 0){printf("%d\n", ans); return 0;} ++ans; } for(RE int i = e1.h[x.id]; i; i = e1.e[i].nxt) { int v = e1.e[i].to; if (cnt[v] < k && x.v + e1.e[i].w + e2.dis[v] <= e) Q.push(node{v, x.v + e1.e[i].w + e2.dis[v], x.v + e1.e[i].w}); } } printf("%d\n", ans); }
P2901 [USACO08MAR]Cow Jogging G
\(\text{code}\)
#include <cstdio> #include <queue> #define RE register #define IN inline typedef long long LL; using namespace std; const int N = 1005, M = 2e5 + 5, INF = 1e9; int n, m, k, cnt[N]; struct node{ int id; LL f, v; bool operator < (const node &c) const{return f > c.f;} }; priority_queue<node> Q; struct graph{ struct edge{int to, nxt, w;}e[M]; int tot, h[N], vis[N]; LL dis[N]; IN void add(int u, int v, int w){e[++tot] = edge{v, h[u], w}, h[u] = tot;} IN void getdis() { for(RE int i = 2; i <= n; i++) dis[i] = INF, vis[i] = 0; vis[1] = 0, Q.push(node{1, 0}); while (!Q.empty()) { node x = Q.top(); Q.pop(); if (vis[x.id]) continue; vis[x.id] = 1; for(RE int i = h[x.id]; i; i = e[i].nxt) { int v = e[i].to; if (dis[v] > dis[x.id] + e[i].w) Q.push(node{v, dis[v] = dis[x.id] + e[i].w}); } } } }e1, e2; int main() { scanf("%d%d%d", &n, &m, &k); for(RE int i = 1, u, v, w; i <= m; i++) scanf("%d%d%d", &u, &v, &w), e1.add(u, v, w), e2.add(v, u, w); e2.getdis(), Q.push(node{n, 0}); int sum = 0; while (!Q.empty()) { node x = Q.top(); Q.pop(); ++cnt[x.id]; if (x.id == 1) { printf("%d\n", x.v), ++sum; if (sum == k) return 0; } for(RE int i = e1.h[x.id]; i; i = e1.e[i].nxt) { int v = e1.e[i].to; if (cnt[v] < k) Q.push(node{v, x.v + e1.e[i].w + e2.dis[v], x.v + e1.e[i].w}); } } for(RE int i = sum; i < k; i++) printf("-1\n"); }