分支限界TSP（旅行商问题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了分支限界TSP（旅行商问题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

分支限界TSP（旅行商问题）

TSP 问题

【问题】

TSP 问题（traveling salesman problem）是指旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。

【想法】

首先确定目标函数的界[down, up]，可以采用贪心法确定 TSP 问题的一个上界。如何求得 TSP 问题的一个合理的下界呢？对于无向图的代价矩阵，把矩阵中每一行最小的元素相加，可以得到一个简单的下界。但是还有一个信息量更大的下界：考虑一个 TSP 问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以 2，假设图中所有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。需要强调的是，这个解可能不是一个可行解（可能没有构成哈密顿回路），但给出了一个参考下界。例如，对于图 (a)所示带权无向图， (b)是该图的代价矩阵，采用贪心法求得近似解为为 1→3→5→4→2→1，其路径长度为 1+2+3+7+3=16，这可以作为 TSP问题的上界。把矩阵中每一行最小的两个元素相加再除以 2，得到 TSP 问题的下界：[(1+3)+(3+6)+(1+2)+(3+4)+(2+3)]/2=14。于是，得到了目标函数的界[14, 16]。
分支限界TSP（旅行商问题）
一般情况下，假设当前已确定的路径为 U=(r 1 , r 2 , …, r k )，即路径上已确定了 k 个顶点，此时，该部分解的目标函数值的计算方法（即界限函数）如下：

例如，对于所示无向图，如果部分解包含的路径是 1-3-5，则该部分解的下界是 lb=[2×(1+2)+3+3+(3+6)+(3+4)]/2=14。
应用分支限界法求解所示无向图的 TSP 问题，其搜索空间如图所示，具体的搜索过程如下（其中加黑部分表示已经确定的路径）：
（1） 在根结点 1，计算目标函数值为 lb=[(1+3)+(3+6)+(1+2)+(3+4)+(2+3)]/2=14，将根结点加入待处理结点表 PT；
（2） 依次处理根结点的每一个孩子结点。在结点 2，已确定的路径是 1-2，路径长度为 3，则目标函数值为[2×3+1+6+(1+2)+(3+4)+(2+3)]/2=14，将结点 2 加入表 PT；在结点 3，已确定的路径是 1-3，路径长度为 1，则目标函数的值为[2×1+3+1+(3+6)+(3+4)+(2+3)]/2=14，将结点 3 加入表 PT 中；在结点 4，已确定的路径是 1-4，路径长度为 5，则目标函数的值为[2×5+1+3+(3+6)+(1+2)+(2+3)]/2=16，将结点 4 加入表 PT 中；在结点 5，已确定的路径是 1-5，路径长度为 8，则目标函数的值为[2×8+1+2+(3+6)+(1+2)+(3+4)]/2=19，超出目标函数的界，将结点 5 丢弃；
（3） 在表 PT 中选取目标函数值极小的结点 2 优先进行搜索；
（4） 依次处理结点 2 的每一个孩子结点。在结点 6，已确定路径 1-2-3，路径长度为 3+6=9，则目标函数值为[2×9+1+1+(3+4)+(2+3)]/2=16，将结点 6 加入表 PT；在结点 7，已确定路径 1-2-4，路径长度为 3+7=10，则目标函数值为[2×10+1+3+(1+2)+(2+3)]/2=16，将结点 7 加入表 PT；
在结点 8，已确定路径 1-2-5，路径长度为 3+9=12，则目标函数值为[2×12+1+2+(1+2)+(3+4)]/2=19，超出目标函数的界，将结点 8 丢弃；
（5） 在表 PT 中选取目标函数值极小的结点 3 优先进行搜索；
（6） 依次处理结点 3 的每一个孩子结点。在结点 9，已确定路径 1-3-2，路径长度为 1+6=7，则目标函数值为[2×7+3+3+(3+4)+(2+3)]/2=16，将结点 9 加入表 PT 中；在结点 10，已确定路径 1-3-4，路径长度为 1+4=5，则目标函数值为[2×5+3+3+(3+6)+(2+3)]/2=15，将结点 10 加入表 PT；在结点 11，已确定路径 1-3-5，路径长度为 1+2=3，则目标函数值为[2×3+3+3+(3+6)+(3+4)]/2=14，将结点 11 加入表 PT；
（7） 在表 PT 中选取目标函数值极小的结点 11 优先进行搜索；
（8） 依次处理结点 11 的每一个孩子结点。在结点 12，已确定路径 1-3-5-2，路径长度为 1+2+9=12，则目标函数值为[2×12+3+3+(3+4)]/2=19，超出目标函数的界，将结点 12 丢弃；在结点 13，已确定路径 1-3-5-4，路径长度为 1+2+3=6，则目标函数值为[2×6+3+4+(3+6)]/2=14，将结点 13 加入表 PT 中；
（9） 在表 PT 中选取目标函数值极小的结点 13 优先进行搜索；
（10） 依次处理结点 13 的每一个孩子结点。在结点 14，已确定路径 1-3-5-4-2，路径长度为1+2+3+7=13，则目标函数值为(2×13+3+3)/2=16，最后从城市 2 回到城市 1，路径长度为1+2+3+7+3=16，由于结点 14 为叶子结点，得到一个可行解，其路径长度为 16；
（11） 在表 PT 中选取目标函数值极小的结点 10 优先进行搜索；
（12） 依次处理结点 10 的每一个孩子结点。在结点 15，已确定路径 1-3-4-2，路径长度1+4+7=12，则目标函数值为[2×12+3+3+(2+3)]/2=18，超出目标函数的界，将结点 15 丢弃；在结点 16，已确定路径 1-3-4-5，路径长度为 1+4+3=8，则目标函数值为[2×8+3+2+(3+6)]/2=15，将结点 16 加入表 PT 中；
（13） 在表 PT 中选取目标函数值极小的结点 16 优先进行搜索；
（14） 依次处理结点 16 的每一个孩子结点。在结点 17，已确定路径 1-3-4-5-2，路径长度为1+4+3+9=17，则目标函数的值为(2×17+3+3)/2=20，超出目标函数的界，将结点 17 丢弃；
（15） 表 PT 中目标函数值均为 16，且有一个是叶子结点 14，所以，结点 14 对应的解即是 TSP 问题的最优解，搜索过程结束。为了求得最优解的各个分量，从结点 14开始向父结点进行回溯，得到最优解为 1→3→5→4→2→1。
分支限界TSP（旅行商问题）
文章来源地址https://www.toymoban.com/news/detail-480511.html