在优化和/或计算机科学方面说“算法是精确的”是什么意思？我需要一个精确的逻辑/认识论定义。
最佳答案
Exact和approximate算法是解决优化问题的方法。Exact algorithms是总能找到给定优化问题的最佳解决方案的算法。
但是，在组合问题或总体优化问题中，常规方法通常效果不佳，尤其是在问题搜索区域较大且复杂的情况下。在其他方法中，我们可以使用启发式方法来解决该问题。启发式方法往往会给出次优的解决方案。启发式方法的一个子集是approximation algorithms。
当我们使用approximation algorithms时，我们可以证明最优解与算法产生的解之间的比率有界。
例如。在某些NP-hard问题中，有一些polynomial-time近似算法，而最著名的精确算法需要exponential time。
例如，当存在polynomial-time的Vertex Cover近似算法时，最佳exact algorithm(使用备注)在 O(1.1889) pp 62-63 中运行。