我遇到了以下问题,我不知道解决方案,也找不到“查找”术语来进一步调查。
假设我们有 N 个有序节点 (n_1,n_2....n_N),每个节点之间的固定距离为 1。所以距离(n_1,n_N)= N-1。现在我们可以连接任意两个节点,从而有效地将它们的距离减少到 1。假设我们可以有 k 个这样的连接。
问题是:我们如何选择连接哪些节点以最小化任意两个节点之间的总距离?
这个问题是某个经过充分研究的问题的已知变体吗?是否存在有效的解决方案(或者我们只想最小化任意两个节点之间的最大距离的变体)
谢谢
最佳答案
您可能对“On the sum of all distances in a graph or digraph”感兴趣。该论文将您的“总距离”称为图形的“传输”。您的“最大距离”通常称为图形的“直径”。对两者进行了讨论,证明了图传输的一些性质,证明了传输与直径相互独立。
天真地,您有 n-choose-k 个选项可以尝试。如果 n 和 k 很大,那就太糟糕了。如果其中一个很小,那还不错。
有比这更好的工作。 This Mathoverflow question询问减少顶点之间的平均距离,这与图的传输成正比。有两个答案,我都不能保证。它还指a paper直接解决了这个问题。
最小化图形的直径在 this paper 中处理。 .
您可以考虑将这个问题提交给 Math stackexchange。
关于algorithm - 使用 n 个节点之间的 k 个链接最小化总距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37045103/