对于 TSP，Held–Karp 算法如何将 Brute-force O(n!) 的时间复杂度降低到 O(2^n*n^2)？
For TSP, how does Held–Karp algorithm reduce the time complexity from Brute-force's O(n!) to O(2^n*n^2)?
我很难理解Held-Karp算法的核心思想，它是如何降低时间复杂度的？
是因为它使用动态规划，所以通过从缓存中获取中间结果来节省时间，还是因为它在计算中更早地删除了一些路径？
此外，是否可以使用二维 table 来显示计算
一个简单的 TSP 问题（3 或 4 个城市）？
Held–Karp 算法的动态规划过程利用了以下 属性 TSP 问题：最小距离路径的每个子路径本身也是最小距离。
因此，从本质上讲，我们不是使用天真的 "top-down" 蛮力方法（针对所有可能的排列）检查所有解决方案，而是使用 "bottom-up" 方法，其中求解所需的所有中间信息该问题出现一次 并且仅出现一次 。初始步骤是最小的子路径。每次我们向上移动以解决更大的子路径时，我们都能够查找已计算出的所有较小子路径问题的解决方案。节省时间是因为所有较小的子问题都已经解决，并且这些节省呈指数复合（在每个更大的子路径级别）。但是计算中没有 "paths are removed"——在程序结束时，所有的子问题都将得到解决。明显的缺点是可能需要非常大的内存来存储所有中间结果。
总而言之，Held–Karp 算法之所以能节省时间，是因为它从不 重复求解城市的任何子集（组合）的解决方案。但是蛮力方法将多次重新计算任何给定子集组合的解决方案（尽管不一定在给定的整体集合排列内按连续顺序）。
维基百科包含二维距离矩阵示例和伪代码 here。
我很难理解Held-Karp算法的核心思想，它是如何降低时间复杂度的？ 是因为它使用动态规划，所以通过从缓存中获取中间结果来节省时间，还是因为它在计算中更早地删除了一些路径？
此外，是否可以使用二维 table 来显示计算 一个简单的 TSP 问题（3 或 4 个城市）？
Held–Karp 算法的动态规划过程利用了以下 属性 TSP 问题：最小距离路径的每个子路径本身也是最小距离。
因此，从本质上讲，我们不是使用天真的 "top-down" 蛮力方法（针对所有可能的排列）检查所有解决方案，而是使用 "bottom-up" 方法，其中求解所需的所有中间信息该问题出现一次 并且仅出现一次 。初始步骤是最小的子路径。每次我们向上移动以解决更大的子路径时，我们都能够查找已计算出的所有较小子路径问题的解决方案。节省时间是因为所有较小的子问题都已经解决，并且这些节省呈指数复合（在每个更大的子路径级别）。但是计算中没有 "paths are removed"——在程序结束时，所有的子问题都将得到解决。明显的缺点是可能需要非常大的内存来存储所有中间结果。
总而言之，Held–Karp 算法之所以能节省时间，是因为它从不 重复求解城市的任何子集（组合）的解决方案。但是蛮力方法将多次重新计算任何给定子集组合的解决方案（尽管不一定在给定的整体集合排列内按连续顺序）。
维基百科包含二维距离矩阵示例和伪代码 here。