我一直在关注 Coursera 的算法课程，并提出了关于最近对问题的分治算法的想法，我想澄清这一点。
根据 Roughgarden 教授的算法（你可以看到here https://class.coursera.org/algo-2012-002/lecture/download.mp4?lecture_id=18如果你有兴趣）：
对于给定的一组点 P，我们有两个副本 - 按 X 和 Y 方向排序 - Px 和 Py，算法可以给出为
最接近的对（Px，Py）：
- 将点分为左半部分 - Q 和右半部分 - R，并沿 x 和 y 方向形成两半的排序副本 - Qx,Qy,Rx,Ry
- 令closestPair(Qx,Qy)为点p1和q1
- 令closestPair(Rx,Ry)为p2,q2
- 令 delta 为 dist(p1,q1) 和 dist(p2,q2) 中的最小值
- 这是不幸的情况，令 p3,q3 为最接近的SplitPair(Px,Py,delta)
- 返回最好的结果
现在，我想要的澄清与步骤 5 相关。
我应该事先说一下，我的建议几乎没有任何改进，但如果您仍然感兴趣，请继续阅读。
R 教授表示，由于点已经在 X 和 Y 方向上排序，为了在步骤 5 中找到最佳对，我们需要迭代宽度为 2*delta 的条带中的点，从下到上，并在内部循环我们只需要 7 次比较。这可以比只有一个更好吗？
我认为如何可能似乎很难用纯文本解释，所以我画了一个图表并将其写在纸上并上传到这里：
既然没有人想出这一点，我很确定我的思路有一些错误。
但我实际上已经思考这个问题几个小时了，我只是不得不发布这个。这就是我脑子里的一切。
有人可以指出我哪里出错了吗？
你在第 5 点中的结论是不正确的。尝试将点 A 画得更靠近分界线。
A 的 delta 内可以有两个点（一个在上面，一个在下面），但彼此不在 delta 之内。
| B
|
A|
|
| C
Here, dist(A,B) = dist(A,C) < dist(B,C).
这是为什么图片有助于获得直觉的完美例子，但仍然需要证据来支持你的结论。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
