algorithm - 为什么在算法中使用启发式会消除渐近最优性？

Question

我正在阅读一些几何路由算法，它说当在主算法的一个版本中采用启发式算法时，它可能会提高性能，但会带走渐近最优性。

为什么会这样？我们应该更喜欢渐近最优而不是更好的性能吗？是否存在应该选择渐近最优性的典型案例？有没有已知的基准？

Answer 1

我认为您问的是启发式算法运行速度快但可能无法实现完全最优解决方案的优化问题，而真正的最优解决方案寻找算法在最坏的情况下运行速度可能会慢得多，尽管它们总是给出完全最优的解决方案。如果是这样，这里有一些信息。一般来说，使用启发式算法的决定通常取决于它在“实践中”逼近最佳解决方案的程度，以及这种典型的解决方案质量是否对您来说足够好，以及您是否认为您的特定问题实例属于实践中遇到的问题的类别。如果您有兴趣，可以查找 NP 完全问题的近似算法。有一些问题，启发式找到的解决方案的分数在最优解决方案分数的常数乘数（1 + epsilon）内，您可以选择 epsilon；然而，通常运行时间会随着 epsilon 的减少而增加。

Answer 2

我的猜测是，他们正在谈论使用（不可接受的）启发式算法进行近似算法。例如，旅行商问题是 NP 完全问题，但有一些启发式逼近方法比 NP 完全问题的已知算法快得多，但只能保证达到最优值的百分之几。