traveling-salesman - 计算旅行推销员(TSP)的持有卡普下限

Question

我目前正在研究旅行推销员的问题，想知道是否有人能够简单地解释持有的卡尔普下限。我一直在看很多论文，我正在努力理解它。如果有人可以简单地解释它，那将是很好的。

我也知道，有一种方法可以计算不包括起始顶点的顶点的最小生成树，然后从起始顶点中添加两个最小边。

Answer 1

我将在不做过多详细说明的情况下尝试进行解释。我将避免使用正式的证明，并尽量避免使用技术术语。但是，一旦您通读了所有内容，您可能想要再次遍历所有内容。最重要的是；自己尝试算法。

介绍

一棵树是由包含2条边的顶点组成生成树的树。您可以自己检查每个TSP游览都是一棵树。

还有图的最小1树。当您遵循此算法时，即为结果树：


从图形中排除顶点
计算结果图的最小生成树
将具有2个最小边的排除顶点附加到最小生成树上


*现在，我假设您知道最小1棵树是最佳TSP游览的下限。最后有一个非正式的证明。

当您排除不同的顶点时，您会发现结果树是不同的。但是，所有得到的树都可以视为TSP中最佳巡回的下限。因此，您发现以这种方式找到的最小一棵树中的最大树的下界要好于其他以这种方式发现的树。

持有卡普下界

Held-Karp下限是更严格的下限。

这个想法是您可以用一种特殊的方式来改变原始图形。修改后的图将生成与原始图不同的最小一棵树。

此外（这很重要，因此我将在本段中用不同的词来重复这一点），这样的修改使得所有有效TSP游程的长度都被相同（已知）常数修改。换句话说，此新图中有效TSP解决方案的长度=原始图中有效解决方案的长度加上一个已知常数。例如：假设原始图形中按此顺序访问TSP巡回顶点A，B，C和D的权重= 10，然后在修改后的图形中按相同顺序访问TSP巡回顶点的权重= 10 +一个已知的常数。

当然，对于最佳TSP巡回赛也是如此。因此，修改后的图中的最佳TSP巡视也是原始图中的最佳巡视。修改图的最小1-Tree是修改图中最佳巡回的下限。再次，我只是假设您了解这为修改后的图的最佳TSP巡视产生了一个下限。通过从修改后的图的找到的下限中减去另一个已知常数，可以为原始图提供一个新的下限。

无限多地对图形进行此类修改。这些不同的修改导致不同的下限。这些下限中最紧密的是Held-Karp下限。

如何修改图形

现在，我已经解释了Held-Karp下界是什么，我将向您展示如何修改图形以生成不同的minimum-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巡回的下限。

结论

当您以某种方式修改图形并找到此修改图形的minimum-1-Tree来计算下限时。通过这些方式可能的最佳下限是Held-Karp下限。

我希望这回答了你的问题。

链接

有关更正式的方法和更多信息，我建议以下链接：


ieor.berkeley.edu/~kaminsky/ieor251/notes/3-16-05.pdf
http://www.sciencedirect.com/science/article/pii/S0377221796002147