双向搜索

参考资料

• 双向搜索 - OI Wiki

双向同时搜索

从起点和终点同时进行 BFS，两侧交替向外扩展，直到在中间相遇。

设答案深度为 $d$、分支因子为 $b$。单向 BFS 需要扩展 $O(b^d)$ 个状态；双向各搜一半深度，只需扩展 $O(b^{d/2})$，规模大幅下降。

实现时维护两个队列与两张距离表，每轮扩展当前规模较小的一侧。当某个状态在两侧都被访问到，即找到最短路，答案为它在两侧的距离之和。

Meet in the middle

折半搜索（Meet in the Middle）适用于状态无法分层、但决策序列可以对半拆分的问题。

把 $n$ 个决策分成两半，分别暴力枚举两侧各 $2^{n/2}$ 种组合，将一侧结果排序或存入哈希表，再用另一侧结果去查询配对，从而把 $O(2^n)$ 降到 $O(2^{n/2}\log 2^{n/2})$。

典型场景是子集和一类问题：例如从 $n$ 个数中选若干个使和为 $S$，直接枚举是 $O(2^n)$，折半后两侧各 $O(2^{n/2})$，再用双指针或哈希合并即可。