旅行商问题（动态规划解法）

题目描述：
给定一系列城市和每对城市之间的距离，旅行商问题要求找到一条最短的可能路径，使得旅行商访问每个城市恰好一次，并最终回到起点城市。这是一个经典的NP-hard问题，在组合优化和图论中具有重要地位。

解题过程：

1. 问题建模
   首先将问题建模为完全图G=(V,E)，其中：

• V是城市集合，|V|=n
• E是连接所有城市的边集合
• 每条边(i,j)有权重w(i,j)表示城市i到j的距离

2. 动态规划状态定义
   我们定义dp[mask][i]为：

• 从城市0出发
• 访问过mask表示的城市集合（用位掩码表示）
• 当前位于城市i
  时的最短路径长度

其中：

• mask是一个n位的二进制数，第k位为1表示城市k已被访问
• 初始状态：dp[1][0] = 0（只访问了城市0，且位于城市0）

3. 状态转移方程
   对于每个状态dp[mask][i]，考虑所有未访问的城市j：
   dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j], dp[mask][i] + w(i,j))

解释：

• 从当前状态(mask, i)转移到新状态(mask | (1<<j), j)
• 新mask是原mask加上城市j
• 路径长度增加w(i,j)

4. 算法步骤
   步骤1：初始化

• 创建dp数组，大小为2^n × n，初始值为无穷大
• dp[1][0] = 0（起点状态）

步骤2：状态转移
遍历所有mask值从1到2^n-1：
对于每个mask，遍历所有城市i：
如果dp[mask][i]不是无穷大：
遍历所有未访问城市j（mask的第j位为0）：
更新dp[mask | (1<<j)][j] = min(当前值, dp[mask][i] + w(i,j))

步骤3：计算最终结果
遍历所有城市i（i≠0）：
最终结果 = min(最终结果, dp[(1<<n)-1][i] + w(i,0))

5. 复杂度分析

• 时间复杂度：O(n² × 2^n)
• 空间复杂度：O(n × 2^n)

6. 实例演示
   考虑4个城市（0,1,2,3），距离矩阵为：

  0  1  2  3
0 0 10 15 20
1 10 0 35 25  
2 15 35 0 30
3 20 25 30 0

计算过程：

• 初始：dp[0001][0] = 0
• 第一步后：dp[0011][1] = 10, dp[0101][2] = 15, dp[1001][3] = 20
• 继续状态转移直到mask=1111
• 最终找到最短回路：0→1→3→2→0，总距离80

这个动态规划解法虽然仍是指数级复杂度，但对于n≤20的情况在实际中是可接受的。