Python基于回溯法子集树模板解决旅行商问题(TSP)实例
作者:罗兵 时间:2023-04-27 15:39:32
本文实例讲述了Python基于回溯法子集树模板解决旅行商问题(TSP)。分享给大家供大家参考,具体如下:
问题
旅行商问题(Traveling Salesman Problem,TSP)是旅行商要到若干个城市旅行,各城市之间的费用是已知的,为了节省费用,旅行商决定从所在城市出发,到每个城市旅行一次后返回初始城市,问他应选择什么样的路线才能使所走的总费用最短?
分析
此问题可描述如下:G=(V,E)是带权的有向图,找到包含V中每个结点一个有向环,亦即一条周游路线,使得这个有向环上所有边成本之和最小。
这个问题与前一篇文章https://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程序设计有所帮助。
来源:http://www.cnblogs.com/hhh5460/p/6929822.html
标签:Python,回溯法,子集树模板
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python生成器generator原理及用法解析
2021-10-14 14:00:13
![](https://img.aspxhome.com/file/2023/8/92408_0s.jpg)
Django 用户认证组件使用详解
2021-05-11 12:44:25
sqlserver之datepart和datediff应用查找当天上午和下午的数据
2024-01-14 22:27:42
详解python调度框架APScheduler使用
2021-11-05 22:55:36
从p开始,循序渐进学习WEB标准
2008-03-08 18:53:00
python3读取图片并灰度化图片的四种方法(OpenCV、PIL.Image、TensorFlow方法)总结
2021-06-20 20:47:41
![](https://img.aspxhome.com/file/2023/8/108008_0s.png)
PHP采集静态页面并把页面css,img,js保存的方法
2023-10-22 19:44:22
PYQT5 vscode联合操作qtdesigner的方法
2023-10-31 16:46:41
![](https://img.aspxhome.com/file/2023/9/121889_0s.jpg)
Python编程图形库之Pillow使用方法讲解
2022-04-07 06:10:57
![](https://img.aspxhome.com/file/2023/5/80425_0s.png)
mysql 批处理文件出错后继续执行的实现方法
2024-01-19 13:25:09
你的网站使用了微格式了么
2009-05-21 12:10:00
js控制图片闪烁代码
2008-07-30 12:35:00
对Python中画图时候的线类型详解
2021-02-22 00:18:43
![](https://img.aspxhome.com/file/2023/6/133656_0s.jpg)
如何把数据库的记录输出到表格去?
2009-11-06 13:37:00
Django Path转换器自定义及正则代码实例
2022-05-19 09:01:25
MySQL8.0+版本1045错误的问题及解决办法
2024-01-16 23:19:33
![](https://img.aspxhome.com/file/2023/9/72499_0s.png)
python实现pptx批量向PPT中插入图片
2021-10-05 23:18:29
![](https://img.aspxhome.com/file/2023/6/131606_0s.jpg)
Python利用Pydub实现自动分割音频
2022-10-08 22:02:48
CSS属性behavior的语法及介绍
2010-01-13 12:40:00
Python使用sftp实现传文件夹和文件
2021-09-30 12:27:37
![](https://img.aspxhome.com/file/2023/1/76881_0s.jpg)