algorithm - 将边缘添加到树形图中，以便使任意两个顶点之间的新最大距离最小

Question

我一直在努力解决以下问题（请注意，这不是家庭作业，我只是在用过去几年的作业练习考试）：http://i.imgur.com/VqgKvkh.png。
我希望有人来验证或改进我的方法来完成这项任务，因为我不确定是否有一个更快的方法（或者我所做的是否正确，真的）。
我的解决方案：
1）首先，我计算每一个望远镜之间的距离（用毕达哥拉斯定理），给我O（V^ 2）复杂度的过程，但它不是那么糟糕，考虑到V的最大值是300。我用这些加权边构造了一个完整的图。
2）接下来，使用Kraskar算法，在O（E log（V））复杂度下运行该图的最小生成树。
（这是我不确定的地方）
3）由于这是一个树图，我可以找到它的中心，忽略边的权重。
4）一旦我找到了中心（考虑到一个单顶点中心，还没有考虑如何处理一个两顶点中心），我就把这个图分成子图（一个子图与每个从中心出来的边相关）
5）对于每个顶点，我计算它与中心的距离（考虑权重）-O（e）复杂度。
6）对于每个子图，从中心到O（V log（V））复杂度取两个最大距离的顶点。
7）取用这种方法得到的所有顶点对，并从中再次取最大值2如果它们不在同一个子图中，我们就完成了，并用新边连接这两个子图。
8）如果它们在同一个子图中，则转到3），然后在子图上递归运行此操作。
我的问题是-这是我能达到的最快的解决方案吗？更重要的是，这是否正确？谢谢您。

Answer 1

不幸的是，你的算法没有产生正确的答案。
请考虑您提供的练习表屏幕截图上的第一个示例这里有7个顶点，让我们按照给定的顺序从1到7给它们编号。我同意望远镜网络最初是一个最小生成树，因为“所有电缆的总长度是最小可能的”在描述中说明。
下面的边是我计算出的这个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）。
我们怎样才能做得更好我喜欢先考虑天真的解决方案，因为你知道你需要看什么。从那里你开始移除不必要的操作。你正确地发现最长的路径需要变短（否则直径不会改变）。换句话说，添加的边必须连接位于最长路径上的两个顶点。但是你不知道是哪两个你可以很容易地构造例子，其中每个顶点都是最长路径的一部分，但是对于一个分布良好的望远镜网络，最长路径上的顶点要少得多现在您只需尝试沿最长路径插入边，然后在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）