首页 后端开发 Python教程 实例讲解Python基于回溯法子集树模板解决旅行商问题(TSP)

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

Sep 07, 2017 am 10:14 AM
python 回溯 基于

这篇文章主要介绍了Python基于回溯法子集树模板解决旅行商问题(TSP),简单描述了旅行商问题并结合实例形式分析了Python使用回溯法子集树模板解决旅行商问题的相关实现步骤与操作技巧,需要的朋友可以参考下

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

问题

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

分析

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

这个问题与前一篇文章http://www.jb51.net/article/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基于回溯法子集树模板解决旅行商问题(TSP)的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Linux系统自带Python解释器能删除吗? Linux系统自带Python解释器能删除吗? Apr 02, 2025 am 07:00 AM

关于Linux系统自带Python解释器的删除问题许多Linux发行版在安装时会预装Python解释器,它并非通过软件包管理器�...

如何解决Python中自定义装饰器的Pylance类型检测问题? 如何解决Python中自定义装饰器的Pylance类型检测问题? Apr 02, 2025 am 06:42 AM

使用自定义装饰器时的Pylance类型检测问题解决方法在Python编程中,装饰器是一种强大的工具,可以用于添加行�...

Python 3.6加载pickle文件报错ModuleNotFoundError: No module named '__builtin__'怎么办? Python 3.6加载pickle文件报错ModuleNotFoundError: No module named '__builtin__'怎么办? Apr 02, 2025 am 06:27 AM

Python3.6环境下加载pickle文件报错:ModuleNotFoundError:Nomodulenamed...

在Linux终端中使用python --version命令时如何解决权限问题? 在Linux终端中使用python --version命令时如何解决权限问题? Apr 02, 2025 am 06:36 AM

Linux终端中使用python...

FastAPI 和 aiohttp 是否共享同一个全局事件循环? FastAPI 和 aiohttp 是否共享同一个全局事件循环? Apr 02, 2025 am 06:12 AM

Python异步库之间的兼容性问题在Python中,异步编程已经成为处理高并发和I/O...

如何在Python中通过信号杀死父进程后确保子进程也终止? 如何在Python中通过信号杀死父进程后确保子进程也终止? Apr 02, 2025 am 06:39 AM

使用信号杀死父进程时,子进程继续运行的问题及解决方案在Python编程中,通过信号杀死父进程后,子进程仍然...

Python 3.6加载Pickle文件报错"__builtin__"模块未找到怎么办? Python 3.6加载Pickle文件报错"__builtin__"模块未找到怎么办? Apr 02, 2025 am 07:12 AM

Python3.6环境下加载Pickle文件报错:ModuleNotFoundError:Nomodulenamed...

See all articles