Python 旅行商问题 (TSP) 算法实现 - 限制条件优化

def tsp(current, visited, path, distance, start, end):
    if len(visited) == n and current == end:  # 已经访问了所有景点且当前景点是终点
        path.append(current)  # 将最后一个景点添加到路径中
        distance += d[current][start]  # 加上回到起点的距离
        return path, distance  # 返回路径和总距离

    min_distance = float('inf')  # 初始化最小距离为无穷大
    min_path = None  # 初始化最短路径为空

    for i in range(1, n):  # 遍历未访问的景点
        if i not in visited and not (current == start and 3 in visited):  # 添加限制条件
            visited.add(i)  # 将当前景点添加到已访问集合中
            new_path, new_distance = tsp(i, visited, path + [current], distance + d[current][i], start, end)  # 递归调用
            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 = 0  # 起点编号
    end = 1  # 终点编号

    visited = set([start])  # 起点已经被访问
    path, distance = tsp(start, visited, [], 0, start, end)  # 调用tsp函数

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

这段代码实现了旅行商问题 (TSP) 算法，并添加了一个限制条件：不允许从起点 0 号到景点 3 号后进行路径规划。这个限制条件通过在递归调用之前添加判断条件来实现：

if i not in visited and not (current == start and 3 in visited):  # 添加限制条件

当当前景点为起点 0 号，并且已经访问了景点 3 号时，这个条件将为 True，从而跳过当前景点，不进行递归调用。这样就能避免从起点 0 号到景点 3 号的路径被包含在最终的解中。

这段代码简洁易懂，适合初学者学习。你可以通过修改代码中的参数来测试不同的场景，并观察限制条件对结果的影响。

注意：

• 邻接矩阵 d 表示了景点之间的距离。
• start 和 end 分别代表起点和终点。
• 代码中 visited 集合用来记录已经访问过的景点。
• path 列表用来记录最终的路径。
• distance 记录了路径的总距离。

你可以根据自己的需求修改代码中的参数和限制条件，以满足不同的应用场景。