我正在尝试执行最接近的对算法-但是有一个区域完全卡住了我。
可以使用递归分治法在O（n log n）时间内解决此问题，例如：
1）根据点的x坐标对点进行排序。
2）用垂直线x = xmid将点集分成两个大小相等的子集。
3）在左子集和右子集中递归解决问题。这分别产生了左侧和右侧最小距离dLmin和dRmin。
4）在一组点对中找到最小距离dLRmin，其中一个点位于垂直分割线的左侧，第二个点位于右侧。
5）最终答案是dLmin，dRmin和dLRmin中的最小值。
我的问题出在第3步：假设您将8元素数组分为两半，在左半部分上有4个点-1,2,3和4。又说点2和3是这4点中最接近的一对。好吧，如果您继续将此子集递归划分为两半，最终将最终计算出1-2（在左侧）之间的最小值，您将计算出3-4（在右侧）之间的最小值，然后返回这两对线之间的最小距离线对
但是-您完全错过了2-3之间的距离，因为它们在相反的方向，所以您从未计算过它...那么如何解决此问题？请注意，在此递归过程之后，步骤4是如何出现的，它似乎是一个独立的步骤，仅适用于步骤3之后的最终结果，而不适用于步骤3中发生的子数组的每个后续划分。还是有其他方法我错过了？
这些步骤有点误导，因为步骤2-5都是递归的一部分。在递归的每个级别，您都需要计算dLmin，dRmin和dLRmin。这些中的最小值作为该递归级别的答案返回。
以您的示例为例，您将计算dLmin作为点1和点2之间的距离，dRmin作为点3和点4之间的距离，然后dLRmin作为点2和3之间的距离。由于在您的假设情况下dLRmin是最小的，它会被退回。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句