知识卡片

普通读书笔记卡 · 3623.b.2.a

最长简单路径不能任意拼接

理解等级:高级

最长简单路径拆成两段后,各段独立求得的最长路径可能共用顶点,拼起来会重复顶点而失去“简单”资格。因此原问题的最优路径中的子段未必是对应端点间最长简单路径,不能直接套最短路径式动态规划。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.