10

我在某些度量空间（例如配备Jaccard Distance ）中有大量点（数量 n > 10000 ）。我想将它们与最小生成树连接起来，使用度量作为边缘的权重。

  • 是否存在运行时间少于 O(n 2 ) 的算法？
  • 如果没有，是否有一种算法运行时间少于 O(n 2 ) 平均时间（可能使用随机化）？
  • 如果没有，是否有一种算法可以在少于 O(n 2 ) 的时间内运行并给出最小生成树的良好近似值？
  • 如果不是，是否有理由不存在这种算法？

先感谢您！

编辑下面的海报： 寻找最小生成树的经典算法在这里不起作用。他们的运行时间有一个 E 因素，但在我的情况下 E = n 2因为我实际上考虑了完整的图表。我也没有足够的内存来存储所有 >49995000 个可能的边。

4

2 回答 2

7

显然，根据这个：在次线性时间内估计度量最小生成树的权重没有确定性o（n ^ 2）（注意：smallOh，我想这可能是您所说的小于O（n ^ 2）的意思） 算法。该论文还给出了度量最小权重生成树的亚线性随机算法。

另请参阅这篇论文：给出了最优算法的最优最小生成树算法。该论文还声称，最优算法的复杂性尚不清楚！

第一篇论文中的参考文献应该会有所帮助，并且该论文可能与您的问题最相关。

希望有帮助。

于 2011-01-17T18:15:20.367 回答
4

3-4 年前，当我在研究一个非常相似的问题时，我在查阅的文献中找不到理想的解决方案。

我认为的诀窍是找到“可能好的”边缘的“小”子集，然后您可以在其上运行普通的旧 Kruskal。一般来说，对于一些小的k ，很可能在将每个顶点连接到它的k个最近邻居的边集合中可以找到许多 MST 边。这些边可能不会跨越图形，但如果它们不跨越，则每个组件都可以折叠到单个顶点（随机选择）并重复该过程。（为了获得更高的准确性，不要选择单个代表作为新的“超顶点”，而是选择少量r代表，并在下一轮检查 2 个超顶点之间的所有r ^2 距离，选择最小值。）

k最近邻算法在对象可以表示为有限维欧几里得空间中的向量的情况下得到了很好的研究，所以如果你能找到一种方法将你的对象映射到那个（例如多维缩放）然后你可能在那里有运气。特别是，映射到 2D 允许您计算 Voronoi 图，并且 MST 边将始终位于相邻面之间。但从我所读到的很少内容来看，这种方法并不总能产生高质量的结果。

否则，您可能会发现聚类方法很有用：在任意度量空间中对大型数据集进行聚类是我发现的少数几篇论文之一，这些论文明确处理了在欧几里得空间中不一定是有限维向量的对象，并且考虑了计算昂贵的距离函数。

于 2011-01-17T19:12:12.000 回答