实例讲解Python基于回溯法子集树模板解决旅行商问题（TSP）

'''旅行商问题（Traveling Salesman Problem,TSP）'''# 用邻接表表示带权图n = 5 # 节点数a,b,c,d,e = range(n) # 节点名称graph = [  {b:7, c:6, d:1, e:3},  {a:7, c:3, d:7, e:8},  {a:6, b:3, d:12, e:11},  {a:1, b:7, c:12, e:2},  {a:3, b:8, c:11, d:2}]x = [0]*(n+1) # 一个解（n+1元数组，长度固定）X = []     # 一组解best_x = [0]*(n+1) # 已找到的最佳解（路径）min_cost = 0    # 最小旅费# 冲突检测def conflict(k):  global n,graph,x,best_x,min_cost  # 第k个节点，是否前面已经走过  if k  n: # 解的长度超出，已走遍n+1个节点 （若不回到出发节点，则 k==n）    cost = sum([graph[node1][node2] for node1,node2 in zip(x[:-1], x[1:])]) # 计算总旅费    if min_cost == 0 or cost <p><span style="font-size: medium"><strong>效果图</strong></span></p><p><img src="https://img.php.cn/upload/article/000/000/007/d02e1dc89544204ff1cf066c2144afd5-1.jpg" alt=""></p>