bfs算法进阶

kebingyi · 2020-07-28 12:25:44 · 个人记录

简介

在最基本的广度优先搜索中，每次沿着分支的扩展都记为1步，即每条边的边权均为1。

然而，如果图上的边权一部分为1，另一部分为0呢（如下图所示）？

这是一张边权要么为1，要么为0的无向图。如果用普通的BFS去做的话，当处理到第3层时，队列内会有5个点，step分别为2,1,2,1,0，并不是按从小到大的顺序排的，这可怎么办？

1. 考虑用具有排序功能的数据结构储存节点，如优先队列。这个思路很类似于Dijkstra算法，区别在于排序的依据一个是步数，一个是最短路。

2. 把队列(queue)换成双端队列(deque)，如果当前点u到相邻点v的边权为0，就push\_front(v)；反之，边权为1就push\_back(v)。这样就能保证队列内节点的顺序是按照step从小到大排的了。

一道例题

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
#define Re register
using namespace std;

const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
const int N=2001;

struct Node {
    int x,y;
}Nd;

int T,n,m;
char Map[N][N];
int d[N][N];

void bfs(int bx,int by)
{
    deque<Node> dq;
    Nd.x=bx,Nd.y=by;
    dq.push_back(Nd);
    d[bx][by]=0;
    while(!dq.empty())
    {
        Node P=dq.front();
        dq.pop_front();
        for(Re int i=0;i<4;i++)
        {
            int X=P.x+dx[i],Y=P.y+dy[i];
            if(X>0&&Y>0&&X<=n&&Y<=m)
            {
                int t=(Map[P.x][P.y]!=Map[X][Y]);
                if(d[P.x][P.y]+t<d[X][Y])
                {
                    d[X][Y]=d[P.x][P.y]+t;
                    Nd.x=X,Nd.y=Y;
                    if(!t) dq.push_front(Nd);
                    else dq.push_back(Nd);
                }
            }
        }
    }
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(d,0x3f,sizeof d);
        scanf("%d %d",&n,&m);
        for(Re int i=1;i<=n;i++)
        {
            scanf("%s",Map[i]+1);
        }
        bfs(1,1);
        printf("%d\n",d[n][m]);
    }
    return 0;
}

双向BFS

在一些题目中，问题不但有初态，还有明确的终态，并且从初态开始搜索与从终态开始搜索所产生的搜索树都能够覆盖整个搜索的状态空间。在这种情况下，就可以采用双向搜索，即从初态和终态各搜索一半状态，产生两棵深度较小的搜索树，这两棵搜索树在中间相遇(meet\ in\ the\ middle)，形成最终的答案。

先观察一下上面这张图，这是从初始节点1出发，到终止节点21的BFS状态树。

再观察一下上面这张图，这是同时从初始节点1和终止节点21出发的BFS状态树。

很明显，我们会发现如果同时从初始节点和终止节点出发，并且让它们在中间相遇，这种方法的状态数会少特别多。这便是双向BFS的优势所在。

双向BFS可以将状态数大大减少，但减少的数目不稳定，不过我们可以大致把它估算成 ：O(2^n)→O(2^\frac{n}{2})，减少的状态数也是很可观的。

代码基本结构

q.push(st);
q.push(en);
mark[st]=1;
mark[en]=2;
while(!q.empty())
{
    now=q.front();
    if(mark[now]==1)
    {
        Next=...;
        if(mark[Next]==2) 
        {
            ...(搜索两端碰撞，已找到最优解)
            break;
        }
        mark[Next]=1;
        q.push(Next);
        ...
    }
    if(mark[now]==2)
    {
        Next=...;
        if(mark[Next]==1) 
        {
            ...(搜索两端碰撞，已找到最优解)
            break;
        }
        mark[Next]=2;
        q.push(Next);
        ...
    }
}

A^*算法