第 115B 章 双向搜索¶
状态：待扩写。 本章目前只有收益分析一节。 双向 BFS 的实现细节、与折半枚举的分工、例题尚未写入。
前置：BFS广度优先搜索
双向搜索从起点和终点同时扩展，在中间相遇。 它是唯一能把指数「开平方」的通用手段：\(O(b^d)\) 变成 \(O(2b^{d/2})\)。
代价是两个前提：反向邻居可枚举，且起点终点都明确。
1 双向搜索的收益¶
| 单向 BFS | 双向 BFS | |
|---|---|---|
| 扩展的状态数 | \(O(b^d)\) | \(O(2 b^{d/2})\) |
| \(b=4, d=20\) | \(10^{12}\) ❌ | \(2\times10^6\) ✅ |
双向搜索是唯一能把指数「开平方」的通用手段， 但要求「反向邻居可枚举」且「起点终点都明确」。 见 BFS 广度优先搜索 的双向 BFS 小节。 数论里的同一思想叫 BSGS（同余方程组与离散对数）， 组合里叫 meet in the middle（\(2^{40}\) 子集和拆成两半）。
2 本章速查¶
| 要点 | 结论 |
|---|---|
| 收益 | \(O(b^d) \Rightarrow O(2b^{d/2})\)，唯一能把指数开平方的通用手段 |
| 两个前提 | 反向邻居可枚举；起点终点都明确 |
| 实现 | 双向 BFS，见 BFS广度优先搜索 |
| 数论里的同一思想 | BSGS（同余方程组与离散对数） |
| 组合里的同一思想 | meet in the middle（\(2^{40}\) 子集和拆成两半） |