第k短路问题

ACM

搜索的瓶颈就是搜索的时间复杂度和空间复杂度。所以有的时候要采取必要的剪枝策略。而剪枝策略中将充满着玄学。
这篇文章主要总结一下A*的思维来解决第k短路问题。

什么是A*算法？

A*详细介绍
前辈们已经说的很清楚了。构造了一个如下的函数:
\(f(x) = g(x)+h(x)\)
g(x)为实际搜索的答案，h(x)为一个启发的因子。
我们一般用的BFS其实就是一种最坏情况的A*算法，\(h(x) = 0;\)
这个函数有很多的应用的背景：比如求最短路的时候，我们搜索到一个状态的时候，然后加上最好的曼哈顿距离(h(x))，这时候的值比已经找到的值要大。那么我们完全没有必要接着往下找最短路了。这样的方案是不可能为最优方案的。

问题

poj2449 Remmarguts’ Date

题意

  • 首先给定n, m:n表示节点的个数，m代表有向图的边。
  • 下面的m行给定从节点u到v的距离dist
  • 最后一行给定起点(s), 终点(t), 第k短路
  • 若s == t,必须在外面经过一些点再返回。

题解

  • 暴力搜索没想好怎么暴力搜索。如果能暴力，时间复杂度也是不行吧。
  • 我们先预处理出来图中所有的点到terminal的最短路,这个来作为h[]函数(启发函数)。
  • 而我们下面要讨论的第k短路问题，是一个不断将可能的解放入优先队列(pq)的过程之中。这些解可能不是最优的，但是由于优先队列的性质，我们取出来的一个是当前最优的结果。
  • 当terminal节点被取出来k次之后，说明这就是第k短路的结果了。

更多的理解和说明

A*其实就是给BFS()的时候加了一个h()函数，h()函数设计的好坏影响着整个的算法的优劣程度。好的h()函数可以极大的介绍搜索的空间。
而且求第k短路的时候看到了一句醍醐灌顶的话：

优先队列相当于把所有的情况都先保存起来，这些解不一定是最优的。不管是骡子还是马，都放进优先队列中。然后从最优的解(队首)开始向外拓展。最后找到第k优的解。

AC代码

其实前面的原理没看懂也没什么，结合下下面的代码，先把terminal当成起始点跑dijkstra，然后用A*算法来枚举所有的可能的解就可以了。

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int max_node = 1e3+10;
const int max_edge = 1e5+10;
int n, m;
const int INF = 1e9;
struct Edge{
    int to, weight, next;
}edge[max_edge], reverse_edge[max_edge];
struct Node{
    int u;
    int h, g;
    bool operator <(Node a) const{
        return a.g+a.h < h+g;
    }
};
int head[max_node];
int head1[max_node];
void add_edge(int u, int v, int weight, int index, Edge edge[], int head[]){
    edge[index].to = v;
    edge[index].weight = weight;
    edge[index].next = head[u];
    head[u] = index;
    return ;
}
int s, t, k;
bool vis[max_node];
int dist_end[max_node];
void Dijkstra(){
    memset(vis, 0, sizeof(vis));
    memset(dist_end, 0x7F, sizeof(dist_end));
    dist_end[t] = 0;
    for(int i=1; i<=n; i++){
        int u = -1;
        int min_dis = INF;
        for(int j=1; j<=n; j++){
            if(!vis[j] && min_dis>dist_end[j]){
                u = j;
                min_dis = dist_end[j];
            }
        }
        if(u == -1) return ;
        vis[u] = true;
        for(int j=head1[u]; j!=-1; j=reverse_edge[j].next){
            int v = reverse_edge[j].to;
            if(!vis[v]){
                dist_end[v] = min(dist_end[v], min_dis+reverse_edge[j].weight);
            }
        }
    }
}
int times[max_node];
int Astar()
{
    priority_queue<Node> pq;
    Node now, temp;
    memset(times, 0, sizeof(times));
    now.u = s;
    now.g = now.h = 0;
    while(!pq.empty()) pq.pop();
    pq.push(now);
    while(!pq.empty()){
        now = pq.top();
        pq.pop();
        times[now.u]++;
        if(times[now.u] == k &&now.u == t)return now.g+now.h;
        if(times[now.u]>k) continue;
        int edge_number = head[now.u];
        while(edge_number != -1){
            int v = edge[edge_number].to;
            temp.u = v;
            temp.g = now.g + edge[edge_number].weight;
            temp.h = dist_end[v];
            edge_number = edge[edge_number].next;
            //printf("%d ", edge_number);
            pq.push(temp);
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        memset(head, -1, sizeof(head));
        memset(head1, -1, sizeof(head1));
        for(int i=0; i<m; i++){
            int u, v, weight;
            scanf("%d%d%d", &u, &v, &weight);
            add_edge(u, v, weight, i, edge, head);
            add_edge(v, u, weight, i, reverse_edge, head1);
        }
        scanf("%d%d%d", &s, &t, &k);
        if(s == t) k++;
        Dijkstra();
        printf("%d\n", Astar());
    }
    return 0;
}

k短路更新

我原来的k短路太慢了。。。
poj上面dij其实是要比这个快的，但是今天没有卡spfa
题目链接

ac code

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0xffffff
#define MAXN 100010
struct node
{
    int to;
    int val;
    int next;
};
struct node2
{
    int to;
    int g,f;
    bool operator<(const node2 &r ) const
    {
        if(r.f==f)
            return r.g<g;
        return r.f<f;
    }
};
node edge[MAXN],edge2[MAXN];
int n,m,s,t,k,cnt,cnt2,ans, len;
int dis[1010],visit[1010],head[1010],head2[1010];
void init()
{
    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    cnt=cnt2=1;
}
void addedge(int from,int to,int val)
{
    edge[cnt].to=to;
    edge[cnt].val=val;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void addedge2(int from,int to,int val)
{
    edge2[cnt2].to=to;
    edge2[cnt2].val=val;
    edge2[cnt2].next=head2[from];
    head2[from]=cnt2++;
}
bool spfa(int s,int n,int head[],node edge[],int dist[])
{
    queue<int>Q1;
    int inq[1010];
    for(int i=0;i<=n;i++)
    {
        dis[i]=INF;
        inq[i]=0;
    }
    dis[s]=0;
    Q1.push(s);
    inq[s]++;
    while(!Q1.empty())
    {
        int q=Q1.front();
        Q1.pop();
        inq[q]--;
        if(inq[q]>n)
            return false;
        int k=head[q];
        while(k>=0)
        {
            if(dist[edge[k].to]>dist[q]+edge[k].val)
            {
                dist[edge[k].to]=edge[k].val+dist[q];
                if(!inq[edge[k].to])
                {
                    inq[edge[k].to]++;
                    Q1.push(edge[k].to);
                }
            }
            k=edge[k].next;
        }
    }
    return true;
}
int A_star(int s,int t,int n,int k,int head[],node edge[],int dist[])
{
    node2 e,ne;
    int cnt=0;
    priority_queue<node2>Q;
    if(s==t)
        k++;
    if(dis[s]==INF)
        return -1;
    e.to=s;
    e.g=0;
    e.f=e.g+dis[e.to];
    Q.push(e);
    while(!Q.empty())
    {
        e=Q.top();
        Q.pop();
        if(e.to==t)//找到一条最短路径
        {
            cnt++;
        }
        if(cnt==k)//找到k短路
        {
            return e.g;
        }
        for(int i=head[e.to]; i!=-1; i=edge[i].next)
        {
            ne.to=edge[i].to;
            ne.g=e.g+edge[i].val;
            ne.f=ne.g+dis[ne.to];
            Q.push(ne);
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        scanf("%d%d%d%d",&s,&t,&k,&len);
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
            addedge2(b,a,c);
        }
        spfa(t,n,head2,edge2,dis);
        int last = A_star(s,t,n,k,head,edge,dis);
        //cout<<last<<endl;
        if(last>len){
            printf("Whitesnake!\n");
        }
        else printf("yareyaredawa\n");
    }
    return 0;
}

参考博客

the kth shortest path
kth shortest path②

未解决的问题

本文标题:第k短路问题

文章作者:Babydragon

发布时间:2017-11-14, 00:31:32

最后更新:2018-09-08, 19:55:23

原始链接:http://baolintian.github.io/2017/11/14/第k短路问题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 什么是A*算法？
  2. 2. 问题
    1. 2.1. 题意
    2. 2.2. 题解
    3. 2.3. 更多的理解和说明
    4. 2.4. AC代码
  3. 3. k短路更新
    1. 3.1. ac code
    2. 3.2. 参考博客
  4. 4. 未解决的问题
{{ live2d() }}