【搜索】优先队列BFS

【搜索】优先队列BFS


前言#

在讲解优先队列 BFS 之前,让我们回顾一下最普通的走迷宫问题:

对于一个迷宫,从起点开始,对于四周能扩展的点打上标记并加入队列。直到从队列取出来的点表示的位置为终点时,退出搜索

显然,在没有限制的情况下,我们只需要给出一条路径,如果把迷宫看成一个无向图,那么每一条边其实都是边权为一的无向边。但我们如果给每一条边不同的权值,一般的 BFS 就不能解决这个问题了,因为它会在找到一条路径时立刻退出,不能保证最短路径被扩展。实际上这种问题我们可以通过最短路算法求解,而今天我们则尝试用优先队列 BFS 进行求解。

优先队列 BFS#

方法一(不使用优先队列)#

方法一非常暴力,仍然使用一般的广搜——采用一般的队列。

这时我们结束条件要进行更改,因为不能保证每一个状态第一次入队时就是最优解,所以只能允许每一个状态被多次更新多次,多次进出队列。也就是结束条件不再是找到终点,而是一直搜索,直到队列为空(迭代思想)。

此时整个广搜算法对搜索树进行了重复遍历更新,直到“收敛”到最优解。想法很暴力,时间复杂度也很暴力(笑)。在最坏情况下,时间复杂度会从 O(N)增长到 O(N^2)。这跟最短路的Bellmon-Ford 算法差不多(偷懒专用)。

方法二(使用优先队列)#

这里我们把一般队列改成优先队列,相当于一个二叉堆。

我们可以从队列中取出当前代价最小的状态进行扩展(因为当前所有状态中没有比它更优的,所以以后也不会再更新它没有负权边),然后沿这这一条“最优解”道路往下,同时把其他新状态加入优先队列,不断搜索直到队列为空。

类比最短路的Dijkstra 算法,优先队列不像朴素 Dijkstra 一样寻找所有结点,BFS 只会寻找当前有可能为最优解的搜索树结点,其逻辑类似于堆优化的 Dijkstra 算法,都是仅在可能情况下寻找最优解。类似的,在 Dijkstra 算法中,每一个结点只会被扩展一次,时间复杂度为O(N)O(N)。优先队列 BFS 也是如此,当每一个状态第一次从队列中被取出时,就已经得到了从起始状态到该状态的最优解,不管它会不会被再次取出,它已经是最优,我们可以直接跳过。所以在优先队列 BFS 中,每个结点仍然只被扩展过一次,时间复杂度为O(N)O(N),加上维护二叉堆的代价,优先队列 BFS 的时间复杂度为O(NlogN)O(N log N),这与堆优化的 Dijkstra 算法类似。

例题 UVA11367(洛谷评级:紫)#

题目跳转

观察题目,可以发现这是一道优先队列 BFS+DP。因为这一道题目中引入了油量的概念,所以此时distdist数组不再是一维数组,而是一个二维数组,它表示所有城市结点和油量结点的集合。

因此,自然地,我们使用一个结构体NodeNode来表示每个结点,NodeNode包含三个值:crdoil以及cost。其中 crd 是当前城市结点的下标 (我们需要遍历这个城市结点的子城市),oil 是油量下标,代表当前 DP 所存储的油量。cost 则是从起点 S 到此结点的最小花费。同时,我们使用dist[city][fuel]dist[city][fuel]数组来存储被扩展结点的最小 cost。

回顾优先队列 BFS,我们每次取出在当前状态下的最优解——cost 最小的结点,因此我们需要一个小根堆储存NodeNode,以 cost 为比较标准,把 cost 最小的结点放在堆顶,每次取出堆顶元素进行扩展。同样的,因为每次取出的已经是当前结点的最优解(优先队列 BFS 的特性),所以我们可以给此结点打上一个 tag、标记,表示此结点已经被扩展过,无需再次扩展。又因为这个特性,我们无需一直搜索直到队列为空——只要有一次堆顶结点为目标结点,我们就可以直接结束广度优先搜索,返回答案。此时目标结点已经是最小值,无需扩展其他结点。

对于题目的每一个问题,我们都单独进行一次优先队列 BFS,起始状态结点为Node(start,0)Node(start, 0)(忽略 cost)在每个状态(crdoil)(crd,oil)的分支有两条路:

  1. 如果此时 oil 小于汽车油量 C,并且子结点的distdist不是最优 dist[crd][oil+1]>dist[crd][oil]+当地油价dist[crd][oil + 1] > dist[crd][oil] + 当地油价,则添加一个新的可能改变值的结点,扩展到新状态(crdoil+1)(crd,oil + 1),同时给dist[crd][oil+1]dist[crd][oil + 1]赋值为dist[crd][oil]dist[crd][oil]加上当地油价的值。
  2. 对于每一条从城市 crd 出发的边,若边权大小 edge 不超过此时油量 oil(能开过去),并且并且子结点的 dist 不是最优 dist[son][oiledge]>crd结点的costdist[son][oil – edge] > crd结点的cost ,则添加一个新的可能改变值的结点,扩展到新状态(sonoiledge)(son,oil – edge),同时给dist[son][oiledge]dist[son][oil – edge]赋值为 crd 结点的 cost。

我们不断取出当前队列中“花费最少的结点”进行扩展,并且更新distdist的值,直到终点 T 第一次被取出,则停止广度优先搜索,返回 T 的 cost,输出答案。

若直到队列为空也没有取出终点 T,说明没有路可以从起点 S 到终点 T,此时输出 impossible。

下面是示例代码,结合注释应该可以看懂:

C
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
//主要思想:优先队列BFS+DP
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define MAX 2005
using namespace std;
int city, road; //当前的城市数和道路数
int C, S, T; //油量C、起点S和终点T
int head[MAX]; //代表一个城市
int toll[MAX]; //每个城市的油价
int edge[MAX * 10]; //储存边的值
int son[MAX * 10]; //子结点链
int ver[MAX * 10]; //代表有向边
/*
注意我们这里用二维数组存结点
因为我们动态规划时要找出最优
所以油量不同的同城市情况也是一个结点
*/
//dist的第一维是当前城市
//dist的第二维是当前油量
int dist[MAX][105]; //存储最小花费
bool tag[MAX][105]; //标记结点
int tot = 0;
struct Node
{
    int crd; //结点下标
    int oil; //到达此结点耗费的油量
    int cost; //到达此结点的总花费
    //结构体函数,方便我们添加结点
    Node(int c, int o, int t)
    {
        //给结点赋值
        crd = c;
        oil = o;
        cost = t;
    }
    //在优先队列中按所花的钱更少的排序,变成小根堆
    bool operator < (const Node &a) const
    {
        //你不用管a是什么,只把符号倒一下就可以了
        return cost > a.cost;
    }
};
priority_queue<Node> q; //存结点Node的小根堆
//没什么好说的邻接表函数
void add(int u, int v, int w)
{
    edge[++tot] = w;
    ver[tot] = v;
    son[tot] = head[u];
    head[u] = tot;
}
int BFS(int start)
{
    while(!q.empty()) q.pop(); //初始化小根堆q
    memset(dist, 0x3f, sizeof(dist)); //初始化dist
    memset(tag, 0, sizeof(tag)); //初始化tag
    q.push(Node(start, 0, 0)); //把起点推入小根堆
    dist[start][0] = 0; //赋值起点
    /*
    因为每次取出结点时,此结点是当前所有状态的最优解
    所以只要我们取出T结点,就可以马上退出广度优先搜索
    */
    //一直计算直到取出T结点
    while(!q.empty())
    {
        Node now = q.top(); //取出最小的结点
        q.pop(); //移出二叉堆
        if(now.crd == T) return now.cost; //如果取出T结点,直接退出
        if(tag[now.crd][now.oil]) continue; //确保此结点没有被扩展过
        tag[now.crd][now.oil] = true; //标记已经扩展过的结点
        //如果油箱没有满且子结点的dist不是最优,则添加一个新的可能改变值的结点
        if(now.oil < C && dist[now.crd][now.oil + 1] > now.cost + toll[now.crd])
        {
            dist[now.crd][now.oil + 1] = now.cost + toll[now.crd]; //更改此时的结点值
            q.push(Node(now.crd, now.oil + 1, now.cost + toll[now.crd])); //把这个更改过,可能影响下一个子结点的结点入队
        }
        //遍历此结点的子结点
        for(int i = head[now.crd]; i; i = son[i])
        {
            if(now.oil < edge[i]) continue; //如果油量不够开,直接continue
            //如果当前城市的子城市在油量为now.oil – edge[i]的情况不是最优解,则更改
            if(dist[ver[i]][now.oil – edge[i]] > now.cost)
            {
                 dist[ver[i]][now.oil – edge[i]] = now.cost; //更新子城市此时油量的dist
                 q.push(Node(ver[i], now.oil – edge[i], now.cost)); //把这个更改过,可能影响下一个子城市的结点入队
            }
        }
    }
    return -1; //如果队列空了都没能取出T结点,说明没有路可走到T结点
}
int main()
{
    scanf(“%d %d”, &city, &road);
    for(int i = 1; i <= city; i++)
        scanf(“%d”, &toll[i]); //输入当前油价
    for(int i = 1; i <= road; i++)
    {
        int u, v, w;
        scanf(“%d %d %d”, &u, &v, &w);
        u++; v++; //因为我们下标从1开始,这里要把结点下标都加一
        //添加无向边,看成两条重复的有向边
        add(u, v, w);
        add(v, u, w);
    }
    int q;
    scanf(“%d”, &q);
    for(int i = 1; i <= q; i++)
    {
        scanf(“%d %d %d”, &C, &S, &T);
        S++; T++; //因为我们下标从1开始,这里要把起点和终点都加一
        int ans = BFS(S); //开始广度优先搜索
        if(ans == -1) //无解
            printf(“%s\n”, “impossible”);
        else
            printf(“%d\n”,ans);
    }
    return 0;
}