我的“最接近对”问题的分治法逻辑有什么问题？ [英] What is wrong with my logic for the divide and conquer algorithm for Closest Pair Problem?

问题描述

我一直在遵循Coursera的算法课程，并想出了一个关于最接近对问题的除法/征服算法的想法，我想弄清楚。

I have been following Coursera's course on Algorithms and came up with a thought about the divide/conquer algorithm for the closest pair problem, that I want clarified.

根据Roughgarden教授的算法（您可以在此处如果您有兴趣）：
对于给定的一组点P，我们有两个副本-在X和Y方向上排序-Px和Py，该算法可以表示为

As per Prof Roughgarden's algorithm (which you can see here if you're interested): For a given set of points P, of which we have two copies - sorted in X and Y direction - Px and Py, the algorithm can be given as

closestPair（Px，Py）：

closestPair(Px,Py):

1. 将点分为左半部分-Q和右半部分-R，并沿x和y方向形成两半的排序副本-Qx，Qy，Rx，Ry


2. 让closetairPair（Qx，Qy）为点p1和q1


3. 让最近的对（Rx，Ry）为p2，q2


4. 让delta为dist（p1，q1）和dist（p2，q2）的最小值


5. 这是不幸的情况，让p3，q3是最接近的SplitPair（Px，Py，delta）


6. Ret最好的结果

1. Divide points into left half - Q, and right half - R, and form sorted copies of both halves along x and y directions - Qx,Qy,Rx,Ry
2. Let closestPair(Qx,Qy) be points p1 and q1
3. Let closestPair(Rx,Ry) be p2,q2
4. Let delta be minimum of dist(p1,q1) and dist(p2,q2)
5. This is the unfortunate case, let p3,q3 be the closestSplitPair(Px,Py,delta)
6. Return the best result

现在，我要说明的内容与步骤5有关。
我应该事先说一下，我的建议几乎没有任何改善，但是如果您仍然有兴趣，请继续阅读。

Now, the clarification that I want is related to step 5. I should say this beforehand, that what I'm suggesting, is barely any improvement at all, but if you're still interested, read ahead.

R教授说，由于这些点已经被排序了在X和Y方向上，要在步骤5中找到最佳对，我们需要从下到上对宽度为2 * delta的条带中的点进行迭代，在内部循环中，我们只需要7个比较即可。

Prof R says that since the points are already sorted in X and Y directions, to find the best pair in step 5, we need to iterate over points in the strip of width 2*delta, starting from bottom to up, and in the inner loop we need only 7 comparisions. Can this be bettered to just one?

我怎么可能以纯文本的方式解释似乎有点困难，所以我画了一个图并写在纸上并上传在这里：

How I think is possible seemed a little difficult to explain in plain text, so I drew a diagram and wrote it on paper and uploaded it here:

由于没有其他人提出这个建议，所以我很确定自己的思路有误。
但是我现在确实已经在HOURS上考虑了这一点，我只是不得不发布此内容。

Since no one else came up with is, I'm pretty sure there's some error in my line of thought. But I have literally been thinking about this for HOURS now, and I just HAD to post this. It's all that is in my head.

有人可以指出我要去哪里了吗？

Can someone point out where I'm going wrong?

推荐答案

您在第5点的结论不正确。尝试将点A画得更靠近分界线。

Your conclusion in bullet point #5 is incorrect. Try drawing point A closer to the dividing line.

您可以在A的三角形内有两个点（一个在上方，一个在下），这些点不在彼此的三角形内。

You can have two points within delta of A (one above, one below) that are not within delta of each other.

  | B
  | 
 A|
  | 
  | C

此处， dist（A，B）= dist（A，C ）< dist（B，C）。

这是为什么图片有助于获得直觉的完美示例，但仍然需要证据证明得出结论。

This is a perfect example of why pictures are helpful to gain intuition, but proofs are still necessary to back up your conclusions.

这篇关于我的“最接近对”问题的分治法逻辑有什么问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！