旅行商问题（动态规划解法） 题目描述：给定一个带权完全无向图，每个顶点代表一个城市，边权代表城市间的距离。旅行商需要访问每个城市恰好一次并返回起点，求最短的环路路径长度。 解题过程： 问题分析 这是NP难问题，暴力解法需要检查O(n !)种路径 使用动态规划将时间复杂度优化到O(n²·2ⁿ) 核心思想：记录"已访问城市集合"和"当前所在城市"的状态 状态定义 令dp[ mask][ i ]表示： mask：二进制位集合，表示已访问的城市（1表示已访问，0表示未访问） i：当前所在的城市编号 dp值：从起点出发，经过mask中的城市，最后到达i的最短路径长度 状态转移方程 基础情况：dp[ 1<<0][ 0 ] = 0（只访问起点，停留在起点） 转移方程：dp[ mask][ i] = min{ dp[ mask⊕(1<<i)][ j] + dist[ j][ i ] } 其中j是mask中除i外的已访问城市 mask⊕(1< <i)表示从mask中移除城市i的集合 dist[ j][ i ]表示从j到i的距离 算法步骤 a. 初始化dp数组为无穷大，dp[ 1<<0][ 0 ] = 0 b. 遍历所有mask值（从包含起点的小集合开始） c. 对每个mask，遍历所有已访问城市i作为当前城市 d. 对每个未访问城市j，更新dp[ mask|(1<<j)][ j ] e. 最后在所有城市都访问的状态中，加上返回起点的距离 实例演示 考虑4个城市（0,1,2,3），距离矩阵： dist[ 0][ 1]=2, dist[ 0][ 2]=9, dist[ 0][ 3 ]=10 dist[ 1][ 2]=6, dist[ 1][ 3 ]=4 dist[ 2][ 3 ]=8 计算过程： mask=1(0001): dp[ 1][ 0 ]=0 mask=3(0011): dp[ 3][ 1] = dp[ 1][ 0] + dist[ 0][ 1 ] = 2 dp[ 3][ 0] = dp[ 2][ 1] + dist[ 1][ 0 ] = 2 最终结果：min{ dp[ 15][ i] + dist[ i][ 0 ] } = 21 算法优化 使用位运算高效处理集合操作 只考虑包含起点的mask，减少状态数 对于对称的TSP，可以固定起点进一步优化 这个解法虽然仍是指数级，但比阶乘级有显著改进，适用于20个城市左右的规模。