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

Question

假设我们在2D平面上给出了一个图，其中节点和每对节点之间的边具有等于欧几里得距离的权重。最初的问题是找到这个图的MST，并且很清楚如何使用Prim's或Kruskal算法来解决这个问题。

现在我们假设我们有k额外的节点，我们可以将它放在我们的2D平面上的任何整数点上。问题是如果没有必要使用所有这些额外节点，则为这些节点查找位置，以便新图具有尽可能最小的MST。

显然不可能找到确切的解决方案（在多时间），但目标是找到最佳近似解（可在1秒内找到）。也许你可以想出一些最有效的抛出可能解决方案的提示，或者提供一些文章，其中涉及类似的问题。

Answer 1

这是你正在研究的非常有趣的问题。你有很多选择来解决这个问题。在这种情况下最有名的启发式是 - Genetic Algorithms,Particle Swarm Optimization,Differential Evolution和这类许多其他类型。

这种启发式算法的好处在于，你可以限制它们的执行时间（比如说1秒）。如果这是我的任务，我会尝试第一个遗传算法。

Answer 2

您可以尝试使用贪婪算法，尝试MST中最长的边缘，这可能会给您带来最大的节省。

选择最长的边，现在从每边从每个角度关闭的顶点获取从所选角度关闭的边的潜在边。

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

修复MST ...

重复，直到1秒消失。

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