旅行商问题动态规划python

旅行商问题是一个组合优化问题，目标是找到访问每个城市一次并返回原始城市的最短路线。在动态规划中，可以使用一个二维数组来表示子问题的最优解，并利用状态转移方程进行计算。下面是一个旅行商问题的动态规划解法的示例代码：

def tsp_dp(dist_matrix):
    n = len(dist_matrix) # 城市数量
    # 创建二维数组来存储子问题的最优解
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0 # 起始点的最优解为0
    
    # 通过遍历所有状态（子集）来计算最优解
    for mask in range(1, 1 << n):
        for j in range(n):
            if mask & (1 << j): # 判断第 j 个城市是否在子集中
                for k in range(n):
                    if k != j and mask & (1 << k): # 判断第 k 个城市是否在子集中且不等于 j
                        dp[mask][j] = min(dp[mask][j], dp[mask ^ (1 << j)][k] + dist_matrix[k][j])
    
    # 返回最终的最优解
    return min(dp[-1])

# 示例输入
dist_matrix = [
    [0, 2, 9, 10],
    [1, 0, 6, 4],
    [15, 7, 0, 8],
    [6, 3, 12, 0]
]

# 调用函数并输出结果
result = tsp_dp(dist_matrix)
print("最短路线的长度为:", result)