向树图中添加一条边，使任意两个顶点之间的新最大距离尽可能小
Adding an edge to a tree graph so as the new maximum distance between any two vertices is minimum possible
我一直在尝试解决以下问题（请注意，这不是家庭作业，我只是使用过去几年 class 的作业练习考试）：http://i.imgur.com/VqgKvkh.png。
我希望有人验证或改进我完成这项任务的方法，因为我不确定是否有更快的方法（或者我所做的是否完全正确，真的）。
我的解决方案：
1) 首先，我计算每个 telescope 之间的距离（使用毕达哥拉斯定理），给我一个 O(V^2) 复杂度的过程，但考虑到最大值V是300。我用这些加权边构造了一个完整的图。
2) 接下来，我使用 Kruskal 算法找到该图的最小生成树，运行 复杂度为 O(E log(V))。
（这是我不确定的地方）
3) 由于这是一个树图，我可以找到它的中心，忽略边缘权重。
4) 一旦我找到了中心（考虑一个 single-vertex 中心，还没有想太多如何处理 two-vertex 中心），我把这个图分成子图（一个子图与从中心出来的每条边相关）
5) 对于每个顶点，我计算它到中心的距离（考虑权重）- O(E) 复杂度
6) 对于每个子图，取两个与中心距离最大的顶点 - 大约 O(V log(V)) 复杂度
7) 取出所有以这种方式得到的顶点对，并再次从中取出最大的两个。如果它们不在同一个子图中，我们就完成了，并将这两个与新边连接起来。
8)如果在同一个子图中，则转到3)，运行在子图上递归。
我的问题是 - 这是我能实现的最快解决方案吗？更重要的是，它是否正确？谢谢。
很遗憾，您的算法没有给出正确答案。
请考虑您提供的练习 sheet 屏幕截图中的第一个示例。你有 7 个顶点，让我们按照给出的顺序从 1 到 7 对它们进行编号。我同意 telescope 网络最初是一个最小生成树，因为 "the total length of all cables is minimum possible" 在描述中有说明。
以下边是我计算出的这个 MST 的边（在顶点上使用建议的编号）：
{1,3}, {2,3}, {3,4}, {4,5}, {4,6}, {6,7}
使用您找到中心的方法，中心是顶点 4，因为每个其他顶点距它最多 2 跳。现在让我们按照您的建议将 MST 分成子图。有3个子图（我用它们的顶点集来识别）：
- {1,2,3}
- {5}
- {6,7}
因此，离中心最远的顶点是
{2,5,7}
很明显，从顶点 2 到顶点 7 的距离最大。我使用勾股定理计算出了 9.99 = sqrt(10) + 2 + sqrt(8) + 2 的距离。正如您所建议的，您的解决方案是连接顶点 2 和顶点 7 以最小化直径。
但有一个更好的解决方案：连接顶点 3 和顶点 7（如练习中给出的解决方案）。这样做的原因是从顶点 1 到顶点 7 的距离从 9.06 = sqrt(5) + 2 + sqrt(8) + 2 减小到 8.82 = sqrt(10) + sqrt(32)。使用您的解决方案，从顶点 1 到顶点 7 的最小距离仍为 9.06，这并没有达到最佳。
其次，不需要像您在步骤 8 中建议的那样进行递归。它是一棵树，那么三个子图中的一个如何在不通过中心的路径上连接到另一个？如果是，则该图将包含一个循环，因为子图已经通过中心连接。
第三，在稠密图上，最好使用 Prim-Dijkstra 来实现 O(E + Vlog(v)) 的 MST。它很容易实现，例如您可以在维基百科上查找它。不过我想你已经知道了。
最后，如何产生正确的结果？
如您所见，由于您的想法没有实现，因此如何使用启发式方法找到边缘并不明显。
天真的解决方案是什么？
您几乎可以从每个顶点对中进行选择，即 O(n^2) 许多候选边。要（天真地）计算它的直径，你需要 O(n^2)。因此，您可以尝试每条边并计算插入这条附加边的树的直径。最后，您输出最小直径。这将是 O(n^2 * n^2) = O(n^4).
我们怎样才能做得更好？我喜欢首先考虑天真的解决方案，因为你知道你需要看什么东西。从那里开始删除不必要的操作。您正确发现的是最长的路径需要变短（否则直径不会改变）。换句话说，您添加的边必须连接最长路径上的两个顶点。但是你不知道是哪两个。您可以轻松构建示例，其中每个顶点都是最长路径的一部分，但对于 telescopes 的良好分布式网络，最长路径上的顶点要少得多。现在您只尝试沿最长路径插入边并在 O(n^2) 中再次计算新直径。如果你在最长的路径上有 k 个顶点，你会得到 O(n^2 k^2).
总结：
- 使用 Prim 算法计算生成树 -> O(n^2) 在你的完整图上
- 计算树的最长路径，即直径 -> O(n^2) 得到最长路径上的所有 k 个顶点
- 尝试在这条最长路径上的所有顶点对之间一次添加一条 (O(k^2) 多条) 边，并存储所有直径的最小值，即您必须再次重新计算直径并再次 (O(n^2))。总共：O(n^2 k^2)
如果我们能缩短计算直径的时间就好了。对于在线性时间内工作的树，请参阅 Linear algorithm of finding tree diameter。您的图形最初是一棵树，但是您一次最多添加一条边，即它仍然几乎是一棵树。因此，您需要做的就是找到原始树中距离最远的两个节点 u1、v1，然后在我们的算法中插入边 e={u,v} 时，您删除与顶点 u 处的 e 不同的边，这样循环就消失了，你又得到了一棵树。现在您再次找到距离最远的顶点 u2、v2。现在计算四个顶点 u1、u2、v1、v2 之间的最大距离，这是线性时间的直径。
这将使您 运行 时间缩短到 O(n*k^2 + n^2)
我一直在尝试解决以下问题（请注意，这不是家庭作业，我只是使用过去几年 class 的作业练习考试）：http://i.imgur.com/VqgKvkh.png。
我希望有人验证或改进我完成这项任务的方法，因为我不确定是否有更快的方法（或者我所做的是否完全正确，真的）。
我的解决方案：
1) 首先，我计算每个 telescope 之间的距离（使用毕达哥拉斯定理），给我一个 O(V^2) 复杂度的过程，但考虑到最大值V是300。我用这些加权边构造了一个完整的图。
2) 接下来，我使用 Kruskal 算法找到该图的最小生成树，运行 复杂度为 O(E log(V))。
（这是我不确定的地方）
3) 由于这是一个树图，我可以找到它的中心，忽略边缘权重。
4) 一旦我找到了中心（考虑一个 single-vertex 中心，还没有想太多如何处理 two-vertex 中心），我把这个图分成子图（一个子图与从中心出来的每条边相关）
5) 对于每个顶点，我计算它到中心的距离（考虑权重）- O(E) 复杂度
6) 对于每个子图，取两个与中心距离最大的顶点 - 大约 O(V log(V)) 复杂度
7) 取出所有以这种方式得到的顶点对，并再次从中取出最大的两个。如果它们不在同一个子图中，我们就完成了，并将这两个与新边连接起来。
8)如果在同一个子图中，则转到3)，运行在子图上递归。
我的问题是 - 这是我能实现的最快解决方案吗？更重要的是，它是否正确？谢谢。
很遗憾，您的算法没有给出正确答案。
请考虑您提供的练习 sheet 屏幕截图中的第一个示例。你有 7 个顶点，让我们按照给出的顺序从 1 到 7 对它们进行编号。我同意 telescope 网络最初是一个最小生成树，因为 "the total length of all cables is minimum possible" 在描述中有说明。
以下边是我计算出的这个 MST 的边（在顶点上使用建议的编号）：
{1,3}, {2,3}, {3,4}, {4,5}, {4,6}, {6,7}
使用您找到中心的方法，中心是顶点 4，因为每个其他顶点距它最多 2 跳。现在让我们按照您的建议将 MST 分成子图。有3个子图（我用它们的顶点集来识别）：
- {1,2,3}
- {5}
- {6,7}
因此，离中心最远的顶点是
{2,5,7}
很明显，从顶点 2 到顶点 7 的距离最大。我使用勾股定理计算出了 9.99 = sqrt(10) + 2 + sqrt(8) + 2 的距离。正如您所建议的，您的解决方案是连接顶点 2 和顶点 7 以最小化直径。
但有一个更好的解决方案：连接顶点 3 和顶点 7（如练习中给出的解决方案）。这样做的原因是从顶点 1 到顶点 7 的距离从 9.06 = sqrt(5) + 2 + sqrt(8) + 2 减小到 8.82 = sqrt(10) + sqrt(32)。使用您的解决方案，从顶点 1 到顶点 7 的最小距离仍为 9.06，这并没有达到最佳。
其次，不需要像您在步骤 8 中建议的那样进行递归。它是一棵树，那么三个子图中的一个如何在不通过中心的路径上连接到另一个？如果是，则该图将包含一个循环，因为子图已经通过中心连接。
第三，在稠密图上，最好使用 Prim-Dijkstra 来实现 O(E + Vlog(v)) 的 MST。它很容易实现，例如您可以在维基百科上查找它。不过我想你已经知道了。
最后，如何产生正确的结果？
如您所见，由于您的想法没有实现，因此如何使用启发式方法找到边缘并不明显。
天真的解决方案是什么？ 您几乎可以从每个顶点对中进行选择，即 O(n^2) 许多候选边。要（天真地）计算它的直径，你需要 O(n^2)。因此，您可以尝试每条边并计算插入这条附加边的树的直径。最后，您输出最小直径。这将是 O(n^2 * n^2) = O(n^4).
我们怎样才能做得更好？我喜欢首先考虑天真的解决方案，因为你知道你需要看什么东西。从那里开始删除不必要的操作。您正确发现的是最长的路径需要变短（否则直径不会改变）。换句话说，您添加的边必须连接最长路径上的两个顶点。但是你不知道是哪两个。您可以轻松构建示例，其中每个顶点都是最长路径的一部分，但对于 telescopes 的良好分布式网络，最长路径上的顶点要少得多。现在您只尝试沿最长路径插入边并在 O(n^2) 中再次计算新直径。如果你在最长的路径上有 k 个顶点，你会得到 O(n^2 k^2).
总结：
- 使用 Prim 算法计算生成树 -> O(n^2) 在你的完整图上
- 计算树的最长路径，即直径 -> O(n^2) 得到最长路径上的所有 k 个顶点
- 尝试在这条最长路径上的所有顶点对之间一次添加一条 (O(k^2) 多条) 边，并存储所有直径的最小值，即您必须再次重新计算直径并再次 (O(n^2))。总共：O(n^2 k^2)
如果我们能缩短计算直径的时间就好了。对于在线性时间内工作的树，请参阅 Linear algorithm of finding tree diameter。您的图形最初是一棵树，但是您一次最多添加一条边，即它仍然几乎是一棵树。因此，您需要做的就是找到原始树中距离最远的两个节点 u1、v1，然后在我们的算法中插入边 e={u,v} 时，您删除与顶点 u 处的 e 不同的边，这样循环就消失了，你又得到了一棵树。现在您再次找到距离最远的顶点 u2、v2。现在计算四个顶点 u1、u2、v1、v2 之间的最大距离，这是线性时间的直径。
这将使您 运行 时间缩短到 O(n*k^2 + n^2)