知识卡片
最长简单路径不能任意拼接
最长简单路径拆成两段后,各段独立求得的最长路径可能共用顶点,拼起来会重复顶点而失去“简单”资格。因此原问题的最优路径中的子段未必是对应端点间最长简单路径,不能直接套最短路径式动态规划。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
you cannot necessarily assemble a “legal” solution to the problem from solutions to subproblems.
参考来源
- 位置:《算法导论(第4版)》第 14 章 14.3–14.4 节(`OEBPS/chapter014.xhtml`,文本字符 [50000, 60000);图 14.6、Art_P463)。
- 结论依据:14.3 节最长简单路径反例中,两段各自最长路径拼接会重复顶点,所得路径不再简单;故不能把独立最长子段直接替换进整体。
- 原始内容:you cannot necessarily assemble a “legal” solution to the problem from solutions to subproblems.