知识卡片

普通读书笔记卡 · 3592

近似算法换取可行效率

理解等级:中级

当精确最优解暂无已知高效算法时,近似算法用可接受的解质量换取可执行的计算成本。

选择它前要明确“好解”的衡量标准、可接受偏差和问题假设;近似不等于无条件正确。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

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