在图中找到最大距离/传播的N个节点

Question

5

给定一个具有N个节点（数千个）的图，我需要找到K个节点，使得每对K之间的平均路径长度（K1，K2）最大化。因此，基本上，我希望尽可能将它们彼此分开。

我应该使用哪种算法来解决这个问题/如何编程而不必尝试几个单独的K组合？

另外作为扩展：如果现在我有N个节点，并且我需要在图中放置两组节点K和L，使得每对（L，K）之间的平均路径长度最大化，我该怎么做？

我的当前尝试只是进行一些随机放置，然后计算K和L的每对之间的平均路径长度，但是这个计算正在开始花费很多时间，因此我宁愿不要花费太多时间仅评估随机选择的组合。我宁愿花时间一次获得真正最广泛的组合。

是否有任何算法可以解决这个问题？

- user134589

这是一个关于编程的问题。你是在问是否只需要使用不同的标签，还是这个网站上有我不熟悉的其他部分？ - user134589

如果您有一个算法，但不确定如何实现，或者想了解哪种算法可以解决这个问题，可以访问http://math.stackexchange.com/来提出数学问题。 - Asthor

4

这是一个有关算法的问题，但它并不是数学SE的重点。计算机科学SE会更适合，但在这里也可以。 "algorithm" 标签下有超过50,000个问题。请问您需要翻译其他内容吗？ - j_random_hacker

2

@j_random_hacker 我同意，我不喜欢最近的趋势，即任何比“我按哪个按钮才能得到颗小球？”更深入的问题都被投票为离题，并仅适合数学专家。 - biziclop

2

@biziclop 这不是最近的事情了，但当计算机科学交流开始游说使算法问题成为离题时，情况变得更加糟糕。 - David Eisenstat

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

坏消息是，这个问题是NP难问题，通过从独立集合归约得出。（假设单位权重。添加一个连接到所有其他顶点的新顶点；然后我们正在寻找平均距离为2的K个集合。）

如果你决定要得到精确解（我不确定你是否应该这样做），那么我建议尝试分支定界算法，使用节点是否为K中的一个作为分支决策和粗略的界限（给定K的子集，找到最大化它们之间距离和到子集距离的适当组合的两个节点，然后将边界设置为包含已知节点间距离的适当加权平均值）。

如果上述精确算法在Evgeny担心的千节点图上无法处理，则使用farthest-point clustering（链接转到维基百科上的设施位置页面，描述了FPC）将图形裁剪到可管理的大小，产生希望很小的近似误差。