知识卡片
精确程度是需要明确的契约
对难以在时限内精确求解的优化问题,可评估足够好且及时的结果,但需由用户目标决定允许放宽什么。启发式通常不自动提供质量证明,近似算法的保证依问题条件与算法而定。原书TSP结果仅差2%—5%的说法不构成普遍保证,也不能由NP-hard推出所有实例必然难解。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 优化——一些强大的技术 12.4.1 使用启发式和近似算法 · 查看原书依据
具有可证明的解决方案质量和运行时间界限
参考来源
- 位置:《Python编程精进(第1辑)(套装共3册)(异步图书)》Python高级编程(第2版) · 第12章 优化——一些强大的技术,spine021单元012;来源项目book-sources,extracted/Python编程精进(第1辑)(套装共3册)(异步图书)/_epub-src/OEBPS/text00020.html。
- 结论依据:原文讨论近似结果与时限,支持以允许误差定义目标;启发式、近似保证和NP-hard各有条件,2%—5%不是通用保证。未在本机运行示例或改变环境。
- 原始内容:启发式相似,但是与启发式算法不同的是,它具有可证明的解决方案质量和运行时间界限。 例如,有已知良好的启发式和近似问题可以在合理的时间内解决非常大的TSP问题。它们也有很高的概率产生只有2%~5%的最优解的结果。 启发式的另一个好处是,它们并不总是需