对于TSP，Held算法如何从Brute-force的O(n!)中减少时间复杂度？到O(2^n*n^2)？

Question

我很难把握hard算法的核心思想，它如何降低时间复杂度？是因为它使用了动态规划，以便通过从缓存中获取中间结果来节省时间，还是因为它在计算的早期删除了一些路径？

此外，是否可以使用二维表显示一个简单的TSP问题(3或4个城市)的计算？

Answer 1

Held算法的动态规划过程利用了TSP问题的以下性质:最小距离路径的每个子路径本身都是最小距离的。

因此，从本质上说，我们没有在天真的“自上而下”(每一种可能的排列)中检查所有的解决方案，而是使用“自下而上”的方法，即解决问题所需的所有中间信息都是一次，一次只开发一次。第一步是极小的子路径。每次我们向上移动到求解一个更大的子路径时，我们就能够查找已经计算过的所有较小的子路径问题的解。节省时间是因为所有较小的子问题都已经解决了，并且这些节省成倍地复合(在每个更大的子路径级别上)。但是没有从计算中删除任何“路径”--在该过程的末尾，所有的子问题都将得到解决。明显的缺点是，存储所有中间结果可能需要非常大的内存大小。

总之，Held算法节省的时间是因为它从不重复求解城市的任何子集(组合)。但是，蛮力方法会多次重新计算任何给定子集组合的解(尽管不一定在给定的整体集合排列中以连续顺序排列)。

维基百科包含一个2D距离矩阵示例和伪代码这里。