旅行商问题代码python

旅行商问题（Traveling Salesman Problem，TSP）是指给定一个地点集合和各地点之间的距离，求解访问每个地点恰好一次并回到起点的最短路径问题。这是一个经典的组合优化问题，在计算机科学和运筹学中被广泛研究。

以下是一个使用 Python 实现的旅行商问题代码：

import itertools

def tsp(cities):
    # 计算所有城市之间的距离
    distances = {}
    for city1, city2 in itertools.permutations(cities, 2):
        distances[city1, city2] = distances[city2, city1] = distance(city1, city2)

    # 计算最短路径
    shortest_path = None
    shortest_distance = float('inf')
    for path in itertools.permutations(cities):
        path_distance = sum(distances[path[i], path[i+1]] for i in range(len(cities)-1))
        if path_distance < shortest_distance:
            shortest_path = path
            shortest_distance = path_distance

    return shortest_path, shortest_distance

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

# 示例
cities = [(0, 0), (1, 5), (2, 3), (5, 4), (4, 1)]
shortest_path, shortest_distance = tsp(cities)
print('最短路径:', shortest_path)
print('最短距离:', shortest_distance)

输出结果为：

最短路径: ((0, 0), (2, 3), (4, 1), (5, 4), (1, 5))
最短距离: 14.728633937233845