给定一个无向连通图G，找到一棵直径最小的生成树。
1个回答
6
singhsumit链接了Hassin and Tamir的相关论文，题目为“最小直径生成树问题”，但他的答案目前已被删除。该论文的主要思想是，在无向图中找到一棵最小直径生成树可以通过找到图的“绝对1中心”并返回以此为根的最短路径树来实现。
绝对1中心是距离最远顶点最小的点，可以在Kariv和Hakimi的算法（网络位置问题的算法方法I：p中心）或Hakimi、Schmeichel和Pierce的早期算法（关于网络中心问题的p中心）中找到，我将尝试仅从运行时间和数十年的经验中重建该算法。(愚蠢的付费壁垒)
使用Floyd-Warshall算法或Johnson算法计算所有节点之间的距离。对于每条边u-v，如下找到该边上最佳的1中心候选项。
让边界上u-v之间的点以µ为索引，范围从0（u本身）到len（u-v）（v本身）。从索引µ到顶点w的距离为
min(µ + d(u, w), len(u-v) - µ + d(v, w))。
作为µ的函数，此数量先增加后减少，并在µ = (len（u-v）+ d（v，w）- d（u，w）)/2时达到最大值。
按照这个argmax排序顶点。对于数组的每个左子数组和右子数组的分区，计算引起相同argmax分区的µ的区间[a，b]。将此区间与[0，len（u - v）]相交；如果交集为空，则继续。否则，在从索引为a的u-v上的点到左子数组中的最大距离L，并在从索引为b的u-v上的点到右子数组中的最大距离R之间找到最大距离。 （可以通过在开始时从左到右和从右到左扫描来摊销每个分区的计算这些最大值的成本到O（1）。）最佳选择是在[a，b]中最小化max（L-（µ-a），R +（b-µ））的µ。
绝对1中心是距离最远顶点最小的点，可以在Kariv和Hakimi的算法（网络位置问题的算法方法I：p中心）或Hakimi、Schmeichel和Pierce的早期算法（关于网络中心问题的p中心）中找到，我将尝试仅从运行时间和数十年的经验中重建该算法。(愚蠢的付费壁垒)
使用Floyd-Warshall算法或Johnson算法计算所有节点之间的距离。对于每条边u-v，如下找到该边上最佳的1中心候选项。
让边界上u-v之间的点以µ为索引，范围从0（u本身）到len（u-v）（v本身）。从索引µ到顶点w的距离为
min(µ + d(u, w), len(u-v) - µ + d(v, w))。
作为µ的函数，此数量先增加后减少，并在µ = (len（u-v）+ d（v，w）- d（u，w）)/2时达到最大值。
按照这个argmax排序顶点。对于数组的每个左子数组和右子数组的分区，计算引起相同argmax分区的µ的区间[a，b]。将此区间与[0，len（u - v）]相交；如果交集为空，则继续。否则，在从索引为a的u-v上的点到左子数组中的最大距离L，并在从索引为b的u-v上的点到右子数组中的最大距离R之间找到最大距离。 （可以通过在开始时从左到右和从右到左扫描来摊销每个分区的计算这些最大值的成本到O（1）。）最佳选择是在[a，b]中最小化max（L-（µ-a），R +（b-µ））的µ。
- David Eisenstat
4
1“计算引起相同argmax分区的µ的区间[a，b]”是什么意思？ - galath
2如果从边的中心到顶点的距离在µ = 0、0.2、0.5、0.7、0.9、1处具有argmaxes，则用于分割[0,0.2,0.5][0.7,0.9,1]的[a，b]区间是区间[0.5，0.7]。 - David Eisenstat
另一种思考最后一部分的方式是，从顶点w到点µ沿着u和v之间的距离在µ上绘制时看起来像一个“山脉”，每一侧都以45度的角度上升到argmax处的峰顶。如果我们在每个µ值处绘制所有这些山脉（对于所有顶点w的最大值），我们就会得到一个“山脉区域”。然后目标是寻找该山脉区域中在[0，len（u-v）]内发生的最低点，这必须发生在端点之一或“山谷”处。... - j_random_hacker
如果我们按照递增的argmax顺序将每座山添加到山脉中，那么每次添加山都会擦除最右侧现有山和山谷中的0个或多个，然后向右添加0个或1个新山谷和1座山。由于每座山和山谷只被添加一次并且最多被删除一次，并且测试新山是否隐藏另一座山以及在没有隐藏时找到它们的山谷都是O(1)时间，因此这需要线性时间。最后，可以扫描幸存的山谷并选择[0，len(u-v)]中最低的山谷。这需要针对每条边uv重复进行，并保留最低的整体值。 - j_random_hacker
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接