5

我目前正在研究旅行推销员问题，并且想知道是否有人能够简单地解释持有的 karp 下限。我一直在看很多论文，我很难理解它。如果有人可以简单地解释一下，那就太好了。

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

4

1 回答 1

10

我将尝试解释这一点，而不涉及太多细节。我会避免正式的证明，我会尽量避免使用技术术语。但是，当您通读所有内容后，您可能需要重新检查所有内容。最重要的是；自己尝试算法。

介绍

一棵树是一棵树，它由一个顶点和两条边连接到一棵生成树组成。您可以自己检查每个 TSP 游览都是一棵树。

还有一个图的最小一棵树这样的东西。当您遵循此算法时，这就是生成的树：

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

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

排除不同的顶点，你会发现得到的树是不同的。然而，所有生成的树都可以被认为是 TSP 中最佳游览的下限。因此，您以这种方式找到的最小一棵树中最大的一个是比其他以这种方式找到的更好的下限。

保持-卡普下限

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

这个想法是您可以以特殊方式更改原始图形。此修改后的图将生成与原始图不同的最小 1 树。

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

当然，对于最佳 TSP 巡回赛也是如此。因此，修正图中的最优 TSP 路径也是原始图中的最优路径。修改后的图的最小一棵树是修改后的图中最优路径的下界。同样，我只是假设您了解这会为您修改后的图的最佳 TSP 之旅生成一个下限。通过从修改后的图形的找到的下限中减去另一个已知常数，您就有了原始图形的新下限。

您的图表有无数这样的修改。这些不同的修改导致不同的下限。这些下限中最紧的是 Held-Karp 下限。

如何修改图表

现在我已经解释了 Held-Karp 下限是什么，我将向您展示如何修改您的图表以生成不同的 minimum-1-trees。

使用以下算法：

  • 给图中的每个顶点一个任意权重
  • 更新每条边的权重如下：新边权重 = 边权重 + 起始顶点权重 + 结束顶点权重

例如，您的原始图具有顶点 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。

您将需要另一个已知常数。您从 minimum-1-tree 中减去的常数以获得下限。这取决于您找到的 minimum-1-tree 的顶点度数。您需要将赋予每个顶点的权重乘以该最小 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 树是最优 TSP 解决方案的下限。minimum-1-Tree 由两部分组成：minimum-spanning-tree 和一个带有 2 条边的顶点。TSP 游览必须经过连接到最小生成树的顶点。最短的方法是通过附加的边缘。游览还必须访问最小生成树中的所有顶点。该最小生成树是不包括附加顶点的图的最佳 TSP 的下限。结合这两个事实可以得出结论，最小一棵树是最佳 TSP 游览的下限。

结论

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

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

链接

对于更正式的方法和其他信息，我推荐以下链接：

于 2014-07-02T22:38:26.183 回答