我正在尝试理解最接近点对算法。我了解如何将集合分成两半，但我不太明白如何通过递归计算最接近的点对。我了解递归，但不知道如何通过递归计算最接近的点对。如果给你这些点：(1,2)(1,11)(7,8)，那么递归应该如何工作呢？
4个回答
9
算法的基本思想是这样的。
你有一组点P，你想找到P中距离最短的两个点。
一个简单的暴力方法是遍历P中的每一对点，计算它们之间的距离，然后选择距离最短的一对。这是一个O(n²)的算法。
但是，你所说的算法可以更好地解决这个问题。首先，按照其中一个坐标（例如x坐标）对所有点进行排序。现在，你的集合P实际上是一个按其x坐标排序的点列表。该算法现在将其输入设置为一组有序的点，而不是一组点。我们称这个算法为ClosestPair(L)，其中L是作为参数给出的点列表。
ClosestPair(L)的递归实现如下：
1.将列表L在中间分成Lleft和Lright两部分。
2.递归解决ClosestPair(Lleft)和ClosestPair(Lright)。让相应的最短距离分别为δleft和δright。
3.现在我们知道原始集合（由L表示）中的最短距离要么是两个δ中的一个，要么是Lleft中的一个点和Lright中的一个点之间的距离。
4.因此，我们仍然需要检查左右子分区中是否存在更短的距离。这个技巧是，因为我们知道距离必须小于δleft和δright，所以只需要考虑从分割线（你用来分割原始列表L的x坐标）不超过min(δleft,δright)的点即可。这种优化使得该过程比暴力方法更快，实际上是O(n log n)。
你有一组点P，你想找到P中距离最短的两个点。
一个简单的暴力方法是遍历P中的每一对点，计算它们之间的距离，然后选择距离最短的一对。这是一个O(n²)的算法。
但是，你所说的算法可以更好地解决这个问题。首先，按照其中一个坐标（例如x坐标）对所有点进行排序。现在，你的集合P实际上是一个按其x坐标排序的点列表。该算法现在将其输入设置为一组有序的点，而不是一组点。我们称这个算法为ClosestPair(L)，其中L是作为参数给出的点列表。
ClosestPair(L)的递归实现如下：
1.将列表L在中间分成Lleft和Lright两部分。
2.递归解决ClosestPair(Lleft)和ClosestPair(Lright)。让相应的最短距离分别为δleft和δright。
3.现在我们知道原始集合（由L表示）中的最短距离要么是两个δ中的一个，要么是Lleft中的一个点和Lright中的一个点之间的距离。
4.因此，我们仍然需要检查左右子分区中是否存在更短的距离。这个技巧是，因为我们知道距离必须小于δleft和δright，所以只需要考虑从分割线（你用来分割原始列表L的x坐标）不超过min(δleft,δright)的点即可。这种优化使得该过程比暴力方法更快，实际上是O(n log n)。
- Antti Huima
4
谢谢，这是我感到困惑的地方。假设你有12对数据，将其分成4个包含3对数据的子集。在左侧，你有1-6号数据对。已知1-3和4-6中距离最短的数据对。为找到中间值，需要比较1到4、5、6中距离最短的数据对，然后是2到4、5、6再到3到4、5、6。完成上述步骤后，得到的结果是否就是中间值？这样理解正确吗？ - Aaron
不，你没有12对，也不会把这些对分成子集。你有一些点数，需要将这些点数分成两个子集。 - Antti Huima
那么这些点被分成两个子集，这些子集又被分成两个更小的子集。然后找到子集中每个点之间的最短距离，对吗？所以现在我们有了L(左)和L(右)，但我们仍然需要找到L(左-右)。这就是我感到困惑的地方。我们是否要将L(左)中的所有点与L(右)中的所有点进行比较，以获取L(左-右)？ - Aaron
不，你将点分成两个子集。然后在这些子集上递归运行最短对算法。一旦递归调用返回，您就会检查是否存在比递归调用返回的任何两个更短的距离可用。因为您已经有了距离的上限（递归调用返回的最小结果），所以您不需要考虑左右区域中的所有点，而只需要考虑足够接近分割线的那些点。 - Antti Huima
7
如果你指的是这个算法，你需要按照以下步骤进行：
- 对点进行排序：(1,2) (1,11) (7,8)
- 构建两个子集：(1,2) (1,11) 和 (7,8)
- 分别在 (1,2) (1,11) 和 (7,8) 上运行算法 <= 这里涉及到递归。结果为 dLmin = 9 和 dRmin = infinity（右侧没有第二个点）
- dLRmin = sqrt(45)
- result = min(dLmin, dRmin, dLRmin) = sqrt(45)
递归包括与上述相同的步骤。例如，使用 (1,2) 和 (1,11) 进行调用：
- 排序点：(1,2) (1,11)
- 构建两个子集：(1,2) 和 (1,11)
- 分别在 (1,2) 和 (1,11) 上运行算法 <= 再次递归调用。结果是 dLmin = 无穷大，dRmin = 无穷大
- dLRmin = 9
- 结果 = min(dLmin, dRmin, dLRmin) = 9
- Howard
5
谢谢，如果有6对数据，(1,2)(1,11)(7,8)(9,9)(13,3)(13,4)，那会有什么变化？ - Aaron
1@Aaron 实际上我并不太理解你的问题。算法在输入大小方面并没有任何变化。我给了你一个关于如何处理你的示例输入的描述。你可以自己继续推导更多的例子。 - Howard
抱歉，我正在尝试解决一个更大的问题，并且只理解了其中一半。 - Aaron
我理解了分割部分，但是在比较子集时遇到了困难。您是要比较每个子集中的最短距离吗？例如，在子集一中，最短距离为5，在子集二中，最短距离为3。我们只需要比较5和3，而不需要比较子集中的实际点。 - Aaron
如果在递归函数调用之前进行排序，则无需在每个递归调用中执行排序。但是，您需要一种以线性时间O（n）使用哈希/集合的方法来将元素从所有点的排序数组中分离出来。 - FloatingRock
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接