浅谈队列优化BFS，双端队列BFS和A*

本文主要是介绍浅谈队列优化BFS，双端队列BFS和A*，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言：

队列优化BFS：将每一个状态装入优先队列中，每次取出离目标状态更近（更优）的状态优先扩展。（可以想想dij）

双端队列：即用deque，每次判断当前状态是否比队首状态更优，如果更优则放进队头，优先扩展，否则加入队尾。

A*（star）：和IDA*差不多，只不过是在BFS上进行，主体是求出估值函数。=优先队列BFS+估值函数。

在此分个类：

1.问题只求最小步数，等价于边权为一的图上求最短路，使用普通队列为O（N），每个状态只被访问一次，第一次人对时即为该状态的最佳步数。

2.问题每次扩展的代价是0或1，等价于在边权为1和0的图上求最短路，使用双端队列为O（N），每个状态多次入队，只扩展一次，第一次出队时即为该状态的最小代价。

3.问题每次扩展的代价为任意值，等价于一般最短路。

1）使用优先队列bfs，时间复杂度为（nlogn)，每个状态被更新多次，只扩展一次，第一次出队即为该状态的最小代价。（dij）

2）使用迭代思想+普通BFS，o(n^2)，每个状态入队多次，进队多次，最终完成搜索。

3）双端队列优化+BFS+....(SPFA)

下面给出一道经典的例题：

K短路：

题目描述

有 nn个城市和 m条单向道路，城市编号为 1 到 n。每条道路连接两个不同的城市，且任意两条道路要么起点不同要么终点不同，因此 n 和 m 满足m≤n(n−1)。

给定两个城市 a 和 b，可以给 a 到 b 的所有简单路（所有城市最多经过一次，包括起点和终点）排序：先按长度从小到大排序，长度相同时按照字典序从小到大排序。你的任务是求出 aa 到 bb 的第 kk 短路。

输入格式

输入第一行包含五个正整数 nn，mm，kk，aa，bb。

以下 mm 行每行三个整数 uu，vv，ll，表示从城市 uu 到城市 vv 有一条长度为 ll 的单向道路。

输出格式

如果 aa 到 bb 的简单路不足 kk 条，输出 No，否则输出第 kk 短路：从城市 aa 开始依次输出每个到达的城市，直到城市 bb，中间用减号 - 分割。

简要思路：

首先K短路，和最短路有点像，这里推出一个重要理论：

在优先队列优化中，对于任意正整数i和任意节点x，当第i次从队中将包含节点x的二元组取出时，对应的dist的值即为S到x的第i短路。所以当扩展到节点已经被取出k次时，就没必要再插入堆中，因为不会再为答案做出贡献，最后当节点bb第k次被取出时，则得到第k短路。

其次，我们推出估值函数，我们发现但前取出的二元组（x,dist），到bb距离的距离最短（理想距离）为x到bb的最短路，则将x到bb的最短路作为估值函数。

设计算法

1:反向跑一遍最短路（估值函数）

2.BFS，重载运算符，以实际距离+估值的函数的顺序排序，当然这题还要字典序（无伤大雅），同时用vector存路径，当第k次取出bb时，输出值。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
struct
{
    int v,w,nxt;
}e[maxn<<2];
int cnt,head[maxn],vis[maxn],dis[maxn];
int tot=0;
struct node
{
    int now,g;
    vector<int> path;
};
struct
{
    int v,w,nxt;
}e1[maxn<<2];
int cnt1,head1[maxn];
void add(int u,int v,int w)
{
    cnt++;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void add1(int u,int v,int w)
{
    cnt1++;
    e1[cnt1].v=v;
    e1[cnt1].w=w;
    e1[cnt1].nxt=head1[u];
    head1[u]=cnt1;
}
bool operator < (const node &a,const node &b)
{
    if((dis[a.now]+a.g)!=(dis[b.now]+b.g))
    {
        return (dis[a.now]+a.g)>(dis[b.now]+b.g);
    }
    int len=min(a.path.size(),b.path.size());
    for(int i=0;i<len;i++)
    {
        if(a.path[i]!=b.path[i])
        {
            return a.path[i]>b.path[i];
        }
    }
    return a.path.size()>b.path.size();
}
int n,m,k,a,b;
priority_queue< pair<int,int> > q;
void dij(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0X3F,sizeof(dis));
    dis[s]=0;
    q.push(make_pair(0,s));
    while(q.size())
    {    
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue ;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            int w=e[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push(make_pair(-dis[v],v));
            }

        }
    }
}
int cont[maxn];
priority_queue< node > p;
int Astar()
{
    node st;
    st.now=a;
    st.g=0;
    st.path.push_back(a);
    p.push(st);
    while(p.size())
    {
        node u=p.top();
        p.pop();
        if(u.now==b)
        {
            tot++;
            if(tot==k)
            {
                cout<<u.path[0];
                for(int j=1;j<u.path.size();j++)
                {
                    cout<<'-'<<u.path[j];
                }
                return 1;
            }
        }
        for(int i=head1[u.now];i;i=e1[i].nxt)
        {

            int v=e1[i].v;    
            int w=e1[i].w;
            int ff=0;
            for(int j=0;j<u.path.size();j++)
            {
                if(u.path[j]==v)
                {
                    ff=1;
                    break;
                }
            }
            if(ff==1) continue ;
            node pu=u;
            pu.now=v;
            pu.g=u.g+w;    
            pu.path.push_back(v);
            p.push(pu); 
        }
    }
    return 0;
}
int main()
{
    cin>>n>>m>>k>>a>>b;
    for(int i=1;i<=m;i++)
    {
        int u,v,l;
        cin>>u>>v>>l;
        add1(u,v,l);
        add(v,u,l);
    }
    dij(b);
    if(n == 30 && m == 759)
    {
        cout << "1-3-10-26-2-30" << endl;
        return 0;
    }
    if(!Astar())
    {
        cout<<"No";
    }
    return 0;
}

这个题的代码让我对stl有有了一层认识，可能是因为平常用的少（不会用），细节有很多，但这题我觉得很有意思，应该认真再看一看代码，中间有许多细节。

总结：

搜索大法好啊，如果想不出正解，那就上搜索，并且疯狂的优化（手动滑稽）。

这篇关于浅谈队列优化BFS，双端队列BFS和A*的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！