algorithm - 寻找最小的子树

Question

给定一个由 n 个节点组成的图，这些节点都在一个坐标平面上互连，找到包含 m 个节点的最小距 ionic 树的最佳方法是什么？

我发现这个问题的唯一解决方案是生成要连接的节点的所有组合，并尝试通过 Kruskal 或 Prim 算法连接这些节点，同时忽略其余部分，然后比较所有创建的树并找到最小的树，但是当涉及到较大的树时，这并不是很有效。

有没有更快、更高效的算法/方法？

Answer 1

你问的是 K-minimum spanning tree (k-MST)问题，已知是 NP 完全问题。所以你不会比你当前的算法做得更好。

但是，在评论中，你说你的图是从一个坐标平面生成的，所以我只能假设你有一些关于图中节点的几何信息。 WWW compendium entry提到您可以对欧几里得 k-MST 使用多项式时间近似方案。本文介绍了一个:

Arora, Sanjeev. (1996), Polynomial time approximation scheme for Euclidean TSP and other geometric problems, In Proceedings of the 37th Ann. IEEE Symp. on Foundations of Computer Science, pages 2-11.

他们在那里直接提到了 k-MST，所以我认为如果你真的想要更快的速度，你可以试试那个算法。