最近对算法

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和_左右.
2. 递归求解ClosestPair(_左起)和ClosestPair(_右右).设δ _左和δ _右对应的最短距离.
3. 现在我们知道原始集合中的最短距离(由L表示)是两个δ中的一个,或者它是L _左边的点和_右边的 L点之间的距离.
4. 我们还需要检查左右细分两点之间的距离是否较短.诀窍在于,因为我们知道距离必须小于δ _左和δ _右,所以从分割线(x坐标)的两个细分点(距离δ _左,δ _右)不足以考虑你曾经拆分原始清单L).这种优化使得程序比蛮力方法更快,实际上是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)和(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)和on(1,11)上运行算法<=再次递归调用.结果是dLmin =无穷大,dRmin =无穷大
4. dLRmin = 9
5. result = min(dLmin,dRmin,dLRmin)= 9