就优化和/或计算机科学而言，“算法是精确的”是什么意思？我需要一个精确的逻辑/认识论定义。
最佳答案
Exact 和approximate 算法是解决优化问题的方法。
精确算法 是总能找到给定优化问题的最优解的算法。
然而，在组合问题或总体优化问题中，常规方法通常不够有效，尤其是当问题搜索区域较大且复杂时。在其他方法中，我们可以使用启发式方法来解决这些问题。启发式往往会给出次优的解决方案。启发式算法的一个子集是近似算法。
当我们使用近似算法时，我们可以证明最优解与算法生成的解之间的比率存在界限。
例如在某些 NP-hard 问题中，有一些多项式时间 近似算法，而最著名的精确算法需要指数时间。
例如，虽然 Vertex Cover 有一个多项式时间 近似算法，但最好的精确算法(使用内存)在 <强> O(1.1889n) pp 62-63 .
关于algorithm - 对 "Exact Algorithm"的定义感到困惑，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26074895/