Python实现旅行商问题(TSP)算法：寻找最短路径

def tsp(current, visited, path, distance):
    '''
    使用递归和回溯法解决旅行商问题

    Args:
        current: 当前所在景点
        visited: 已经访问过的景点集合
        path: 当前路径
        distance: 当前路径总距离

    Returns:
        tuple: 最短路径和对应的总距离
    '''
    if len(visited) == n:
        return path, distance

    min_distance = float('inf')
    min_path = None

    for i in range(n):
        if i not in visited:
            visited.add(i)
            new_path, new_distance = tsp(i, visited, path + [i], distance + d[current][i])
            visited.remove(i)

            if new_distance < min_distance:
                min_distance = new_distance
                min_path = new_path

    return min_path, min_distance

if __name__ == '__main__':
    d = [
        [0, 300, 360, 210, 530, 475, 500, 690],  # 邻接矩阵，表示景点之间的距离
        [300, 0, 380, 270, 230, 285, 200, 390],
        [360, 380, 0, 510, 230, 665, 490, 680],
        [210, 270, 510, 0, 470, 265, 450, 640],
        [530, 230, 230, 470, 0, 515, 260, 450],
        [475, 285, 665, 265, 515, 0, 460, 650],
        [500, 200, 490, 450, 260, 460, 0, 190],
        [690, 390, 680, 640, 450, 650, 190, 0]
    ]
    n = len(d)  # 景点的数量

    start_point = 0 # 设置起点
    visited = set([start_point])  # 起点已访问
    path, distance = tsp(start_point, visited, [], 0)  # 调用tsp函数

    print('最短路径为：', path)
    print('最短距离为：', distance)