本篇深入讲解双向广搜、BFS+优先队列、BFS+双端队列的算法思想和应用。
*本文内容由罗勇*老师提供。01
双向广搜
1.双向广搜的原理和复杂度分析
双向广搜的应用场合：有确定的起点和终点，并且能把从起点到终点的单个搜索，变换为分别从起点出发和从终点出发的“相遇”问题，可以用双向广搜。
从起点s（正向搜索）和终点t（逆向搜索）同时开始搜索，当两个搜索产生相同的一个子状态v时就结束。得到的s-v-t是一条最佳路径，当然，最佳路径可能不止这一条。注意，和普通BFS一样，双向广搜在搜索时并没有“方向感”，所谓“正向搜索”和“逆向搜索”其实是盲目的，它们从s和t逐层扩散出去，直到相遇为止。与只做一次BFS相比，双向BFS能在多大程度上改善算法复杂度？下面以网格图和树形结构为例，推出一般性结论。（1）网格图。用BFS求下面图中两个黑点s和t间的最短路。左图是一个BFS；右图是双向BFS，在中间的五角星位置相遇。▍图1网格图搜索
设两点的距离是k。左边的BFS，从起点s扩展到t，一共访问了2k(k+1)≈2k2个结点；右边的双向BFS，相遇时一共访问了约k2个结点。两者差2倍，改善并不明显。
在这个网格图中，BFS扩展的第k和第k+1层，结点数量相差(k+1)/k倍，即结点数量是线性增长的。（2）树形结构。
▍图2二叉树搜索
以二叉树为例，求根结点s到最后一行的黑点t的最短路。左图做一次BFS，从第1层到第k-1层，共访问1+2+...+2k?1≈2k个结点。右图是双向BFS，分别从上往下和从下往上BFS，在五角星位置相遇，共访问约2×2k/2个结点。双向广搜比做一次BFS改善了2k/2倍，优势巨大。在二叉树的例子中，BFS扩展的第k和第k+1层，结点数量相差2倍，即结点数量是指数增长的。从上面2个例子可以得到一般性结论：（1）做BFS扩展的时候，下一层结点（一个结点表示一个状态）数量增加越快，双向广搜越有效率。（2）是否用双向广搜替代普通BFS，除了（1）以外，还应根据总状态数量的规模来决定。双向BFS的优势，从根本上说，是它能减少需要搜索的状态数量。有时虽然下一层数量是指数增长的，但是由于去重或者限制条件，总状态数并不多，也就没有必要使用双向BFS。例如后面的例题“hduopenthelock”，密码范围～，共约种，用BFS搜索时，最多有个状态进入队列，就没有必要使用双向BFS。而例题HDUSolitaire，可能的棋局状态有万种，走8步棋会扩展出^种状态，大于万，相当于扩展到所有可能的棋局，此时应该使用双向BFS。很多教材和网文讲解双向广搜时，常用八数码问题做例子。下图引用自本篇参考书《算法竞赛入门到进阶》4.3.2节，演示了从状态A移动到状态F的搜索过程。八数码共有9!=种状态，不太多，用普通BFS也行。不过，用双向广搜更好，因为八数码每次扩展，下一层的状态数量是上一层的2～4倍，比二叉树的增长还快，效率的提升也就更高。▍图3八数码问题的搜索树
2.双向广搜的实现
双向广搜的队列，有两种实现方法：
（1）合用一个队列。正向BFS和逆向BFS用同一个队列，适合正反2个BFS平衡的情况。正向搜索和逆向搜索交替进行，两个方向的搜索交替扩展子状态，先后入队。直到两个方向的搜索产生相同的子状态，即相遇了，结束。这种方法适合正反方向扩展的新结点数量差不多的情况，例如上面的八数码问题。
（2）分成两个队列。正向BFS和逆向BFS的队列分开，适合正反2个BFS不平衡的情况。让子状态少的BFS先扩展下一层，另一个子状态多的BFS后扩展，可以减少搜索的总状态数，尽快相遇。例题见后面的“洛谷p字串变换”。
和普通BFS一样，双向广搜在扩展队列时也需要处理去重问题。把状态入队列的时候，先判断这个状态是否曾经入队，如果重复了，就丢弃。
3.双向广搜例题
（1）hduopenthelock