旅行商问题python代码

以下是旅行商问题的Python代码：

import itertools
import math

def distance(city1, city2):
    """计算两座城市之间的距离"""
    x1, y1 = city1
    x2, y2 = city2
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def tsp(cities):
    """旅行商问题的求解"""
    shortest_distance = None
    shortest_path = None
    for path in itertools.permutations(cities):
        # 对于每个可能的路径，计算它的距离
        total_distance = 0
        for i in range(len(path) - 1):
            total_distance += distance(path[i], path[i+1])
        # 如果这是目前找到的最短路径，记录下来
        if shortest_distance is None or total_distance < shortest_distance:
            shortest_distance = total_distance
            shortest_path = path
    # 返回最短路径和距离
    return shortest_path, shortest_distance

# 测试代码
cities = [(0,0), (1,1), (2,2), (3,3), (2,0)]
shortest_path, shortest_distance = tsp(cities)
print(shortest_path)
print(shortest_distance)

这是一个暴力枚举的方法，对于小规模的问题可以运行得很快，但对于大规模的问题会变得非常慢。更高效的解法需要使用更复杂的算法，例如动态规划或遗传算法。