algorithm - 最接近对算法

Question

我试图了解最接近的配对算法。我了解将集合分成两半。但我无法理解如何递归计算最接近的对。我了解递归，但不了解如何通过递归计算最接近的对。如果你有 (1,2)(1,11)(7,8) 递归将如何处理这些？

score 8 · Accepted Answer

该算法的基本思想是这样的。

你有一组点 P，你想找到 P 中距离最短的两个点。

一个简单的蛮力方法将遍历 P 中的每一对，计算距离，然后取距离最短的一对。这是一个 O(n²) 算法。

但是，您正在谈论的算法可能会更好。这个想法是首先根据其中一个坐标对所有点进行排序，例如 x 坐标。现在你的集合 P 实际上是一个排序的点列表，按它们的 x 坐标排序。该算法现在将输入不是一组点，而是一个排序的点列表。我们将算法称为 ClosestPair(L)，其中 L 是作为参数给出的点列表。

ClosestPair(L) 现在递归实现如下：

将列表 L 在其中间拆分，得到 L _left和 L _right。
递归求解 ClosestPair(L _left ) 和 ClosestPair(L _right )。_{让δ left}和δ _right得到相应的最短距离。
现在我们知道原始集合中的最短距离（由 L 表示）要么是两个 δ 之一，要么是 L _left中的一点与 L _right中的一点之间的距离。
我们仍然需要检查左右细分的两点之间的距离是否更短。诀窍在于，因为我们知道距离必须小于 δ _left和 δ _right ，所以从两个细分点考虑距离分界线（x 坐标）不远于 min(δ _left , δ _right ) 的点就足够了您曾经拆分原始列表 L)。这种优化使该过程比蛮力方法更快，实际上是 O(n log n)。

score 7 · Accepted Answer

如果您指的是此算法，请执行以下操作：

排序点： (1,2) (1,11) (7,8)
构建两个子集：(1,2) (1,11) 和 (7,8)
分别在 (1,2) (1,11) 和 (7,8) 上运行算法 <= 这就是递归的来源。结果是 dLmin = 9 和 dRmin = 无穷大（右边没有第二个点）
dLRmin = sqrt(45)
结果 = min(dLmin, dRmin, dLRmin) = sqrt(45)

递归由与上述相同的步骤组成。例如，使用 (1,2) 和 (1,11) 调用会：

score 1 · Accepted Answer

我想我知道你在说什么算法。我可以自己在这里复述它，但是算法简介中给出的描述远远优于我所能产生的。谷歌书籍上也有该章节：享受。（其他人也可以在那里找到问题描述）

score 0 · Accepted Answer

也许线性时间随机最近对算法会有所帮助。在那里你可以在预期的时间 O(n) 中找到这对。

4 回答 4