我一直在跟进Coursera的算法课程,并对最接近点问题的分治算法产生了疑问,希望得到澄清。
根据Roughgarden教授的算法(如果您感兴趣可以在这里看到): 对于给定的点集P,我们有两个副本 - 按X和Y方向排序的Px和Py。该算法可表示为
closestPair(Px,Py):
1.将点分成左半部分Q和右半部分R,并沿着x和y方向形成两个有序的副本-Qx、Qy、Rx、Ry 2.令closestPair(Qx,Qy)为点p1和q1 3.令closestPair(Rx,Ry)为p2,q2 4.令delta为dist(p1,q1)和dist(p2,q2)的最小值 5.这是不幸的情况,让p3,q3成为closestSplitPair(Px,Py,delta) 6.返回最佳结果
现在,我想要澄清的是第五步相关的内容。需要事先说明的是,我所提出的改进几乎没有什么改善作用,但如果您仍然感兴趣,请继续阅读。
R教授说,由于点已经按X和Y方向排序,为了在第5步中找到最佳对,我们需要遍历宽度为2*delta的条带上的点,从下到上开始,在内循环中只需要7次比较。这个过程能否优化到只需要一次?
我认为可能有一种方法,但用纯文本解释有些困难,所以我画了一个图并将其写在纸上上传到了这里:
根据Roughgarden教授的算法(如果您感兴趣可以在这里看到): 对于给定的点集P,我们有两个副本 - 按X和Y方向排序的Px和Py。该算法可表示为
closestPair(Px,Py):
1.将点分成左半部分Q和右半部分R,并沿着x和y方向形成两个有序的副本-Qx、Qy、Rx、Ry 2.令closestPair(Qx,Qy)为点p1和q1 3.令closestPair(Rx,Ry)为p2,q2 4.令delta为dist(p1,q1)和dist(p2,q2)的最小值 5.这是不幸的情况,让p3,q3成为closestSplitPair(Px,Py,delta) 6.返回最佳结果
现在,我想要澄清的是第五步相关的内容。需要事先说明的是,我所提出的改进几乎没有什么改善作用,但如果您仍然感兴趣,请继续阅读。
R教授说,由于点已经按X和Y方向排序,为了在第5步中找到最佳对,我们需要遍历宽度为2*delta的条带上的点,从下到上开始,在内循环中只需要7次比较。这个过程能否优化到只需要一次?
我认为可能有一种方法,但用纯文本解释有些困难,所以我画了一个图并将其写在纸上上传到了这里:
既然没有其他人提出来,我相当确定我的思路中存在一些错误。但我已经想了几个小时了,我必须发帖。这就是我脑海中的全部内容。
有人能指出我哪里错了吗?