给定一个在坐标平面上相互连接的 n 个节点的图，找到包含 m 个节点的最小距离子树的最佳方法是什么？
我发现这个问题的唯一解决方案是生成要连接的节点的所有组合，并尝试通过 Kruskal 或 Prim 算法连接这些节点，同时忽略其余的，然后比较所有创建的树并找到最小的树，但是这个当涉及到较大的树木时，效率并不高。
有没有更快、更有效的算法/方法？
问问题
1410 次
1 回答
5
您正在询问K 最小生成树 (k-MST)问题，该问题已知是 NP 完全的。所以你不会比你当前的算法做得更好。
但是，在评论中，您说您的图表是从坐标平面生成的，所以我只能假设您有一些关于图表中节点的几何信息。WWW 纲要条目提到您可以对欧几里得 k-MST 使用多项式时间近似方案。本文描述了一个：
阿罗拉，桑吉夫。(1996)，欧几里得 TSP 和其他几何问题的多项式时间近似方案，在 第 37 届会议记录中。IEEE 症状。计算机科学基础，第 2-11 页。
他们在那里直接提到了k-MST，所以我认为如果你真的想要更快的速度，你可以试试那个算法。
于 2009-04-02T22:45:49.910 回答