tsp问题贪心算法python

TSP（Traveling Salesman Problem）问题是一个经典的组合优化问题，目标是最短路径经过图中所有顶点一次并返回起点。贪心算法是一种启发式方法，它在每一步选择局部最优解，希望能达到全局最优。对于TSP，一种常见的贪心策略是“nearest neighbor”（最近邻）算法：

def nearest_neighbor(tsp_graph):
    unvisited = list(range(len(tsp_graph)))
    current_city = 0
    tour = [current_city]
    
    while unvisited:
        next_city = min(unvisited, key=lambda x: tsp_graph[current_city][x])  # 找到当前城市最邻近的未访问城市
        tour.append(next_city)
        unvisited.remove(next_city)
        
        if next_city != current_city:  # 如果不是直接回起点，更新当前城市
            current_city = next_city
            
    tour.append(current_city)  # 最后添加起点到路径结束，形成闭合环
    return tour

# 使用示例：
tsp_graph = [[0, 2, 9, 14], [2, 0, 10, 15], [9, 10, 0, 6], [14, 15, 6, 0]]  # 示例旅行商问题图
result = nearest_neighbor(tsp_graph)
print("按贪心策略找到的最短路径:", result)

然而，贪心算法并不能保证一定能找到TSP问题的全局最优解，尤其是在图中有负权边的情况下。对于这些问题，通常需要使用更复杂的方法，如动态规划、遗传算法或者混合智能搜索。