找到最小的子树

Question

给定n个节点在坐标平面上互连的图形,找到包含m个节点的最小距离子树的最佳方法是什么？

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

有更快,更有效的算法/方法吗？

Answer 1

您询问的是K-minimum生成树(k-MST)问题,该问题已知为NP-complete.因此,您不会比当前的算法做得更好.

但是,在注释中,您说您的图是从坐标平面生成的,因此我只能假设您有关于图中节点的一些几何信息.该WWW汇编项提到,您可以使用欧几里德K-MST多项式时间近似方案.本文描述了一个:

阿罗拉,桑杰夫.(1996),欧几里德TSP的多项式时间近似方案和其他几何问题,在 第37届Ann的会议录中.IEEE Symp.关于计算机科学基础,第2-11页.

他们直接在那里提到了k-MST,所以如果你真的想要更快的话,我想你可以尝试那种算法.