旅行商售货贪心算法代码

旅行商问题是一个经典的组合优化问题，目的是找到一条经过所有城市的最短路径。贪心算法是解决该问题的一种方法，被称为旅行商售货问题的近似解。

旅行商售货贪心算法的思路如下：

1. 选定一个起点城市。
2. 找到离起点城市最近的未访问过的城市，并将其作为下一个要访问的城市。
3. 重复第二步，直到所有城市都被访问过。
4. 将最后一个城市与起点城市连成一条路径，得到最终路径。

以下是旅行商售货贪心算法的代码示例（Python）：

def tsp_greedy(city_distances):
    # 随机选定一个起点城市
    start_city = random.choice(list(city_distances.keys()))

    # 记录已访问的城市和路径长度
    visited_cities = [start_city]
    path_length = 0

    # 按照贪心策略选择下一个要访问的城市
    while len(visited_cities) < len(city_distances):
        last_city = visited_cities[-1]
        next_city = min(city_distances[last_city], key=city_distances[last_city].get)
        path_length += city_distances[last_city][next_city]
        visited_cities.append(next_city)

    # 将最后一个城市与起点城市相连
    path_length += city_distances[visited_cities[-1]][start_city]

    return visited_cities, path_length