双向搜索

Summary

两种把指数级搜索规模开方的技巧。双向同时搜索从起点和终点同时做 BFS，两侧交替向外扩展直到在中间相遇，把单向的 O(b^d) 降到 O(b^(d/2))；实现时维护两个队列与两张距离表，每轮扩展规模较小的一侧。折半搜索（Meet in the Middle）针对决策序列可对半拆分的问题：把 n 个决策分成两半，各枚举 2^(n/2) 种组合，一侧排序或存入哈希表，另一侧查询配对，从而把 O(2^n) 规模开方。典型场景是从 n 个数中选若干使和为定值的子集和问题。

参考资料

• 双向搜索 - 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})$，再用双指针或哈希合并即可。