1

由于通过映射将任何 NP Hard 问题简化为任何其他 NP Hard 问题，我的问题向前迈出了一步；例如，该算法的每一步：也可以映射到另一个 NP 硬吗？

提前致谢

4

2 回答 2

2

从http://en.wikipedia.org/wiki/Approximation_algorithm我们看到

NP-hard 问题的逼近性差异很大；有些问题，例如装箱问题，可以在任何大于 1 的因子内进行近似（这样的近似算法族通常称为多项式时间近似方案或 PTAS）。除非 P = NP，否则其他问题不可能在任何常数甚至多项式因子内进行近似，例如最大团问题。（结束报价）

由此可见，一个 NP 完全问题的良好近似不一定是另一个 NP 完全问题的良好近似。在那个幸运的世界里，我们可以使用容易近似的 NP 完全问题来为所有其他 NP 完全问题找到好的近似算法，但这里的情况并非如此，因为存在难以近似的 NP 完全问题。

于 2013-05-06T10:01:25.593 回答
2

当证明一个问题是 NP-Hard 时，我们通常会考虑问题的决策版本，它的输出要么是肯定的，要么是否定的。但是，在考虑近似算法时，我们会考虑问题的优化版本。

如果您使用一个问题的近似算法通过使用 NP-Hard 证明中的约简来解决另一个问题，则近似比可能会发生变化。例如，如果你有一个问题 A 的 2 近似算法，并且你用它来解决问题 B，那么你可能会得到问题 B 的 O(n) 近似算法，因为减少不会保留近似比。因此，如果你想对一个问题使用近似算法来解决另一个问题，你需要确保减少不会过多地改变近似比以获得有用的算法。例如，您可以使用L-reduction或PTAS reduction。

于 2013-05-06T11:10:34.447 回答