TSP旅行商问题python代码

TSP问题（旅行商问题）是一个NP难问题，它的目标是在给定的一些城市和每对城市之间的距离下，找到访问每一座城市并回到起始城市的最短回路。下面是一个基本的TSP问题的python代码实现：

import itertools

def tsp(cities):
    # 获取城市之间的距离
    dists = {(i, j): distance(cities[i], cities[j]) for i, j in itertools.permutations(range(len(cities)), 2)}

    # 计算最短路径
    n = len(cities)
    path = range(n)
    min_dist = None
    for path in itertools.permutations(range(n)):
        d = sum(dists[path[i], path[(i+1) % n]] for i in range(n))
        if not min_dist or d < min_dist:
            min_dist = d
    return min_dist

# 计算两个城市之间的距离
def distance(city1, city2):
    return ((city1 - city2)**2 + (city1 - city2)**2)**0.5

# 调用tsp函数计算最短路径
cities = [(0, 0), (1, 0), (1, 1), (0, 1)]
print(tsp(cities))

这段代码使用了itertools.permutations函数来获取城市之间的距离，并使用sum函数计算路径长度。我们可以根据自己的需要修改代码来适应不同的TSP问题。