知识卡片
近似算法换取可行效率
当精确最优解暂无已知高效算法时,近似算法用可接受的解质量换取可执行的计算成本。
选择它前要明确“好解”的衡量标准、可接受偏差和问题假设;近似不等于无条件正确。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第1章 算法在计算中的作用 · 查看原书依据
If, instead, you can show that the problem is NP-complete, you can spend your time developing an efficient approximation algorithm, that is, an algorithm that gives a good, but not necessarily the best possible, solution.
参考来源
- 位置:《算法导论(第4版)》第 1 章《算法在计算中的作用》(源文件:`OEBPS/chapter001.xhtml`)
- 结论依据:第1章把近似算法描述为有效率地给出良好但不必最优的解;本卡把解质量和假设列为选择时需声明的条件。
- 原始内容:If, instead, you can show that the problem is NP-complete, you can spend your time developing an efficient approximation algorithm, that is, an algorithm that gives a good, but not necessarily the best possible, solution.