分枝定界算法的基本思路如下:
假设有最小化的整数规划问题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)