旅行商问题TSP代码

以下是一个简单的 TSP（旅行商问题）的 Python 代码实现，使用贪心算法：

import math

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

# 计算从当前城市出发到未访问过的城市的距离
def nearest_neighbor(current_city, unvisited_cities):
    return min(unvisited_cities, key=lambda city: distance(current_city, city))

# TSP主函数
def tsp(cities):
    start_city = cities[0]
    unvisited_cities = set(cities[1:])
    tour = [start_city]

    while unvisited_cities:
        nearest_city = nearest_neighbor(tour[-1], unvisited_cities)
        tour.append(nearest_city)
        unvisited_cities.remove(nearest_city)

    tour.append(start_city)
    return tour

# 测试
if __name__ == "__main__":
    cities = [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]
    print(tsp(cities))

输出结果为：

[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (0, 0)]

这表示从起点出发，按照距离最近的顺序访问每个城市，最后回到起点的路径为 `(0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> (4, 4) -> (5, 5) -> (0, 0)`。