回溯法在所有情况下都必然需要指数时间。
虽然回溯法最坏情况是指数时间，但对于某些特殊问题（如 2SAT），精心设计的回溯算法可以在多项式时间内找到解。其实际效率高度依赖于测试、扩展与选择策略的设计。
CS170 · 第 10 讲
面对难解问题，使用搜索、近似、局部搜索、随机化和特殊结构获得可用算法。
回溯法（Backtracking）的核心思想是：在构造解的过程中，往往只需检查解的一个局部就能判断它是否不可能扩展为完整解，从而提前剪枝。以布尔可满足性（SAT）为例，若某个子句为 (w∨x)，则所有 w = x = 0 的赋值可立即排除，一次判断就能剪掉四分之一的搜索空间。
算法从原始问题 P₀ 出发，维护一个活跃子问题集合 S。每次从 S 中取出一个子问题 P，将其扩展为更小的子问题 P₁, P₂, …, Pₖ。对每个子问题执行测试：若测试报告“失败”则丢弃；若测试报告“成功”则找到解并终止；若测试报告“不确定性”则加入 S 继续搜索。当 S 为空时，宣布无解。
对于 SAT，每个搜索树节点可用部分赋值描述，也可用代入后剩余的子句描述。测试规则如下：若存在空子句（empty clause）则失败；若子句全部满足则成功；否则为不确定性。扩展时，选择包含最短子句的子问题，并在该子句中选择一个变量进行分支——若该子句是单文字子句，则至少有一个分支会被立即终止。
回溯法最坏情况仍是指数时间，但通过精心设计的测试、扩展与选择策略，在实际实例中往往极为高效。例如，当输入为 2SAT 实例时，该算法必在多项式时间内找到满足赋值（如果存在的话）。
伪代码：
Start with some problem P0
Let S = {P0}, the set of active subproblems
Repeat while S is nonempty:
choose a subproblem P ∈ S and remove it from S
expand it into smaller subproblems P1, P2, ..., Pk
For each Pi:
If test(Pi) succeeds: halt and announce this solution
If test(Pi) fails: discard Pi
Otherwise: add Pi to S
Announce that there is no solution
给定布尔公式 φ(w,x,y,z) = (w∨x∨y∨z) ∧ (w∨x) ∧ (x∨y) ∧ (y∨z) ∧ (z∨w) ∧ (w∨z)，用回溯法判断其可满足性。
搜索树探索过程（对应图 9.1）： 1. 根节点：选择变量 w 分支。w=1 和 w=0 均不立即产生空子句，两个子问题都保留。 2. 扩展 w=0 节点，选择变量 x 分支。
x=0：代入后剩余子句为 (y∨z) ∧ (y) ∧ (y∨z)，继续探索。
x=1：根据文本，此部分赋值导致空子句 ()，失败，剪枝。 3. 继续扩展其他活跃节点，选择包含最短子句的子问题，在最短子句中分支。 4. 最终，所有分支均遇到空子句，搜索树探索完毕，S 为空，宣布 φ 不可满足。
关键观察：回溯法通过检查部分赋值是否产生空子句来剪枝。选择最短子句进行分支是高效策略——若子句为单文字，则至少一个分支会被立即终止。
分支限界法（Branch-and-bound）将回溯思想从搜索问题推广到优化问题。与回溯法不同，它维护一个当前最优解 bestsofar，并通过计算子问题的下界（lower bound）来决定是否剪枝：若子问题的下界已超过 bestsofar，则该子问题不可能产生更优解，可直接丢弃。
算法框架：从原始问题 P₀ 出发，维护活跃子问题集合 S。每次取出子问题 P 并扩展为 P₁, …, Pₖ。若 Pᵢ 是完整解，则更新 bestsofar；否则若 lowerbound(Pᵢ) < bestsofar，则将 Pᵢ 加入 S 继续搜索。当 S 为空时，返回 bestsofar。
以旅行商问题（TSP）为例：图 G = (V, E) 中边长 dₑ > 0。部分解表示为 [a; S; b]，表示从固定起点 a 出发，经过顶点集 S（含端点 a, b），当前到达 b 的简单路径。子问题是找到从 b 回到 a 的最便宜补全路径，中间经过 V\S 中的顶点。
下界估计：补全路径的代价至少为以下三者之和： 1. 从 a 到 V\S 的最轻边； 2. 从 b 到 V\S 的最轻边； 3. V\S 的最小生成树（MST）。
该下界可通过 MST 算法快速计算。在 8 个顶点的图示例中，分支限界法仅考察了 28 个部分解，而暴力搜索需考察 7! = 5040 个排列。
伪代码：
Start with some problem P0
Let S = {P0}, the set of active subproblems
bestsofar = ∞
Repeat while S is nonempty:
choose a subproblem P ∈ S and remove it from S
expand it into smaller subproblems P1, P2, ..., Pk
For each Pi:
If Pi is a complete solution: update bestsofar
else if lowerbound(Pi) < bestsofar: add Pi to S
return bestsofar
面对 NP-难优化问题，若无法在多项式时间内求得精确最优解，可转而寻求近似算法（Approximation Algorithm）。对于最小化问题，算法 A 的近似比（approximation ratio）定义为：
\[\rho_A = \max_I \frac{A(I)}{OPT(I)}\]
其中 OPT(I) 是实例 I 的最优值。近似比衡量算法输出在最坏情况下超出最优解的倍数。对于最大化问题（如独立集），取倒数以保证比值 ≥ 1。
顶点覆盖（VERTEX COVER）问题：给定无向图 G = (V, E)，找最小顶点子集 S ⊆ V 使得每条边至少有一个端点在 S 中。该问题是 NP-难的，也是集合覆盖的特例，贪心算法可给出 O(log n) 近似。
更好的近似基于匹配（matching）：一组没有公共顶点的边。极大匹配（maximal matching）是无法再添加边的匹配，容易构造——反复选取与已选边不相交的边直到无法继续。
关键事实：任何顶点覆盖的大小 ≥ 任何匹配的边数（因为匹配中每条边需不同端点覆盖）。因此匹配大小是 OPT 的下界。
算法：找极大匹配 M，返回 S = M 中所有边的端点集合。S 必是顶点覆盖——若某边 e 未被覆盖，则 M 不是极大的（还可加 e）。S 有 2|M| 个顶点，而 OPT ≥ |M|，故：
\[|S| = 2|M| \leq 2 \cdot OPT\]
该算法近似比为 2，且存在达到 100% 误差的实例，故 ρ_A = 2。
k-聚类（k-CLUSTER）问题：给定 n 个点 X = {x₁, …, xₙ} 及距离度量 d(·,·)，划分为 k 个簇 C₁, …, Cₖ，最小化簇直径（簇内最远两点距离）。该问题是 NP-难的。
近似算法采用最远优先遍历（farthest-first traversal）：任选第一个中心 φ₁；对 i = 2 到 k，选距离已有中心最远的点作为 φᵢ（即最大化 min_{j<i} d(x, φᵢ)）；然后将每个点分配到最近中心形成 k 个簇。
近似比分析：设 x 是距离 φ₁, …, φₖ 最远的点（即第 k+1 个中心），r 是 x 到最近中心的距离。由三角不等式，每个点到其簇中心距离 ≤ r，故簇直径 ≤ 2r。另一方面，k+1 个点 {φ₁, …, φₖ, x} 两两距离 ≥ r，任何 k-聚类必有两点同簇，故最优直径 ≥ r。因此该算法近似比为 2。
度量 TSP 的近似：若距离满足三角不等式，最小生成树（MST）是关键结构。移除 TSP 任一边得生成树，故 TSP 代价 ≥ MST 代价。将 MST 每条边复制，得欧拉回路，再通过三角不等式跳过重复顶点（shortcutting），得到哈密顿回路，长度 ≤ 2·MST ≤ 2·OPT。
一般 TSP 的不可近似性：若距离不满足三角不等式，则 TSP 无法高效近似。通过从 Rudrata 路径问题的归约：给定图 G 和常数 C > 0，构造 TSP 实例 I(G, C)，使得 G 有 Rudrata 路径时 OPT = n，否则 OPT ≥ n + C。若存在近似比为 ρ_A 的 TSP 近似算法，取 C = n·ρ_A，则算法输出可区分两种情况，从而在多项式时间内解决 NP-完全的 Rudrata 路径问题。因此除非 P = NP，一般 TSP 不存在高效近似算法。
KNAPSACK 是最大化问题：给定 \(n\) 个物品，重量 \(w_1,\dots,w_n\) 与价值 \(v_1,\dots,v_n\)（均为正整数），背包容量为 \(W\)，目标是选出总重量不超过 \(W\) 的物品子集，使总价值最大。
第 6 章给出的动态规划可在 \(O(nW)\) 时间内求解。若改按价值枚举状态——设 \(V=\sum v_i\)，则可在 \(O(nV)\) 时间内求出达到每个可能价值所需的最小重量。但 \(W\) 与 \(V\) 都可能随输入规模指数增长（它们用 \(\log W\)、\(\log V\) 位表示），因此这两个算法都只是伪多项式时间，而非真正多项式时间。
核心思想：如果我们愿意接受 \((1-\varepsilon)\) 近似解（\(\varepsilon>0\) 由用户指定），就可以把价值“压低精度”。例如 \(v_1=117{,}586{,}003\)、\(v_2=738{,}493{,}291\)、\(v_3=238{,}827{,}453\) 可以粗化为 \(117\)、\(738\)、\(238\)，问题整体变化不大，但动态规划的状态数会大幅下降。
KNAPSACK 近似算法（FPTAS）： 1. 丢弃所有重量 \(w_i>W\) 的物品（它们不可能被选中）。 2. 记 \(v_{\max}=\max_i v_i\)。 3. 对价值进行缩放：定义缩放后价值 \[ \hat{v}_i = \left\lfloor \frac{v_i \cdot n}{\varepsilon \cdot v_{\max}} \right\rfloor. \] 4. 对缩放后价值 \(\{\hat{v}_i\}\) 运行动态规划（按价值枚举状态）。 5. 输出所选物品集合。
复杂度分析：每个 \(\hat{v}_i\) 不超过 \(n/\varepsilon\)，因此总缩放价值之和不超过 \(n^2/\varepsilon\)，动态规划的时间复杂度为 \(O(n \cdot n^2/\varepsilon) = O(n^3/\varepsilon)\)，关于输入规模和 \(1/\varepsilon\) 均为多项式。
正确性分析：设原问题最优解选取集合 \(S^*\)，总价值为 \(K^*\)。对同一集合，其缩放价值满足 \[ \sum_{i\in S^*} \hat{v}_i \ge \sum_{i\in S^*} \left(\frac{v_i n}{\varepsilon v_{\max}} - 1\right) \ge \frac{K^* n}{\varepsilon v_{\max}} - n. \] 设算法在缩放问题上求得的解为 \(\hat{S}\)，则其缩放价值至少不低于上界右端。还原到原价值： \[ \sum_{i\in \hat{S}} v_i \ge \sum_{i\in \hat{S}} \hat{v}_i \cdot \frac{\varepsilon v_{\max}}{n} \ge \left(\frac{K^* n}{\varepsilon v_{\max}} - n\right) \cdot \frac{\varepsilon v_{\max}}{n} = K^* - \varepsilon v_{\max} \ge K^*(1-\varepsilon), \] 其中最后一步用到 \(v_{\max} \le K^*\)（最优解至少包含一个物品）。因此算法输出价值至少为最优值的 \((1-\varepsilon)\) 倍。
考虑 \(n=3\)，容量 \(W=10\)，物品为：\((w_1,v_1)=(6,117)\)、\((w_2,v_2)=(5,738)\)、\((w_3,v_3)=(5,238)\)，取 \(\varepsilon=0.1\)。
\(\hat{v}_1 = \lfloor 117 \times 0.04065 \rfloor = \lfloor 4.76 \rfloor = 4\),
\(\hat{v}_2 = \lfloor 738 \times 0.04065 \rfloor = \lfloor 30.0 \rfloor = 30\),
\(\hat{v}_3 = \lfloor 238 \times 0.04065 \rfloor = \lfloor 9.67 \rfloor = 9\)。 4. 对缩放后价值 \(\{4,30,9\}\) 运行动态规划：总缩放价值之和仅 \(43\)，状态数远小于原价值之和 \(1093\)。 5. 动态规划会选物品 2（缩放价值 30，重量 5），是否加入物品 1 或 3 取决于容量；最终输出对应原问题的近似最优解。
此例说明：当原始价值很大时，缩放能把动态规划的状态数从 \(O(n\sum v_i)\) 压到 \(O(n^3/\varepsilon)\)，而解的质量损失被 \(\varepsilon\) 控制。
对任意一个 NP-完全优化问题，我们自然追问：在多项式时间内能达到的最佳近似比是多少？如果找不到最优近似算法，就转而尝试证明“多项式时间下哪些近似比是不可能达到的”——这正是对一般 TSP 所做的下界证明。
在 \(\mathsf{P} \neq \mathsf{NP}\) 的假设下，NP-完全优化问题按可近似性由差到优分为四层：
不可近似：不存在任何有限的近似比。一般 TSP 属于此类（无论取多大常数作为近似比，都无法在多项式时间内达到，除非 \(\mathsf{P}=\mathsf{NP}\)）。
有常数界限，但存在下界：可以达到某个常数近似比，但不可能任意小。例如 VERTEX COVER、k-CLUSTER、满足三角不等式的 TSP。对这些问题，可近似性的精确界限是领域内最深刻的结果之一（本书未给出证明）。
无界限可近似（PTAS/FPTAS 类）：对任意 \(\varepsilon>0\)，都存在多项式时间算法达到 \((1+\varepsilon)\)（最小化）或 \((1-\varepsilon)\)（最大化）的近似比。KNAPSACK 属于此类——上一节给出的 FPTAS 正是这一性质的体现。这一类问题是最“幸运”的 NP-完全问题。
以 \(\log n\) 为比率：近似比大约在 \(\Theta(\log n)\) 量级。SET COVER 是典型例子。
重要前提：整个分层都建立在 \(\mathsf{P} \neq \mathsf{NP}\) 的假设之上。如果 \(\mathsf{P}=\mathsf{NP}\)，则分层坍缩为 \(\mathsf{P}\)，所有 NP-完全优化问题都能在多项式时间内精确求解。
实践启示：近似算法（及其变体）在实际典型实例上的表现往往远好于其最坏情况近似比所暗示的水平。理论保证给出的是下界（最坏情况），但日常输入通常远没有最坏情况那么“病态”。
局部搜索（Local Search）受进化过程启发：通过不断引入小的“变异”，尝试并保留其中表现好的。它可以应用于任何优化问题，对最小化问题的标准框架如下：
take any initial solution s
while there exists s' in the neighborhood of s with cost(s') < cost(s):
replace s with s'
return s
关键设计决策：邻域（neighborhood）结构。它定义了什么叫“与当前解接近的解”，是局部搜索的核心。
例一：旅行商问题（TSP）。搜索空间是 \((n-1)!\) 条不同回路。两条回路若只差两条边，则互为邻居——称为 2-change 邻域（不能只差一条边，因为回路中换一条边无法保持哈密顿回路）。一次局部移动即删去两条边、换入两条新边。每条回路有 \(O(n^2)\) 个邻居，因此每次迭代很快。
但 2-change 存在大量低质量局部最优。扩大为 3-change 邻域（至多差三条边）可修复更多局部最优，但邻居数增至 \(O(n^3)\)，每次迭代更贵，且仍可能存在次优局部极小。继续扩大到 4-change、5-change……质量与效率相互竞争：邻域越小越快搜索，但低质量局部最优越多。
例二：图划分（GRAPH PARTITIONING）。给定带权无向图 \(G=(V,E)\) 和参数 \(\alpha \in (0,1/2]\)，要求把顶点划分为 \(A,B\) 且每部分至少 \(\alpha|V|\) 个顶点，使割 \((A,B)\) 容量最小。此问题是 NP-难的（去掉大小限制后才是可高效求解的 MINIMUM CUT）。
对 \(\alpha=1/2\)（两部分恰好各半）时，定义 成对交换邻域：邻居是所有通过交换 \(a \in A\) 与 \(b \in B\) 得到的划分 \((A-\{a\}+\{b\}, B-\{b\}+\{a\})\)。
两难困境：局部搜索每次迭代快、实现简单，但有两个严重缺陷——（1）迭代次数可能是指数级的；（2）最终解只能保证是局部最优（优于所有直接邻居），与全局最优差距可能很大。TSP 的 2-change 和图划分的成对交换都存在远离全局最优的低质量局部最优。
图划分中的低质量局部最优示例：考虑 16 个节点、边权为 0 或 1 的图，最优划分代价为 0（图可被完美二分）。但存在某个局部最优划分，其割代价为 2——任何单次成对交换都无法降低代价，尽管全局上存在代价为 0 的划分。这说明局部最优 ≠ 全局最优：邻域太小会“困住”搜索。
对图上的 8 节点实例，共有 \(\binom{8}{4}/2 = 35\) 个不同划分，其中有 5 个局部最优：4 个坏的（代价 2）和 1 个好的（代价 0）。若从随机划分出发、每步随机选择代价更低的邻居，则落入坏解的概率至多是好解的 4 倍，因此少量重复即可找到好解——这是随机化重启思想的雏形。
当局部最优质量不佳时，需要额外的机制帮助搜索跳出局部极小。
随机化与重启（Randomization and Restarts）。随机化在局部搜索中有两种用法：（1）随机选取初始解（如随机图划分）；（2）当存在多个可改进的邻居时随机选择其一。若单次运行到达好局部最优的概率为 \(p\)，则独立重复 \(O(1/p)\) 次就很可能找到好解。图划分的 8 节点例子中，\(p\) 不太小，因此少数几次重启即可。但当问题规模增长，好局部最优在所有局部最优中的占比可能指数下降，此时简单重试失效。
模拟退火（Simulated Annealing）。核心改动：允许以一定代价接受使目标变差的移动，从而跳出局部极小。引入温度参数 \(T\)：
take any starting solution s
repeat
randomly choose s' in the neighborhood of s
Δ = cost(s') - cost(s)
if Δ < 0:
replace s with s'
else:
replace s with s' with probability e^{-Δ/T}
当 \(T=0\)：退化为普通局部搜索（只接受改进）。
当 \(T\) 很大：\(e^{-Δ/T} \approx 1\)，几乎所有移动都被接受，搜索近乎随机游走，能自由探索整个空间。
退火策略：初始时取大 \(T\)，使搜索自由漫游、对低成本解仅有微弱偏好；随着时间推移逐步降温，偏好越来越强，系统主要停留在低成本区域，偶尔跳出以逃离局部极小；最终 \(T \to 0\) 时收敛到某个解。
启发来源：模拟退火借鉴自结晶物理——物质从液态缓慢冷却，粒子逐渐进入更有序的构型，最终形成晶格。
代价与收益：退火需要更多的局部移动才能收敛，且降温进度表（annealing schedule）的设计是一门艺术。但在解的质量显著改善的实例上，这种权衡是值得的。
虽然回溯法最坏情况是指数时间，但对于某些特殊问题（如 2SAT），精心设计的回溯算法可以在多项式时间内找到解。其实际效率高度依赖于测试、扩展与选择策略的设计。
近似算法保证的是解的值与最优值的比值有界（如不超过 2 倍），但并不保证找到最优解。例如基于极大匹配的顶点覆盖算法存在达到 2 倍误差的实例，即返回的解确实比最优解差。
FPTAS 的时间复杂度是 \(O(n^3/\varepsilon)\)，依赖于 \(1/\varepsilon\)。当 \(\varepsilon\) 趋近于 0 时，\(1/\varepsilon\) 趋向无穷大，运行时间不再是输入规模的多项式（而是关于 \(1/\varepsilon\) 的多项式）。因此对固定的 \(\varepsilon\) 它是多项式时间，但对任意精度要求它不是——这与“对任意实例都多项式时间精确求解”是两回事。
虽然 (n-1)-change 的 TSP 局部搜索确实能返回全局精确解（称为“精确”的局部搜索），但其邻域大小和迭代代价极大，甚至单次迭代就已不是多项式时间。质量和效率是竞争关系：精确性往往以牺牲效率为代价。事实上，除非 P=NP，否则 TSP 和 SET COVER 不存在既精确又具有多项式迭代次数的局部搜索。
问题：在分支限界法求解 TSP 时，对部分回路 [a;S;b] 的“完成代价”下界估计包含以下哪些要素？
问题：关于顶点覆盖的近似算法（基于极大匹配），以下哪项是正确的？
问题：在 KNAPSACK 的 FPTAS 中，为何要对价值进行缩放（rescale）？
问题：关于局部搜索，下列哪一项最准确地描述了其根本局限？
lectures/chap9.pdf · 本段对应小节 · confidence: high · 9.1 智能穷举搜索（回溯法、分支限界法）与 9.2 近似算法（顶点覆盖、聚类、TSP）lectures/chap9.pdf · 第 297 页（KNAPSACK FPTAS） · confidence: high · 9.2.4 节给出 KNAPSACK 近似算法的缩放公式与正确性分析，包含 (1-ε) 近似比的推导。lectures/chap9.pdf · 第 297-298 页（可近似性分层） · confidence: high · 9.2.5 节将 NP-完全优化问题按可近似性分为四类，并列出代表问题。lectures/chap9.pdf · 本段对应小节（9.3, 9.3.1, 9.3.2, 9.3.3） · confidence: high · 9.3 节给出局部搜索通用框架；9.3.1 以 TSP 的 2-change/3-change 为例；9.3.2 讨论图划分；9.3.3 介绍随机化重启与模拟退火。