给定一个在坐标平面上互连的 n 个节点的图，找到包含 m 个节点的最小距 ionic 树的最佳方法是什么？
我发现这个问题的唯一解决方案是生成要连接的节点的所有组合，并尝试通过 Kruskal 或 Prim 的算法连接这些节点，同时忽略其余节点，然后比较创建的所有树并找到最小的一个，但是对于较大的树来说，这并不完全有效。
有没有更快、更高效的算法/方法？
最佳答案
您询问的是 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，所以我认为如果你真的想要更快的速度，你可以尝试该算法。
关于algorithm - 寻找最小子树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/711684/