graph - 在成本满足三角不等式的无向图中找到不超过 O(m+n log n) 中最小成本两倍的哈密顿循环

Question

所以我被赋予了这项任务，我不知道如何使用有关成本的信息。这是要求，我没有其他信息。

Answer 1

这应该可以通过解决 TSP（旅行商问题）/汉密尔顿电路的双树近似算法来解决。它需要满足输入图的两个条件：

• 三角不等式（你有这个）
• 完整图（你有这个吗？这意味着图中每两个顶点之间必须有一条边。）

该算法的工作原理如下：

• 找到输入图的最小生成树（有一些算法；如果你的图表示是邻接表，复杂度是 O(e+v*log(v))）
• 将生成树中的每条边加倍 - 您将拥有多重图 (O(e))
• 在此图中创建欧拉路径 - 如果您第二次遇到一个顶点，请跳过它并采用直接边到下一个顶点（此边存在于图中，因为您有完整的图） - 这也应该类似于 O( e + 一些对数）
• 你完成了 - 你找到了一个汉密尔顿电路（并解决了 TSP）

该算法约为 2 倍（电路的成本最多是最佳解决方案的两倍 - 如果您愿意，我可以提供一个证明）。最糟糕的复杂性是 O(e + v log(v)) - e 是边数，v 顶点数......这应该映射到你的 O(m + n log(n))。

目前我找不到与算法解释的任何良好链接，我将尝试稍后提供。