代码
import sys
# 10个城市的距离矩阵
dist = [
[0,7,4,5,8,6,12,13,11,18],
[7,0,3,10,9,14,5,14,17,17],
[4,3,0,5,9,10,21,8,27,12],
[5,10,5,0,14,9,10,9,23,16],
[8,9,9,14,0,7,8,7,20,19],
[6,14,10,9,7,0,13,5,25,13],
[12,5,21,10,8,13,0,23,21,18],
[13,14,8,9,7,5,23,0,18,12],
[11,17,27,23,20,25,21,18,0,16],
[18,17,12,16,19,13,18,12,16,0]
]
# 动态规划求解TSP
def tsp_dp():
n = len(dist) # 城市数量
# dp[i][j]表示从城市i出发,经过集合j中的城市,最后回到起点的最短距离
dp = [[sys.maxsize] * (1 << n) for _ in range(n)]
# 初始化dp数组
for i in range(n):
dp[i][1 << i] = 0
# 状态转移
for j in range(1, 1 << n):
for i in range(n):
if j & (1 << i): # 集合j中包含城市i
for k in range(n):
if j & (1 << k) and i != k: # 集合j中包含城市k且i不等于k
dp[i][j] = min(dp[i][j], dp[k][j - (1 << i)] + dist[k][i])
# dp[i][j]表示从城市i出发,经过集合j中的城市,最后回到起点的最短距离
# dp[k][j - (1 << i)]表示从城市k出发,经过集合j中除去城市i的其它城市,最后到达城市i的最短距离
# dist[k][i]表示从城市k到城市i的距离
# 所以dp[i][j]的值为dp[k][j - (1 << i)] + dist[k][i]和dp[i][j]中的较小值
# 找出最短路径
ans = sys.maxsize
for i in range(n):
ans = min(ans, dp[i][(1 << n) - 1] + dist[i][0])
# dp[i][(1 << n) - 1]表示从城市i出发,经过所有城市,最后回到起点的最短距离
# dist[i][0]表示从城市i到起点的距离
# 所以dp[i][(1 << n) - 1] + dist[i][0]表示从城市i出发,经过所有城市,最后回到起点的总距离
# ans为所有城市中从任意一个城市出发,经过所有城市,最后回到起点的总距离的最小值
return ans
print(tsp_dp()) # 输出最短路径长度
运行结果:
66
部分代码详解
dp = [[sys.maxsize] * (1 << n) for _ in range(n)]
这段代码是Python中用于创建一个n维数组的语法。其中,`n`是数组的维数,`sys.maxsize`是一个常量,表示当前系统中整数类型的最大值。这个语法使用了列表推导式和位运算符。具体来说,`[sys.maxsize] * (1<<n)`表示创建一个长度为2^n的列表,其中每个元素都是`sys.maxsize`。然后,通过`for _ in range(n)`的循环语句将这个列表重复n次,从而得到一个n维数组。
版权声明:本文为2301_76620728原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。