专题：搜索（二）—— 迭代加深、双向搜索与折半搜索 —— 换一棵更小的树

本讲定位（先把话说清楚）：基础算法系列第 06 讲，本线正篇的最后一讲，标 S⭐，J 组可跳。

定位比第 05 讲还要克制，依据是本库两份逐题统计（cspj-series/cspj-round2-analysis-2019-2025.md、csps-series/csps-round2-analysis-2019-2025.md）：迭代加深、双向搜索、折半搜索、A 在 CSP-J/S 两组复赛七年 58 题里 0 次主考点、0 次次考点。* 它们在真题里只出现在初赛阅读程序：双向 BFS 是 CSP-S 2020 阅读(3) 的原题，折半搜索是 CSP-S 2025 阅读(3) 的新面孔（csps-series/csps-exam-analysis-2019-2025.md §3）。

所以本讲要交付的是三样东西：（1）NOI 大纲【7】级三条目（迭代加深、双向广搜、启发式搜索）达标；（2）CSP-S 初赛阅读程序里认得出这三种代码、能手算它的复杂度；（3）知道每种手段的前提，以及前提破了会怎样。不追求做难题。

接第 05 讲的钩子：第 05 讲 §2.1 那张表说”可行性剪枝的收益随 $n$ 指数放大”。本讲回答它留下的问题——当剪枝已经用尽、搜索树还是太大时，怎么办？ 答案不是再剪，而是换一棵更小的树：限制深度反复搜（§2）、从两头往中间搜（§3）、把 $2^n$ 拆成两个 $2^{n/2}$（§4）。

本讲实测

⚠️ 编译选项：本讲代码块由 tools/check-cpp-blocks.py 用 g++ -std=c++11（不开 -O2） 编译运行，下列耗时即该环境实测；§4.3 另给了开 -O2 的对照。结点数 / 出队数 / 枚举量与编译选项无关，本讲的结论优先用它们表述——这是第 05 讲定下的纪律。

迭代加深”重复搜浅层”的开销在均匀 $b$ 叉树上精确等于 $\dfrac{b}{b-1}$：$b=2$ 时累计结点是最后一轮的 2.000 倍，$b=3$ 是 1.500 倍，$b=10$ 是 1.111 倍——实测与理论四位小数全对。分叉越多，重复越不值一提。
⚠️ 但在真实问题上”累计 / 最后一轮”这个比值没有意义：加成序列 $n=100$ 时是 1099.44 倍（最后一轮只走了 9 个结点就命中），$n=31$ 时是 5.18 倍，$n=127$ 时是 68.25 倍。该比的对象是”不知道答案深度的普通 DFS”：它要把限深 $ans+1$ 的整棵树搜完才能确认最优，实测比迭代加深多走 28.8 倍（$n=31$）、72.7 倍（$n=63$）、90.5 倍（$n=100$），$n\ge127$ 时 3000 万结点都搜不完。迭代加深省的不是”重复搜浅层”那一点，而是”多猜一层就多几十倍”那一大块。
加一个可采纳的估价函数（IDA），结点数再降 2.9 ～ 224.9 倍*（加成序列，估价 = “剩下的步数全部翻倍也到不了 $n$ 就剪”）。答案与不带估价的版本完全一致——估价不高估，最优性就不丢。
双向 BFS 在一个 $10^5$ 状态、四种互逆操作的状态空间上，600 组随机起终点合计出队少 32.6 倍；按距离分桶，$d=24$ 时 14.8 倍、$d=37$ 时 39.6 倍——距离越远省得越多，与 $b^d \to 2b^{d/2}$ 的预期一致。答案与单向 BFS 600 组全部一致。
折半搜索把 $n=28$ 的 $2^{28}$ 暴力从 1.265 s 压到 0.007 s（181 倍）；$n=40$ 时暴力要 $2^{40}\approx1.1\times10^{12}$ 次、折算约 86 分钟，折半 0.670 s。⚠️ 折半的瓶颈是排序不是合并：$n=40$ 时排序占 0.614 s（92%），双指针合并只要 0.018 s；把合并换成逐个二分是 0.204 s（慢 11 倍）但总时只多 28%。开 O2 后排序占比降到 84%，二分比双指针只慢 4.1 倍——又一条必须标编译选项的结论。
⚠️⚠️ 折半搜索四种错法的错误率（三档 $n\le4$ / $n\le16$ / $n=20$）：左半枚举漏空集 25.11% / 33.97% / 49.50%；划分时漏掉中间那个元素 24.41% / 66.23% / 96.50%；右半忘排序就二分 43.98% / 79.90% / 99.50%；双指针合并遇到相等的和只数一对 1.31% / 54.07% / 97.50%——最后一种在 $n\le4$ 时几乎测不出（1.31%），大数据 97.50%，它是本线第 07 讲”相向双指针”的老毛病换了个地方出现。

前置与适合对象

前置：

basic-series/05-backtracking-and-pruning.md —— 本讲直接接第 05 讲 §2.1 的钩子；回溯骨架不重讲。
graph-series/03-bfs-advanced.md §4 —— 双向 BFS 已经在那里用八数码实测过（省 95%～98% 出队，无解时反而慢 30%）。本讲不重做八数码，只讲一般框架，并换一个非棋盘的状态空间重测一次。
basic-series/07-two-pointers.md §3 —— 折半搜索的”合并两半”就是那一节的相向双指针（有序数组两数之和）。
basic-series/04-enumeration-simulation-construction.md §2 —— 子集枚举 for (s = 0; s < (1 << n); s++) 的写法，折半的两半各用一次。

适合对象：CSP-S 复赛（全讲）；CSP-S 初赛（§2.1、§3.2、§4.2 三个模板 + §7.2 的读法，能看懂 2020 / 2025 阅读(3) 那两段代码即可）；CSP-J 可整讲跳过（J 组两轮七年 0 次）。

本讲不讲（只指路）：