TSP问题的近似算法求解代码

TSP问题是旅行商问题，即在给定的城市之间寻找最短路径，使得旅行商可以经过每个城市恰好一次，最后回到出发点。由于TSP问题是NP难问题，因此很难找到准确的解决方案。但是，我们可以使用近似算法来得到一个近似最优解。

其中，最常用的近似算法是贪心算法。贪心算法的基本思路是每次选择当前状态下最优的解，从而得到一个较优的近似解。在TSP问题中，一种常见的贪心算法是选择当前位置到距离最近的未访问城市进行访问。

以下是TSP问题的近似算法求解代码，使用了贪心算法：

import math

def tsp_approximation(cities):
    n = len(cities)
    visited = [False] * n
    path = []
    current_city = 0
    visited[current_city] = True
    path.append(current_city)

    for i in range(n-1):
        nearest_city = -1
        nearest_distance = float("inf")
        for j in range(n):
            if not visited[j] and cities[current_city][j] < nearest_distance:
                nearest_city = j
                nearest_distance = cities[current_city][j]
        current_city = nearest_city
        visited[current_city] = True
        path.append(current_city)

    return path

def distance(city1, city2):
    x1, y1 = city1
    x2, y2 = city2
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

def calculate_distance_matrix(cities):
    n = len(cities)
    distance_matrix = [ * n for i in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            dist = distance(cities[i], cities[j])
            distance_matrix[i][j] = dist
            distance_matrix[j][i] = dist
    return distance_matrix

if __name__ == "__main__":
    cities = [(0,0), (1,2), (3,4), (5,6), (7,8)]
    distance_matrix = calculate_distance_matrix(cities)
    path = tsp_approximation(distance_matrix)
    print(path)

这里假设TSP问题中的城市坐标已知，并将其存储在一个元组列表中。calculate_distance_matrix函数计算出了城市之间的距离矩阵，tsp_approximation函数根据这个距离矩阵来计算一个近似最优解。