TSP问题-python解法

---

作业

---

题目：

从城市A出发，访问到所有城市且仅访问一次，最后回到城市A，找出所有路径中符合上述要求且代价最小的路径。输出： 最短路径损失和所有最短路径。

---

主体思路：

通过dfs遍历所有路径，并计算每条路径的总成本。比较所有路径的总成本，找出最短的路径。

---

模块解释：

(一) 城市cost矩阵 dist

dist = [
    [0, 1, max, max, max, max, 0.5, 1],
    [1, 0, 1, max, max, max, 1, max],
    [max, 1, 0, 1, max, 2, max, max],
    [max, max, 1, 0, 5, max, max, max],
    [max, max, max, 5, 0, 1, max, max],
    [max, max, 2, max, 1, 0, 0.5, 1],
    [0.5, 1, max, max, max, 0.5, 0, max],
    [1, max, max, max, max, 1, max, 0]
]

Dist为代表城市间代价的矩阵，行（从左到右）和列（从上到下）代表A城市到G城市。

Eg：dist1代表城市A到城市A间的距离(cost)。

(二) min_cost, all_routes = tsp_divide_and_conquer(dist)

tsp_divide_and_conquer(dist)为定义的函数，包含
初始化和嵌套的递归dfs函数两部分。
dfs 探索所有可能的路径，计算每条路径的总成本，并更新最短路径。
1 path：表示当前路径上的城市。
2 visited：一个布尔数组，表示每个城市是否已经被访问过。
3 cost：当前路径的已走的总成本。

在每次递归中，DFS会选择一个未访问的城市，并递归地访问其他城市，直到遍历完所有城市。

源代码：

TSP-fenzhi.zip

运行结果：