贪心算法解决TSP python

TSP问题是指旅行商问题，即在给定的一些城市之间，求解访问每个城市一次并回到起始城市的最短路径。贪心算法可以用来解决TSP问题，但是只能得到近似最优解，而非精确最优解。

具体来说，贪心算法可以采用以下策略：
1. 选择一个起始城市。
2. 从起始城市开始，每次选择距离当前城市最近的未访问过的城市，并将其加入路径中。
3. 重复步骤2，直到所有城市都被访问过。
4. 将最后一个城市与起始城市相连，形成回路。

下面是一个使用贪心算法解决TSP问题的Python代码示例：

import math

def tsp(points):
    n = len(points)
    visited = [False] * n
    path = [0] * n
    visited[0] = True
    path[0] = 0
    for i in range(1, n):
        min_dist = math.inf
        for j in range(n):
            if not visited[j]:
                dist = math.sqrt((points[j][0] - points[path[i-1]][0])**2 + (points[j][1] - points[path[i-1]][1])**2)
                if dist < min_dist:
                    min_dist = dist
                    path[i] = j
        visited[path[i]] = True
    path.append(0)
    return path

# 示例
points = [(0, 0), (1, 1), (2, 2), (3, 3)]
path = tsp(points)
print(path)  # 输出 [0, 1, 2, 3, 0]