TSP动态规划算法演示

深入理解旅行商问题的动态规划求解过程，观察递归调用和回溯法的完整工作流程

问题描述

给定5个城市和它们之间的距离矩阵，找到一条访问每个城市恰好一次并返回起点的最短路径。

这是经典的NP完全问题，动态规划可以在O(n²×2ⁿ)时间内求解

距离矩阵

0 1 2 3 4

最终结果

最短距离

85

最优路径

0 → 1 → 3 → 4 → 2 → 0

递归调用次数: 52

动态规划表大小: 32

城市路径可视化

递归调用过程

动态规划表

访问集合 当前城市 最短距离 前驱城市

算法原理解析

O(n²×2ⁿ)
时间复杂度
O(n×2ⁿ)
空间复杂度
精确解
解的质量
n≤20
适用规模

核心思想

动态规划求解TSP问题的关键在于定义合适的状态。我们定义 dp[S][i] 表示从起点0出发， 访问集合S中的所有城市，最终到达城市i的最短路径长度。

递推关系

基本情况： dp[{0, i}][i] = distance[0][i]
递推关系： dp[S][i] = min(dp[S-{i}][j] + distance[j][i])
最终解： min(dp[all_cities][i] + distance[i][0])

算法步骤

  1. 初始化：计算所有两城市路径的成本
  2. 递推求解：按集合大小递增计算更大的子问题
  3. 回溯重建：从最终解回溯找到最优路径
📊 已访问 次