回溯法---旅行商问题

• 程语言Python
• 难度 中等

问题描述：

给定一组城市和每对城市之间的距离，找到一条最短路径，使得一位旅行商从一个城市出发后，恰好访问每个城市一次，并最终返回出发的城市。

问题特点：

完整性：

旅行商需要访问所有给定的城市。

唯一性：

每个城市只能访问一次（除了起始城市，它既是起点也是终点）。

闭合性：

旅行路线必须形成一个环路，即旅行商最后要回到出发点。

最优性：

寻找的路径应该是所有可能路径中最短的一条。

数学表示：

测试用例：

ifname== "main": import sys NoEdge = sys.maxsize a = [[0,0,0,0,0,0],[0,NoEdge,10,NoEdge,4,12],[0,10,NoEdge,15,8,5],[0,NoEdge,15,NoEdge,7,30],[0,4,8,7,NoEdge,6],[0,12,5,30,6,NoEdge]] n = len(a) x = [i for i in range(n)] bestx =None bestc = NoEdge cc = 0 backtrack(2)#第一个城市固定，所以从第二层开始搜索 print("最短路径长度为：", bestc) print("最短路径为：", bestx)

源码：

import sys def backtrack(t): global cc, bestc, bestx, x, a, n, NoEdge # 递归终止：遍历完所有城市，计算返回起点的总距离 if t == n: # 总距离 = 当前路径长度 + 最后一个城市回到起点的距离 total = cc + a[x[n-1]][x[1]] if total < bestc: bestc = total # 深拷贝当前路径，避免后续修改影响最优解 bestx = x.copy() else: # 遍历t到n-1的城市，生成排列（选择下一个要访问的城市） for i in range(t, n): # 交换x[t]和x[i]，选择第i个城市作为当前层的选择 x[t], x[i] = x[i], x[t] # 剪枝：当前路径长度 + 上一个城市到当前城市的距离 < 最优解，才继续搜索 if cc + a[x[t-1]][x[t]] < bestc: # 更新当前路径长度 cc += a[x[t-1]][x[t]] # 递归搜索下一层 backtrack(t + 1) # 回溯：恢复当前路径长度 cc -= a[x[t-1]][x[t]] # 回溯：恢复x的顺序 x[t], x[i] = x[i], x[t] if __name__ == "__main__": NoEdge = sys.maxsize # 表示无路径（本题中未用到，仅占位） # 距离矩阵：a[i][j]表示城市i到城市j的距离，索引0无意义，有效城市为1-5 a = [ [0, 0, 0, 0, 0, 0], [0, NoEdge, 10, NoEdge, 4, 12], [0, 10, NoEdge, 15, 8, 5], [0, NoEdge, 15, NoEdge, 7, 30], [0, 4, 8, 7, NoEdge, 6], [0, 12, 5, 30, 6, NoEdge] ] n = len(a) # n=6，对应城市索引0(无效)、1、2、3、4、5 x = [i for i in range(n)] # 当前路径，初始为[0,1,2,3,4,5] bestx = None # 最优路径 bestc = NoEdge # 最优路径长度，初始为极大值 cc = 0 # 当前路径长度 backtrack(2) # 第一个城市（x[1]=1）固定，从第2层开始搜索 print("最短路径长度为：", bestc) print("最短路径为：", bestx)