知识卡片
子问题图揭示计算规模
子问题图以每个不同状态为顶点、直接依赖为有向边,可视为把递归树中重复状态折叠合并。自底向上须按依赖的反向拓扑顺序计算;若处理一个状态的成本与出边数成正比,总成本通常随顶点加边数增长。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
It is a directed graph, containing one vertex for each distinct subproblem.
参考来源
- 位置:《算法导论(第4版)》第 14 章 14.1 节(`OEBPS/chapter014.xhtml`,文本字符 [15000, 25000);图 14.4、Art_P455)。
- 结论依据:子问题图定义为每个不同状态一个顶点、直接依赖一条有向边;原文说明自底向上按反向拓扑顺序,若每态工作与出边成正比,总成本与图规模相关。
- 原始内容:It is a directed graph, containing one vertex for each distinct subproblem.