To boldly go where no one has gone before.

【学习笔记】启发式搜索

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

以$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)$的目的。

此后,可以重复以下步骤

//  这是 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$短路模板:

#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;
}