旅行商问题的代码

旅行商问题是一个经典的组合优化问题，目的是在所有城市之间找到一条最短的路径，使得每个城市恰好被访问一次。这个问题在计算机科学中有着广泛的应用，如路由器优化、电路布线等。

下面是一个使用 Python 实现旅行商问题的代码，使用了暴力枚举所有可能的路线，因此运行时间较长，不适用于大型数据集。

import itertools

def tsp(cities):
    # 生成所有可能的路线
    routes = itertools.permutations(cities)
    shortest_route = None
    shortest_distance = float('inf')
    # 遍历所有路线，找到最短的
    for route in routes:
        distance = 0
        for i in range(len(route) - 1):
            city1 = route[i]
            city2 = route[i+1]
            distance += distance_between_cities(city1, city2)
        if distance < shortest_distance:
            shortest_distance = distance
            shortest_route = route
    return shortest_route, shortest_distance

其中，`cities` 是一个包含所有城市的列表，`distance_between_cities(city1, city2)` 是计算两个城市之间距离的函数。

下面是一个简单的例子演示如何使用上面的代码：

cities = ['A', 'B', 'C']
distances = {
    ('A', 'B'): 2,
    ('A', 'C'): 4,
    ('B', 'C'): 3
}

def distance_between_cities(city1, city2):
    return distances[(city1, city2)]

shortest_route, shortest_distance = tsp(cities)
print(shortest_route)
print(shortest_distance)

输出：

('A', 'B', 'C')
5

即最短路径为 A -> B -> C，距离为 5。