algorithm - 使用近似算法查找所有点之间的路径

Question

有 1<=n<=1000 个城市。我必须找到连接所有城市（每个城市只能访问一次）的路径，该路径以城市 1 开始和结束。在这条路径中，两个城市之间的最大长度必须尽可能短。

例如：

输入：

coordinates of cities

输出：

5 1 3 //longest connection is 5 and it is between cities 1 and 3
1 3 6 4 5 2 1 //path

Answer 1

这是一个近似算法，平均而言应该比简单的贪心算法给出更好的结果：

1. 考虑该图是完整的 - 每对顶点之间都有一条边，总共有n(n-1)/2边。
2. 按其权重/距离的降序对边缘进行排序。
3. 从最高距离边缘迭代到最低距离边缘，如果在移除该边缘之后，它的两个端点仍然具有至少 ceil(n/2) 的度数，则将其移除（确保存在哈密顿循环的狄拉克定理）。您可以使用更强大的结果（如Ore 定理）来修剪更多边缘，但计算复杂度会增加。
4. 在剩下的图中，使用贪心算法找到哈密顿圈。贪心算法基本上是从 1 开始，一直选择到目前还没有形成循环一部分的节点距离最短的边。因此，在您的示例中，它将首先选择 1 -> 2，然后是 2->4，然后是 4->5，依此类推。最后选择的顶点将有一条回到 1 的路径。

您可以在输入图上直接使用步骤 4 中给出的贪心算法，但预处理步骤 1-3 通常应该会大大改善您在大多数图上的结果。

Answer 2

听起来与TSP相似，只是您需要最小化 2 个城市之间的最大长度而不是总长度（这可能使其根本不同）。

我的想法是这样的：

create edges between each pair of cities
while (true)
  next = nextLongestEdge
  if (graph.canRemove(next)) // this function may be somewhat complicated,
                             // note that it must at the very least check that every node has at least 2 edges
    graph.remove(next)
  else
    return any path starting and ending at 1 from the remaining edges