TSP贪心算法python

TSP问题（Traveling Salesman Problem）是指给定一个地图和地图上的若干个城市，求出一条经过每个城市恰好一次的最短路径。TSP问题是一个经典的组合优化问题，目前没有已知的多项式算法能够解决其最优解。但是，我们可以采用一些近似算法来解决该问题，其中贪心算法是其中一种。

TSP贪心算法思路：从一个起点开始，每次选择距离当前节点最近的未访问节点作为下一个节点，并将该节点标记为已访问，重复该过程直到所有节点都被访问。由于这种贪心算法只考虑了当前步骤的最优解，而没有考虑到整体最优解，所以该算法并不能保证得到全局最优解。

以下是TSP贪心算法的python实现：

import math

def tsp_greedy(city_list):
    visited = [False] * len(city_list)
    visited = True
    path = 
    cur = 0
    for i in range(1, len(city_list)):
        min_dist = float('inf')
        next_city = -1
        for j in range(len(city_list)):
            if not visited[j]:
                dist = math.sqrt((city_list[cur] - city_list[j])**2 + (city_list[cur] - city_list[j])**2)
                if dist < min_dist:
                    min_dist = dist
                    next_city = j
        visited[next_city] = True
        path.append(next_city)
        cur = next_city
    path.append(0)
    return path

city_list = [[0, 0], [1, 3], [2, 4], [5, 3], [6, 1]]
print(tsp_greedy(city_list))