用python用动态规划法求TSP问题代码

以下是一个采用动态规划法求解TSP问题的Python代码：

import math
import itertools

# 计算两点之间的距离
def dist(p1, p2):
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

# 计算点集之间最短距离
def tsp(points):
    n = len(points)
    dp = [[float('inf')]*(n-1) for _ in range(1<<n-1)]
    for i in range(n-1):
        dp[1<<i][i] = dist(points[0], points[i+1])
    for s in range(1<<n-1):
        for i in range(n-1):
            if s&(1<<i):
                for j in range(n-1):
                    if i!=j and (s&(1<<j)):
                        dp[s][i] = min(dp[s][i], dp[s^(1<<i)][j]+dist(points[0], points[i+1])+dist(points[i+1], points[j+1]))
    res = float('inf')
    for i in range(n-1):
        res = min(res, dp[(1<<n-1)-1][i]+dist(points[0], points[i+1]))
    return res

# 测试
points = [(0,0), (1,1), (2,2), (3,3), (2,0)]
print(tsp(points))

如果您有更多问题，欢迎继续提问。