最近对算法 [英] closest pair algorithm

问题描述

我想了解最近对算法。我都懂分集的一半。但我无法理解如何递归地计算最接近的一对。我理解递归，但不知道如何计算最近对通过递归。如果您有（1,2），（1,11）（7,8）怎么会递归这些工作？

I am trying to understand the closest pair algorithm. I understand about dividing the set in half. But I am having trouble understanding how to recursively compute the closest pair. I understand recursion, but do not understand how to compute the closest pair by recursion. If you have (1,2)(1,11)(7,8) how would recursion work on these?

推荐答案

如果你的意思是该算法你做如下：

If you mean this algorithm you do the following:

1. 排序点：（1,2）（1,11）（7,8）
2. 在构建两个子集：（1,2），（1,11）和（7,8）
3. 在分别与LT运行在（1,2），（1,11）和（7,8）的算法; =这就是递归来。结果是dLmin = 9和dRmin =无穷大（有在右边没有第二个点）
4. dLRmin =开方（45）
5. 在结果=分钟（dLmin，dRmin，dLRmin）=开方（45）

递归由相同的步骤如上述。例如。与呼叫（1,2）和（1,11）的作用：

The recursion consists of the same steps as above. E.g. the call with (1,2) and (1,11) does:

1. 排序点：（1,2），（1,11）
2. 在构建两个子集：（1,2）和（1,11）
3. 在分别与LT运行在（1,2）算法和（1,11）=再次递归调用。其结果是dLmin =无穷大，dRmin =无穷大
4. dLRmin = 9
5. 在结果=分钟（dLmin，dRmin，dLRmin）= 9

这篇关于最近对算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！