运筹学教学|分枝定界求解旅行商问题

分枝定界(branch and bound)某年某月某日,小编正在绝地岛横行霸道。此时,突然手机屏幕一亮,老板来电话,说是有一个branch and bound要写,小编内心一凉,冒着被打成盒子的危险,给出了这个推文。利用分支定界求解旅行商问题(Travelling Salesman Problem,TSP)

分枝定界算法的基本思路如下:

假设有最小化的整数规划问题A,它相应的线性松弛(LP relaxation)规划问题为B。从解问题B开始,若其最优解不符合A的整数条件,那么B的最优目标函数值必是A的最优目标函数值 z* 的下界,记作 Z ;而 A 的任意可行解的目标函数值将是 z* 的一个上界 z 。分枝定界法就是将 A 的可行域分成子区域的方法,逐步增大 Z 和减小z ,最终求到 z* 。

通常,把全部可行解空间反复地分割为越来越小的子集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于最小值问题),这称为定界。在每次分枝后,凡是界限超出已知可行解集目标值(即上界)的那些子集不再进一步分枝,这样,许多子集可不予考虑,这称为剪枝。这就是分枝定界法的主要思路。

求解TSP通常采用的定界方法是用分配问题定界或者是1-tree来定界。

分配问题的匈牙利算法在之前的文章中有过介绍,在此便不再赘述,详情请参考本公众号文章

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

关于1-tree我们在这里简单介绍一下,更加详细的介绍将会在之后的附件中给出,请关注留言区

在一个图G(V,E)中,节点集合V = {1...n},我们定义{2...n}节点组成的子图的生成树以及两条与1节点的边组成的新图为1-tree。如下图:

TSP的可行解是1-tree的一种,因此最小权值1-tree (minimum weight 1-tree)可以作为TSP的一个下界,因此可以利用这个性质来作为定界的标准。

最小权值1-tree的很容易求得,只需要求解子图{2...n}的最小生成树再加上两条与1节点相连的最短的边即可。

一棵1-tree是一个TSP的可行解的充要条件是1-tree中所有节点的度(degree)均为2。这样分枝的方法也就有了,即寻找1-tree中所有度大于等于3的节点,枚举并依次删除这个节点所有的边,依次求解最小权值1-tree,直到找到可行的TSP解。如下图所示:

上面就是关于使用分枝定界算法求解TSP的基本思路,如果读者有什么不懂的地方,可以参考留言区给出的链接,其中有一份详细介绍上述算法的PPT,相信一定能解决你的问题!

在本文的代码中,求解分配问题采用的是之前推文中提到的匈牙利算法,用system调用Hungary.exe来求解并利用get_circle函数来判断环路。1-tree的求解采用的是kruscal算法,也就是里面的kruscal函数。之后用degree_c函数来检查节点的度。分枝定界搜索过程是采用递归的方法实现的,递归的两个函数分别为branch_and_bound_hungary 和branch_and_bround_one。

代码时刻

又到了看代码的季节了,想要下载文字版的代码请移步全文链接,或者打开下面的网址:https://paste.ubuntu.com/26159997/,或者去留言区获取资源下载链接。

算例展示:

输入:

(第一行整数代表城市数目n,接下来第i(i = 1,2,...,n)行每行n个数分别表示城市i到其他城市的距离,极大的正数使用99999)

5

99999 132 217 164 58

132 99999 290 201 79

217 290 99999 113 303

164 201 113 99999 196

58 79 303 196 99999

输出:

ans = 668(表示最小路径长度)

P.S.输出有很多行,只需要关注最后一行(有last_ans的一行)即可,输出中还有一个文件名,路径方案被保存在这个文件中。使用匈牙利算法定界时还需要一个编译好的匈牙利算法的exe文件。具体的使用说明在留言区的网盘链接中给出。

编辑:贺兴(hexing15@gmail.com)

华中科技大学管理学院本科三年级

代码:贺兴(hexing15@gmail.com)

华中科技大学管理学院本科三年级

汪文宇(wangwenyu0928@gmail.com)

华中科技大学管理学院本科四年级

指导老师:秦时明岳(professor.qin@qq.com)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2017-12-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

博客 | MNIST 数据集载入线性模型

这节开始我们使用知名的图片数据库 「THE MNIST DATABASE」 作为我们的图片来源,它的数据内容是一共七a万张 28×28 像素的手写数字图片,并被...

1535
来自专栏机器学习算法原理与实践

用gensim学习word2vec

    在word2vec原理篇中,我们对word2vec的两种模型CBOW和Skip-Gram,以及两种解法Hierarchical Softmax和Nega...

2293
来自专栏hadoop学习笔记

HanLP中人名识别分析详解

分词:给定一个字的序列,找出最可能的标签序列(断句符号:[词尾]或[非词尾]构成的序列)。结巴分词目前就是利用BMES标签来分词的,B(开头),M(中间),E(...

1303
来自专栏机器学习之旅

基于Tensorflow实现DeepFM前言网络结构代码部分

DeepFM,Ctr预估中的大杀器,哈工大与华为诺亚方舟实验室荣耀出品,算法工程师面试高频考题,有效的结合了神经网络与因子分解机在特征学习中的优点:同时提取到低...

2124
来自专栏数据结构与算法

05:Cave Cows 1 洞穴里的牛之一

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 很少人知道其实奶牛非常喜欢到洞穴里面去探险。     洞窟里有N...

2967
来自专栏京东技术

【解题报告】看雪·京东2018CTF—京东AI CTF大挑战特别题

近日,京东安全联合安全界的黄埔军校看雪论坛举办了一次线上CTF大赛,近3w人参赛。参与解答“京东AI CTF大挑战特别题”的同学有1435人,最终解出题目的只有...

1492
来自专栏AI科技评论

开发 | TensorFlow中RNN实现的正确打开方式

上周写的文章《完全图解RNN、RNN变体、Seq2Seq、Attention机制》介绍了一下RNN的几种结构,今天就来聊一聊如何在TensorFlow中实现这些...

4945
来自专栏月色的自留地

从锅炉工到AI专家(9)

2246
来自专栏机器之心

教程 | TensorFlow从基础到实战:一步步教你创建交通标志分类神经网络

选自DataCamp 作者:Karlijn Willems 机器之心编译 参与:Panda TensorFlow 已经成为了现在最流行的深度学习框架,相信很多对...

5236
来自专栏1039778的专栏

Python 数据分析学习笔记

一、基本语法 [1507772432114_7239_1507772402948.jpg] 资料地址:http://www.icoolxue.com/album...

1.3K9

扫码关注云+社区

领取腾讯云代金券