度量空间中高效的最小生成树

Question

我有一个包含大量点的集合 (点数n > 10000)，并且它们存在于某个度量空间中（例如通过Jaccard Distance来衡量）。我想要用度量作为边权将它们连接到最小生成树上。

• 是否存在一种算法，其运行时间少于O(n²)？
• 如果不存在，是否存在一种平均运行时间少于O(n²)的算法（可能使用随机化）？
• 如果不存在，是否存在一种运行时间少于O(n²)的算法，并能够给出最小生成树的很好近似值？
• 如果不存在，是否有某种原因导致这样的算法无法存在？

提前感谢您的回答！

编辑： 传统的最小生成树算法在这里不适用。它们的运行时间中有一个E因子，但在我的情况下，E = n²，因为我实际上考虑的是完全图。我也没有足够的内存来存储所有>49995000个可能的边。

- Yakov Galka

---

你是否至少阅读过这个网址 http://en.wikipedia.org/wiki/Minimum_spanning_tree#Algorithms？ - Nikolai Fetissov

我当然做了。还写了很多论文。 - Yakov Galka

你不需要“存储”你的10^8条边。你需要一个位向量来标记已访问的边，但这个位向量只会使用大约12 MB的内存，就内存而言似乎是可以承受的。 - Sven Marnach

@Sven: a) 10000个顶点是下限。 b) Kruskal算法需要将它们存储并排序。 - Yakov Galka

Answer 1

根据这篇论文：在亚线性时间内估算度量空间最小生成树的权重，显然没有确定性 o(n^2)（注意：小o，可能是你所指的少于O(n^2)，我猜测）算法。该论文还提供了求度量空间最小权重生成树的亚线性随机算法。

同时，请参考这篇论文：一种最优最小生成树算法，该论文提供了一种最优算法，并声称该算法的复杂性尚未确定！

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

希望这能帮到您。

- Aryabhatta

---

谢谢，但这些论文并不是免费提供的。此外，你在这里写的听起来有点矛盾。这里的“线性时间”是按边数还是顶点数计算的？ - Yakov Galka

第一篇论文可以从布朗大学官网免费获取。不幸的是，正如引言第四段所述，它在边数方面是线性的。如果不知道权重来自度量，则无法更好地处理，因为必须读取所有边。 - Yakov Galka

不需要图书馆。我不知道其他领域，但基本上所有计算机科学论文都可以免费找到。前往 scholar.google.com 并输入论文标题。在正确的结果中会有一个小链接“查看所有xx版本”。点击它。这将带您到包含该标题的结果，几乎总是包含pdf或ps链接。您可以通过这种方式找到这三篇论文。 - Chris Hopman

@Moron：不，我的逻辑是正确的。它是随机化的，以达到预期的线性运行时间，但它确实找到了最优解，而不是近似解（考虑使用随机枢轴的快速排序）。要找到最优解，您始终需要考虑所有边缘。顺便说一句，这也是最后一篇论文无法帮助的原因，因为它也适用于一般图形。然而，第一篇论文说，即使对于欧几里得空间，也没有已知的算法...而这篇论文只有两年历史... :( - Yakov Galka

@ybung：我在谈论一般的随机算法（不一定总是给出最优解），而不是参考那篇已经确定边缘线性的论文。这里有一个随机算法，它以1/2的概率给出数组的最小值：选择n/2个随机元素并选择其中的最小值。看起来不太好。如果您总是期望最优解，则显然必须查看所有内容，因为您始终需要找到具有最小权重的边缘。无论如何... - Aryabhatta

Answer 2

当我在3-4年前看到一个非常相似的问题时，我在查阅的文献中找不到理想的解决方案。我认为的诀窍是找到“可能好”的边的“小”子集，然后在上面运行简单的Kruskal算法。一般来说，许多MST边可以在将每个顶点连接到其k个最近邻居的边集中找到，其中k很小。这些边可能无法跨越图形，但是当它们不跨越图形时，可以将每个组件折叠成单个顶点（随机选择），并重复该过程。（为了更好的准确性，不要选择单个代表作为新的“超级顶点”，而是选择一些小的代表数r，在下一轮中检查2个超级顶点之间的所有r^2距离，并选择最小值。） 最近邻算法在有限维欧几里得空间中将对象表示为向量的情况下已经被广泛研究，因此如果您能找到一种将对象映射到该空间中的方法（例如使用多维缩放），那么您可能会有所收获。特别是，映射到2D允许您计算沃罗诺伊图，而MST边将始终位于相邻的面之间。但从我所读的资料来看，这种方法并不总是产生高质量的结果。

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

- j_random_hacker

---

这概括了我的想法 - 除非你能够使用距离度量来排除大量的边，否则你无法避免O(n^2)的运行时间。 - Nathan S.

@Nathan：如果你进行映射，就可以避免在k最近邻查询中进行n^2次距离计算，因为你会建立某种索引（在少于O(n^2)的时间内）。 - j_random_hacker

@j_random_hacker：对，我指的是最小生成树限制，而不是最近邻查询。只有因为/如果邻居查询可以快速完成，你才能做得比n^2更好。 - Nathan S.

@Nathan @j_random：对于一般的最小生成树问题，无法做到比O(n^2)更好的复杂度，但对于度量空间中的最小生成树问题可能是可以的。关键在于三角不等式允许您推断某些边权重的界限，因此您根本不需要处理它们。问题是如何实现这一点。 - Yakov Galka

就像你提到的 Voronoi 一样。它利用了它在欧几里得空间中工作的知识，从而提高了性能。在任何有限维度（不仅仅是2D），你都可以在线性对数时间内构建它，并将其用于最小生成树。 - Yakov Galka