旅行售货员

售货员"/>

旅行售货员

在递归算法Backtrack 中，当i=n时，当前扩展结点是排列树的叶结点的父结点。此时
算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。
如果这两条边都存在，则找到一.条旅行售货员回路。算法还需判断这条回路的费用是否优于
已找到的当前最优回路的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解
bestx。
解空间：排列树
时间复杂度：O（n！）

matrix = [[0, 1, 2, 3],[1, 0, 6, 8],[2, 6, 0, 2],[3, 8, 2, 0]
]def sum(path, matrix):res = 0path.append(path[0]) # 添加从最后一个节点到起始节点for i in range(len(path) - 1):res += matrix[path[i]][path[i + 1]]return resdef template(matrix):result = []def trace(path, choices): if len(path) == len(choices): # 终止条件result.append(list(path))returnfor i in range(len(choices)): # 选择if i in path or choices[path[-1]][i] == 0: # 剪枝continuepath.append(i)trace(path, choices) path.pop()# 回溯trace([0], matrix)res = [(sum(item, matrix), item) for item in result] # 排序选择最短路径res.sort()return res[0]template(matrix)