jac*_*627 3 traveling-salesman lower-bound
我目前正在研究旅行商问题,并且想知道是否有人能够简单地解释持有的karp下限.我一直在看很多论文,我很难理解它.如果有人可以简单地解释它会很棒.
我也知道有一种计算不包括起始顶点的顶点的最小生成树然后从起始顶点添加两个最小边的方法.
小智 8
我会尝试解释这一点,而不会涉及太多细节.我会避免正式的证据,我会尽量避免使用技术术语.但是,一旦你阅读了所有内容,你可能想要再次检查所有内容.最重要的是; 自己尝试算法.
介绍
1-tree树是一个树,由一个顶点连接到生成树的2个边.您可以自己检查每个TSP之旅是1-Tree.
还有图表的最小1-Tree这样的东西.这是您遵循此算法时生成的树:
*现在我假设您知道最小1树是最佳TSP巡回的下限.最后有一个非正式的证明.
当您排除不同的顶点时,您会发现生成的树是不同的.但是,所有生成的树都可以被认为是TSP中最佳游览的下限.因此,你发现这种方式中最小的1棵树是最好的下限然后其他人就是这样找到的.
Held-Karp下限
Held-Karp下界是一个更严格的下界.
这个想法是你可以用一种特殊的方式改变原始图形.此修改后的图形将生成与原始树不同的最小1树.
此外(这很重要,所以我将在本段中用不同的词重复它),修改是这样的,所有有效的TSP游览的长度由相同的(已知的)常数修改.换句话说,此新图中有效TSP解的长度=原始图中有效解的长度加上已知常量.例如:假设在原始图形中按顺序访问顶点A,B,C和D的TSP巡视的权重= 10.然后,在修改的图形中以相同顺序访问相同顶点的TSP巡视的权重= 10 +一个已知的常数.
当然,这对于最佳TSP巡回赛也是如此.因此,修改图中的最佳TSP巡回也是原始图中的最佳巡回.并且修改图的最小1-树是修改图中最佳巡回的下界.同样,我只是假设您理解这会为您修改的图形的最佳TSP巡视生成下限.通过从修改后的图形的下限中减去另一个已知常量,您的原始图形具有新的下限.
您的图表中有无数的此类修改.这些不同的修改导致不同的下限.这些下界中最紧密的是Held-Karp下界.
如何修改图表
现在我已经解释了Held-Karp下限是什么,我将向您展示如何修改图形以生成不同的最小1树.
使用以下算法:
例如,原始图形具有顶点A,B和C,边缘AB = 3,边缘AC = 5,边缘BC = 4.对于算法,您将(任意)权重分配给顶点A:30,B: 40,C:50然后,修改后的图中边缘的最终权重为AB = 3 + 30 + 40 = 73,AC = 5 + 30 + 50 = 85,BC = 4 + 40 + 50 = 94.
修改的已知常数是给予顶点的权重之和的两倍.在此示例中,已知常量为2*(30 + 40 + 50)= 240.注意:修改后的图形中的游览因此等于原始游览+ 240.在此示例中,只有一个游览即ABC.原始图形中的游览长度为3 + 4 + 5 = 12.修改后的图形中的游览长度为73 + 85 + 94 = 252,实际上为240 + 12.
常量等于给予顶点的权重之和的两倍的原因是因为TSP巡视中的每个顶点都具有阶数2.
你需要另一个已知的常数.您从最小1树中减去常数以得到下限.这取决于找到的最小1树的顶点的程度.您需要将给定每个顶点的权重乘以该最小1树中的顶点的度数.全部加起来.例如,如果您给出了以下权重A:30,B:40,C:50,D:60并且在您的最小生成树中,顶点A的度数为1,顶点B和C的度数为2,顶点D的度数为3你的常数减去得到一个下限= 1*30 + 2*40 + 2*50 + 3*60 = 390.
如何找到Held-Karp下界
现在我相信还有一个问题没有答案:我如何找到对图表的最佳修改,以便获得最严格的下限(因此Held-Karp下限)？
嗯,那是困难的部分.没有钻研太深:有办法越来越接近Held-Karp的下限.基本上,人们可以继续修改图形,使得所有顶点的程度越来越接近2.因此越来越接近真实的巡回演出.
最小1树是下限
正如所承诺的那样,我会给出一个非正式的证明,即最小1树是最佳TSP解决方案的下限.最小1树由两部分组成:最小生成树和附有2个边的顶点.TSP巡视必须通过附加到最小生成树的顶点.最简单的方法是通过附加的边缘.游览还必须访问最小生成树中的所有顶点.该最小生成树是除了附加顶点之外的图的最佳TSP的下限.结合这两个事实可以得出结论,最小1树是最佳TSP巡回的下限.
结论
当您以某种方式修改图形并找到此修改图形的最小-1树以计算下限时.通过这些方法的最佳可能下限是Held-Karp下限.
我希望这回答了你的问题.
链接
有关更正式的方法和其他信息,我建议使用以下链接:
| 归档时间： |
|
| 查看次数： |
6163 次 |
| 最近记录： |