算法分析与设计

Appearance

6.2 最优子结构——剪贴证明的威力 ​

问题情境：最长路径的失败 ​

两个看似相似的问题 ​

问题 1：最短路径

给定有向图 G，求从顶点 s 到顶点 t 的最短路径。

小明用 DP 求解：

  • 状态：dp[v] = 从 s 到 v 的最短距离
  • 递推：dp[v] = min(dp[u] + w(u,v)) for all u → v

实现后，结果正确。

问题 2：最长简单路径

给定有向图 G，求从顶点 s 到顶点 t 的最长简单路径（不重复顶点）。

小明心想：同样的思路，把 min 改成 max 就行。

python
def longest_path(G, s, t):
    # 状态：dp[v] = 从 s 到 v 的最长简单路径长度
    # 递推：dp[v] = max(dp[u] + w(u,v)) for all u → v
    ...

实现后，结果错误。

小明困惑了："为什么最短路径能用 DP，最长路径不能用？同样的思路啊。"

第一次困惑：为什么"同样的思路"失效？ ​

小明画了个图：

      A → B → C → D
      ↓           ↑
      E → F → G → D

从 A 到 D 的最长简单路径：

  • 路径 1：A → B → C → D（长度 3）
  • 路径 2：A → E → F → G → D（长度 4）

最长路径：路径 2，长度 4。

小明用 DP 尝试：

  • dp[A] = 0
  • dp[B] = dp[A] + 1 = 1
  • dp[C] = dp[B] + 1 = 2
  • dp[E] = dp[A] + 1 = 1
  • ...

然后，dp[D] = max(dp[C] + 1, dp[G] + 1)。

问题：dp[C] = 2，dp[G] = 3。

所以 dp[D] = max(2 + 1, 3 + 1) = 4。看起来正确啊？

第二次困惑：错误在哪里？ ​

小明继续画图，发现了一个关键问题：

假设最长 A→D 路径是 A → B → C → D（长度 3）。

那么：

  • 最长 A→C 子路径应该是什么？
  • 如果最长 A→C 是 A → E → F → C（经过 B 以外的路径）
  • 那么拼接后：A → E → F → C → D

问题：A → E → F → C → D 中，C 重复出现了！

这不是简单路径！所以子路径的最优解不能直接拼接。

核心发现：最优子结构不是自动成立 ​

小明恍然大悟：

最短路径：子路径最优 + 子路径最优 = 路径最优。这成立。

最长简单路径：子路径最优 + 子路径最优 ≠ 路径最优。因为拼接后可能不合法（顶点重复）。

关键洞察：最优子结构需要验证，不是自动成立。

直观思路：剪贴证明 ​

什么是"剪贴证明"？ ​

CLRS 教材提出了一个形象的方法：剪贴证明（Cut-and-Paste）。

直觉：

  1. 假设子问题的解不是最优的
  2. 把它"剪下来"
  3. 用最优解"贴上去"
  4. 观察拼接后的解是否仍然合法，且更好

如果能"剪贴成功"，说明最优子结构成立。如果不能，说明不成立。

最短路径的剪贴证明 ​

问题：从 s 到 t 的最短路径 P。

假设：P 包含子路径 P'（从 s 到中间点 v），P' 不是最优的。

剪贴：

  • 剪掉 P'（非最优子路径）
  • 贴上 P*（从 s 到 v 的最短路径）

拼接后：P* + （从 v 到 t 的部分）

验证：

  • P* 比 P' 更短 → 拼接后的路径比 P 更短
  • 拼接后的路径仍然合法（无重复顶点）

矛盾：假设 P 是最优，但拼接后的路径更短。矛盾。

结论：最短路径有最优子结构。

最长简单路径的剪贴失败 ​

问题：从 s 到 t 的最长简单路径 P。

假设：P 包含子路径 P'（从 s 到中间点 v），P' 不是最优的。

剪贴：

  • 剪掉 P'（非最优子路径）
  • 贴上 P*（从 s 到 v 的最长简单路径）

拼接后：P* + （从 v 到 t 的部分）

验证：

  • P* 比 P' 更长 → 拼接后的路径更长
  • 但拼接后的路径可能不合法！

失败原因：

  • P* 和 P 的后半部分可能共享顶点
  • 拼接后不是简单路径

反例：

      s → a → v → b → t
      ↓       ↓
      c → d → v

最长 s→t 路径：s → a → v → b → t（长度 4）

最长 s→v 子路径：s → c → d → v（长度 3）

拼接：s → c → d → v → b → t

问题：v 在拼接后的路径中出现了两次！

不是简单路径，不合法。

结论：最长简单路径没有最优子结构。

规范定义：最优子结构 ​

什么是最优子结构？ ​

定义：一个问题具有最优子结构，如果其最优解可以由子问题的最优解构造。

形式化：

设原问题的最优解 S 可以分解为：

  • 子问题 1 的解 S1
  • 子问题 2 的解 S2
  • ...

若 S1 是子问题 1 的最优解，S2 是子问题 2 的最优解，...，则 S 是原问题的最优解。

最优子结构的验证方法 ​

CLRS 四步法：

  1. 刻画最优解的结构：描述最优解如何由子问题的解组成
  2. 假设子问题非最优：剪贴证明的前提
  3. 剪贴替换：用子问题的最优解替换非最优解
  4. 观察拼接结果：是否合法？是否更好？

反例构造方法 ​

当剪贴证明失败时，构造反例：

  1. 找一个具体实例
  2. 找到原问题的最优解 S
  3. 找到子问题的最优解 S*
  4. 尝试拼接 S* 和 S 的其他部分
  5. 观察是否不合法（如顶点重复、约束违反）

算法实现：最短路径的 DP ​

Bellman-Ford 的 DP 视角 ​

状态定义：dp[i][v] = 使用最多 i 条边，从 s 到 v 的最短距离。

递推式：

  • dp[i][v] = min(dp[i-1][v], min(dp[i-1][u] + w(u,v) for all u → v))

初始条件：

  • dp[0][s] = 0
  • dp[0][v] = ∞ for v ≠ s

实现：

python
def bellman_ford_dp(G, s):
    n = len(G.vertices)
    dp = [[float('inf')] * n for _ in range(n + 1)]
    dp[0][s] = 0
    
    for i in range(1, n + 1):
        for v in range(n):
            dp[i][v] = dp[i-1][v]  # 不使用新边
            for u in G.predecessors(v):
                dp[i][v] = min(dp[i][v], dp[i-1][u] + G.weight(u, v))
    
    return dp[n]

时间复杂度：O(VE)（n = |V|，每层遍历所有边）。

Dijkstra 的 DP 视角 ​

状态定义：dp[v] = 从 s 到 v 的最短距离（已确定）。

递推式：对每个新确定的顶点 u，更新 dp[v] = min(dp[v], dp[u] + w(u,v))。

关键：贪心选择——每次选 dp 值最小的未确定顶点。

正确性分析：为什么最优子结构保证正确性？ ​

最短路径的正确性证明 ​

定理：设 P 是从 s 到 t 的最短路径，P 经过中间点 v。则 P 的 s→v 部分是从 s 到 v 的最短路径。

证明（剪贴法）：

假设 P 的 s→v 部分 P' 不是最短路径。

设 P* 是从 s 到 v 的最短路径，length(P*) < length(P')。

构造新路径：P_new = P* + （P 的 v→t 部分）

  • length(P_new) = length(P*) + length(v→t 部分)
  • < length(P') + length(v→t 部分) = length(P)

这与 P 是最短路径矛盾。□

最长简单路径的错误性证明 ​

反例：

图：

      A → B → C
      ↓       ↓
      D → E → C → F

最长 A→F 简单路径：A → B → C → F（长度 3）

最长 A→C 简单路径：A → D → E → C（长度 3）

拼接：A → D → E → C → F

问题：C 在拼接后出现两次，不是简单路径。

结论：最长简单路径没有最优子结构。

复杂度分析 ​

有最优子结构的复杂度 ​

时间复杂度：多项式时间（如最短路径的 O(VE) 或 O(V²)）。

原因：DP 可以按子问题依赖顺序求解，子问题数有限。

无最优子结构的复杂度 ​

时间复杂度：可能指数或 NP-hard（如最长简单路径）。

原因：无法用 DP 系统求解，需要暴力枚举或启发式搜索。

反例与变式 ​

反例 1：最长简单路径 NP-hard ​

最长简单路径问题实际上是 Hamilton 路径问题的变种，是 NP-hard。

教训：没有最优子结构的问题，往往很难用 DP 解决。

反例 2：0-1 背包 vs 分数背包 ​

0-1 背包：物品要么拿要么不拿，不能分割。

分数背包：物品可以拿一部分。

哪个有最优子结构？

答案：

  • 分数背包：有最优子结构 + 贪心选择性质，可以用贪心求解
  • 0-1 背包：有最优子结构（但无贪心选择性质），可以用 DP 求解

0-1 背包的剪贴证明：

设最优解包含物品 i 和物品 j。设子问题"背包容量为 W-w_i 时"的最优解不是最优的。

剪贴：用该子问题的最优解替换。

拼接：新的解仍然合法（容量不超过 W），且更优。矛盾。

结论：0-1 背包有最优子结构。

变式：无权图的最短路径 ​

无权图的最短路径 = BFS。

最优子结构验证：类似有权图，剪贴证明成立。

常见错误诊断 ​

错误 1：误以为所有问题都有最优子结构 ​

有人看到递归定义，就以为可以用 DP。

澄清：需要验证最优子结构。最长简单路径是反例。

错误 2：剪贴证明不严谨 ​

只说"子问题最优 → 整体最优"，没有验证拼接合法性。

澄清：必须检查拼接后的解是否满足约束。

错误 3：混淆"最优子结构"和"子问题重叠" ​

有人以为有最优子结构就能用 DP。

澄清：DP 需要两个条件：

  1. 最优子结构（保证正确性）
  2. 子问题重叠（保证效率）

LLM 连接：子问题独立性假设 ​

LLM 推理中的最优子结构 ​

Tree-of-Thoughts (ToT)：将推理分解为多个分支，每个分支独立评估。

隐含假设：每个分支的评估不依赖其他分支。

类比最优子结构：

  • 分支最优 → 整体最优
  • 类似子问题最优 → 整体最优

为什么这个连接重要？ ​

诊断 ToT 失败：

  • 如果 ToT 效果不好，可能是因为"分支最优 ≠ 整体最优"
  • 类似最长简单路径的问题：分支之间有依赖

设计改进策略：

  • 引入分支间协调机制
  • 类似解决最优子结构缺失的问题

练习 ​

基本理解 ​

  1. 概念解释：什么是"最优子结构"？用自己的话解释剪贴证明。

  2. 对比分析：为什么最短路径有最优子结构，最长简单路径没有？

  3. 画图验证：画一个图，构造最长简单路径的反例。

方法应用 ​

  1. 剪贴证明：用剪贴证明验证 0-1 背包的最优子结构。

  2. 反例构造：构造一个最长简单路径的反例，说明剪贴失败。

  3. 最短路径实现：用 DP 实现 Bellman-Ford 算法。

错误诊断 ​

  1. 诊断错误：有人用 DP 解最长简单路径，分析错误原因。

  2. 剪贴遗漏：如果剪贴证明不验证拼接合法性，会得出什么错误结论？

  3. 混淆概念：有人混淆"最优子结构"和"子问题重叠"，分析差异。

方案比较 ​

  1. 0-1 背包 vs 分数背包：对比两个问题的最优子结构和贪心性质。

  2. 最短路径实现：对比 Dijkstra（贪心）和 Bellman-Ford（DP）的适用场景。

  3. 有/无最优子结构：对比两类问题的复杂度差异。

开放设计 ​

  1. 新问题判断：给定一个问题（如"旅行商问题"），判断是否有最优子结构。

  2. 剪贴证明设计：为 LCS 设计剪贴证明，验证最优子结构。

  3. LLM 连接：分析 ToT 的"分支独立性假设"，类比最优子结构。

综合应用 ​

  1. 矩阵链乘：用剪贴证明验证矩阵链乘的最优子结构。

  2. 编辑距离：用剪贴证明验证编辑距离的最优子结构。

  3. 真实问题：用 DP 解决实际问题：最优股票买卖策略。

思考题 ​

为什么最长简单路径不能用 DP？

因为没有最优子结构。两条最长子路径拼接后，可能因为顶点重复而不合法。剪贴证明失败。

如何判断一个问题是否有最优子结构？

使用剪贴证明：

  1. 假设子问题非最优
  2. 用最优解替换
  3. 验证拼接合法性
  4. 若合法且更优，则最优子结构成立

最优子结构和子问题重叠的区别？

  • 最优子结构：保证 DP 的正确性
  • 子问题重叠：保证 DP 的效率

两者都是 DP 的必要条件，但独立。

过渡：子问题重叠和最优子结构是 DP 的两个基础。下一节：如何设计状态空间？——从一维到多维的平衡。

参考文献：

  • Cormen T H, et al. Introduction to Algorithms[M]. 4th ed. MIT Press, 2022. Chapter 15.
  • Kleinberg J, Tardos E. Algorithm Design[M]. Pearson, 2005. Chapter 6.

新时代的算法课程