具有K个额外节点的最小生成树

Question

3

假设我们有一个在二维平面上的图形，其中有n个节点和每对节点之间的边，权重等于欧几里得距离。最初的问题是找到这个图形的最小生成树，使用Prim算法或Kruskal算法很清楚可以解决它。

现在假设我们有k个额外的节点，我们可以将它们放置在二维平面上的任何整数点上。问题是找到这些节点的位置，使得新图形具有可能使用不了所有额外节点的最小生成树。

显然无法找到确切的解决方案（在多项式时间内），但目标是找到最佳近似解（可以在1秒内找到）。也许您可以想出一些提示，以最有效的方式遍历可能的解决方案，或提供一些文章，涵盖类似的问题。

- Maxim Popov

这听起来让人想起了史泰纳树问题，该问题已知是NP难的。 - templatetypedef

2个回答

0

你可以尝试使用贪心算法，尝试在最小生成树中选择最长的边，这些可能会带来最大的节省。

选择最长的边，现在从每个顶点获取与所选顶点成角度闭合的潜在边缘，从每一侧获取。

从这些中选择最佳的斯坦纳点。

修复最小生成树...

重复直到1秒钟过去。

挑战是如果其中一个顶点本身就是斯坦纳点该怎么办。

- Surt

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

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

- Todor Balabanov · Accepted Answer

你正在处理的问题非常有趣。你有许多攻击这个问题的选择。在这种情况下，最好的已知启发式算法是 - 遗传算法, 粒子群优化, 差分进化以及其他类似的算法。

对于这种启发式算法来说，很好的一点是你可以将它们的执行时间限制在一定的时间内（比如说1秒）。如果这是我的任务，我会首先尝试使用遗传算法。