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

yipeiwu_com6年前Python基础

本文实例讲述了Python基于回溯法子集树模板解决旅行商问题(TSP)。分享给大家供大家参考,具体如下:

问题

旅行商问题(Traveling Salesman Problem,TSP)是旅行商要到若干个城市旅行,各城市之间的费用是已知的,为了节省费用,旅行商决定从所在城市出发,到每个城市旅行一次后返回初始城市,问他应选择什么样的路线才能使所走的总费用最短?

分析

此问题可描述如下:G=(V,E)是带权的有向图,找到包含V中每个结点一个有向环,亦即一条周游路线,使得这个有向环上所有边成本之和最小。

这个问题与前一篇文章/post/122933.htm的区别就是,本题是带权的图。只要一点小小的修改即可。

解的长度是固定的n+1。

对图中的每一个节点,都有自己的邻接节点。对某个节点而言,其所有的邻接节点构成这个节点的状态空间。当路径到达这个节点时,遍历其状态空间。

最终,一定可以找到最优解!

显然,继续套用回溯法子集树模板!!!

代码

'''旅行商问题(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 and x[k] in x[:k]:
    return True
  # 回到出发节点
  if k == n and x[k] != x[0]:
    return True
  # 前面部分解的旅费之和超出已经找到的最小总旅费
  cost = sum([graph[node1][node2] for node1,node2 in zip(x[:k], x[1:k+1])])
  if 0 < min_cost < cost:
    return True
  return False # 无冲突
# 旅行商问题(TSP)
def tsp(k): # 到达(解x的)第k个节点
  global n,a,b,c,d,e,graph,x,X,min_cost,best_x
  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 < min_cost:
      best_x = x[:]
      min_cost = cost
      #print(x)
  else:
    for node in graph[x[k-1]]: # 遍历节点x[k-1]的邻接节点(状态空间)
      x[k] = node
      if not conflict(k): # 剪枝
        tsp(k+1)
# 测试
x[0] = c # 出发节点:路径x的第一个节点(随便哪个)
tsp(1)  # 开始处理解x中的第2个节点
print(best_x)
print(min_cost)

效果图

更多关于Python相关内容可查看本站专题:《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总

希望本文所述对大家Python程序设计有所帮助。

相关文章

Python2和Python3中urllib库中urlencode的使用注意事项

前言 在Python中,我们通常使用urllib中的urlencode方法将字典编码,用于提交数据给url等操作,但是在Python2和Python3中urllib模块中所提供的urle...

Apache如何部署django项目

Apache如何部署django项目

在此之前,我们一直使用django的manage.py 的runserver 命令来运行django应用,但这只是我们的开发环境,当项目真正部署上线的时候这做就不可行了,必须将我们的项目...

JSON Web Tokens的实现原理

前言 最近在做一个Python项目的改造,将python项目重构为Java项目,过程中遇到了这个知识点,觉得这个蛮实用的,所以下班后回来趁热打铁写下这篇总结,希望后面的人能够有所借鉴,少...

django解决订单并发问题【推荐】

并发处理 在多个用户同时发起对同一个商品的下单请求时,先查询商品库存,再修改商品库存,会出现资源竞争问题,导致库存的最终结果出现异常。 解决办法: 悲观锁 当查询某条记录时,即让数...

Python3.7安装keras和TensorFlow的教程图解

Python3.7安装keras和TensorFlow的教程图解

win10 Python3.7安装keras深度学习集成包 TensorFlow 和Ubuntu下安装keras 在win10下安装 安装时必须检查你的python是否为64位,32位不...