最接近配对算法

Question

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

Answer 1

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

您有一组点 P，并且您想要找到 P 中距离最短的两个点。

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

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

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

1. 在中间分割列表 L，获得 L_left 和 L_right。
2. 递归求解 ClosestPair(L_left) 和 ClosestPair(L_right)。
   令δ_left和δ_right得到对应的最短距离。
3. 现在我们知道原始集合中的最短距离（用 L 表示）要么是两个 δ 之一，要么是 L_left 中的点与 L _{中的点之间的距离>对。}
4. 我们仍然需要检查左右细分的两点之间的距离是否较短。诀窍在于，因为我们知道距离必须小于 δ_left 和 δ_right，所以从两个细分点考虑不远于 min(δ _left, δ_right) 距分割线（用于分割原始列表 L 的 x 坐标）。这种优化使得该过程比暴力方法更快，实际上是 O(n log n)。

Answer 2

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

1. 对点进行排序：(1,2) ( 1,11) (7,8)
2. 构建两个子集：(1,2) (1,11) 和 (7,8)
3. 在 (1,2) (1,11) 和 (1,2) 上运行算法(7,8) 分别 <= 这就是递归出现的地方。结果是 dLmin = 9 且 dRmin = 无穷大（右侧没有第二个点）
4. dLRmin = sqrt(45)
5. result = min(dLmin, dRmin, dLRmin) = sqrt(45)

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

1. 排序点：(1,2) (1,11)
2. 构建两个子集：(1,2) 和 (1,11)
3. 在 ( 1,2) 和 (1,11) 分别<=再次递归调用。结果是 dLmin = 无穷大 dRmin = 无穷大
4. dLRmin = 9
5. 结果 = min(dLmin, dRmin, dLRmin) = 9

Answer 3

我想我知道你在说什么算法。我可以自己在这里重述一下，但是算法简介中给出的描述远远优于我可以生产。该章也可以在 Google 图书上找到：享受。 （其他人也可以在那里找到问题描述）

Answer 4

也许线性时间随机最近对< /a> 算法会有所帮助。在那里你可以在预期时间 O(n) 内找到该对。