贪心算法tsp问题python

下面是使用Python实现TSP问题的贪心算法：

import math

def tsp(points):
    # 计算两点之间的距离
    def distance(point1, point2):
        return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)

    # 计算路径长度
    def path_length(path):
        length = 0
        for i in range(len(path) - 1):
            length += distance(points[path[i]], points[path[i+1]])
        return length

    # 选择下一个要访问的城市
    def choose_next_city(current_city, unvisited_cities):
        next_city = None
        min_distance = float('inf')
        for city in unvisited_cities:
            d = distance(points[current_city], points[city])
            if d < min_distance:
                min_distance = d
                next_city = city
        return next_city

    # 贪心算法
    path = [0]  # 起点为0号城市
    unvisited_cities = set(range(1, len(points)))
    while unvisited_cities:
        next_city = choose_next_city(path[-1], unvisited_cities)
        path.append(next_city)
        unvisited_cities.remove(next_city)
    path.append(0)  # 回到起点
    return path_length(path), path

其中，`points`是一个二维坐标列表，表示每个城市的坐标。函数返回值为最短路径长度和路径。