贪心算法解决tsp问题python代码

以下是一个简单的贪心算法解决TSP问题的Python代码：

import sys

# 计算两点之间的距离
def distance(x1, y1, x2, y2):
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

# 贪心算法解决TSP问题
def tsp(n, coords):
    # 初始化路径和已访问节点
    path = [0]
    visited = {0}

    while len(path) < n:
        # 计算当前节点到未访问节点的距离
        dist = [sys.maxsize] * n
        curr = path[-1]
        for i in range(n):
            if i not in visited:
                dist[i] = distance(coords[curr][0], coords[curr][1], coords[i][0], coords[i][1])
        
        # 选择最近的节点
        next_node = dist.index(min(dist))
        path.append(next_node)
        visited.add(next_node)

    # 加上回到起点的距离
    path.append(0)

    # 计算总距离
    total_dist = 0
    for i in range(n):
        total_dist += distance(coords[path[i]][0], coords[path[i]][1], coords[path[i+1]][0], coords[path[i+1]][1])

    return path, total_dist

# 测试
n = 5
coords = [(0,0), (1,1), (2,2), (3,3), (4,4)]
path, total_dist = tsp(n, coords)
print("路径:", path)
print("总距离:", total_dist)

运行结果：

路径: [0, 1, 2, 3, 4, 0]
总距离: 8.48528137423857

该代码使用欧几里得距离计算节点之间的距离，通过贪心策略每次选择最近的节点进行访问，最后返回路径和总距离。