解决特定 NP 完全问题的最快算法是什么？例如，旅行推销员的简单实现是 O(n!)，但使用动态规划可以在 O(n^2 * 2^n) 中完成。是否有任何可能“更简单”的 NP-Complete 问题具有更好的运行时间？
我对确切的解决方案而不是近似值感到好奇。
问问题
1056 次
3 回答
4
NP-Complete 问题的一个特点是 NP 中的任何问题都可以在最多多项式时间内机械地转换为任何 NP-Complete 问题。
因此，无论任何给定 NP 完全问题的最佳解决方案是什么，对于任何其他 NP 问题，它都会自动成为类似的好解决方案。
鉴于动态规划可以在 2^n 时间和 2^n 空间内解决旅行商问题，所有其他 NP 问题也必须如此[好吧，加上应用转换的时间，我猜 - 所以它可能是 2^ (n+1)]。
于 2009-11-22T02:05:42.303 回答
4
[...] 使用动态编程可以在 O(n^2 * 2^n) 中完成。是否有任何可能“更简单”的 NP-Complete 问题具有更好的运行时间？
有点。您可以通过创建一个人为的问题来摆脱任何多项式因素，该问题在多项式更大的输入中编码相同的解决方案。只要输入只是多项式更大，由此产生的问题仍然是 NP 完全的。由于复杂性是根据定义将输入大小映射到运行时间的函数，如果输入大小增长，该函数将进入较低的 O 类。
因此，在 TSP 上运行相同的算法，输入用 n^2 无用位填充，复杂度为 O(1 * 2^sqrt(n))。
于 2009-11-23T17:06:29.410 回答
0
通常，如果不尝试所有组合（可能存在负距离等），您将无法找到通用旅行商问题的最佳解决方案。
通过添加额外的限制并放宽获得最佳解决方案的要求，您可以大大加快速度。
For instance you can get polynomial executable time if the distances in the problem obey the "it is not longer to go directly from A to B than going from A to C to B" (i.e. a shortcut is never longer), and you can live with the result maximally being 1.5 times the optimal value. See http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP
于 2010-11-28T01:12:46.273 回答