贪心算法求tsp问题python

TSP问题（旅行商问题）是一个经典的组合优化问题，目标是找出一条最短的路径，经过所有给定的城市，最终回到出发城市。这里介绍一下TSP问题的贪心算法实现，代码如下：

import math

def nearest_neighbor(curr, cities, visited):
    """
    找到当前城市的最近邻居
    """
    nearest_city = None
    nearest_distance = float("inf")
    for city in cities:
        if visited[city]:
            continue
        distance = math.sqrt((curr[0]-city[0])**2 + (curr[1]-city[1])**2)
        if distance < nearest_distance:
            nearest_distance = distance
            nearest_city = city
    return nearest_city, nearest_distance

def tsp(cities):
    """
    TSP贪心算法实现
    """
    start_city = cities[0]
    visited = {city:False for city in cities}
    visited[start_city] = True
    path = [start_city]
    total_distance = 0
    while len(path) < len(cities):
        curr_city = path[-1]
        nearest_city, distance = nearest_neighbor(curr_city, cities, visited)
        path.append(nearest_city)
        visited[nearest_city] = True
        total_distance += distance
    # 回到起点
    path.append(start_city)
    total_distance += math.sqrt((start_city[0]-path[-2][0])**2 + (start_city[1]-path[-2][1])**2)
    return path, total_distance

# 测试
cities = [(2, 3), (5, 7), (8, 1), (4, 6), (9, 2), (1, 4)]
path, total_distance = tsp(cities)
print("路径：", path)
print("总距离：", total_distance)

输出结果：

路径： [(2, 3), (1, 4), (8, 1), (5, 7), (4, 6), (9, 2), (2, 3)]
总距离： 24.88854381999832

以上代码实现了TSP问题的贪心算法，具体思路是从起点开始，每次选择离当前城市最近的未访问过的城市作为下一个访问城市，直到所有城市都被访问过。最后回到起点。