BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ JerryCheng (chengy) 于 (Tue Nov 4 17:34:48 2008) 提到: 找出平面中距离最短的两个点：在X-Y坐标平面内有N个点，找出这N个点中距离最短的那两个点。据说是用分治法，具体的就不知道了，望高人指点！ ☆─────────────────────────────────────☆ hmcj (子曰|春秋) 于 (Tue Nov 4 17:35:48 2008) 提到: 分治：画个线，分成3种情况 ☆─────────────────────────────────────☆ prating (竹下生|久夜|亲亲尾巴爱尾巴) 于 (Tue Nov 4 17:49:00 2008) 提到: 啥叫距离最短的两个点？【在 JerryCheng (chengy) 的大作中提到: 】 : 找出平面中距离最短的两个点： : 在X-Y坐标平面内有N个点，找出这N个点中距离最短的那两个点。 : 据说是用分治法，具体的就不知道了，望高人指点！ : ................... ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Tue Nov 4 17:55:30 2008) 提到: 经典飞机场问题 ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Tue Nov 4 17:58:21 2008) 提到: 我到现在都搞不清楚，分治和递归有啥不同。我就觉得有时候，让我把想法变成代码，那个困难啊。不负责任地写个伪代码： f(2) = 两个点之间的距离 f(N) = min{ f(N-1), N-1个点与另外的那个点的距离 } 【在 yegle 的大作中提到: 】 : 握手… ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Tue Nov 4 17:59:39 2008) 提到: 还是平方的算法【在 ericyosho 的大作中提到: 】 : 我到现在都搞不清楚，分治和递归有啥不同。 : 我就觉得有时候，让我把想法变成代码，那个困难啊。 : 不负责任地写个伪代码： : ................... ☆─────────────────────────────────────☆ PtwCJ (鲜的每日C|头像不是我，我是长毛贼~~) 于 (Tue Nov 4 18:13:39 2008) 提到: 算法导论有讲，最优应该是nlogn ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Tue Nov 4 18:29:18 2008) 提到: 嗯，一般分治，好像都能把 N 降到 log2N 。只是我还不会灵活运用。所以不怕大家笑话，学校ACM的那些题，我过的都是水题。到了100+就瓶颈了。 (@@)~~~ 【在 PtwCJ 的大作中提到: 】 : 算法导论有讲，最优应该是nlogn ☆─────────────────────────────────────☆ yywbupt (干) 于 (Tue Nov 4 18:31:49 2008) 提到: 【在 JerryCheng 的大作中提到: 】 : 找出平面中距离最短的两个点： : 在X-Y坐标平面内有N个点，找出这N个点中距离最短的那两个点。 : 据说是用分治法，具体的就不知道了，望高人指点！算法导论 33.4节 ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Tue Nov 4 18:58:29 2008) 提到: 参考： http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html [upload=1][/upload] 算法： 0：把所有的点按照横坐标排序 1：用一条竖直的线L将所有的点分成两等份 2：递归算出左半部分的最近两点距离d1，右半部分的最近两点距离d2，取d=min(d1,d2) 3：算出“一个在左半部分，另一个在右半部分”这样的点对的最短距离d3。 4：结果＝min(d1,d2,d3) 关键就是这第3步。貌似这需要n^2的时间，把左边每个点和右边每个点都对比一下。其实不然。秘密就在这里。首先，两边的点，与分割线L的距离超过d的，都可以扔掉了。其次，即使两个点P1,P2（不妨令P1在左边，P2在右边）与分割线L的距离（水平距离）都小于d，如果它们的纵坐标之差大于d，也没戏。就是这两点使得搜索范围大大减小：对于左半部分的，与L的距离在d之内的，每个P1来说：右半部分内，符合以上两个条件的点P2最多只有6个！原因就是： d是两个半平面各自内，任意两点的最小距离，因此在同一个半平面内，任何两点距离都不可能超过d。我们又要求P1和P2的水平距离不能超过d，垂直距离也不能超过d，在这个d*2d的小方块内，最多只能放下6个距离不小于d的点。因此，第3步总的比较距离的次数不超过n*6。第3步的具体做法是： 3.1 删除所有到L的距离大于d的点。 O(n) 3.2 把右半平面的点按照纵坐标y排序。 O(nlogn) 3.3 对于左半平面内的每个点P1，找出右半平面内纵坐标与P1的纵坐标的差在d以内的点P2，计算距离取最小值，算出d3。 O(n*6) = O(n) 因为3.2的排序需要O(nlogn)，所以整个算法的复杂度就是O(n((logn)^2))。改进：我们对3.2这个排序的O(nlogn)不太满意。既然整个算法是递归的，我们可以利用第2步的子递归中已经排好序的序列，在第3.2部归并这两个子列，这样3.2的复杂度变成了O(n)。这样，整个算法就是O(nlogn)的。 ☆─────────────────────────────────────☆ houxionghui (侯子) 于 (Tue Nov 4 23:28:35 2008) 提到: 离散数学书上讲过算法…… ☆─────────────────────────────────────☆ jokerlee (Jackal The Dire) 于 (Wed Nov 5 08:08:27 2008) 提到: 经典分治，详见《离散数学》 Divide and Conquer ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Wed Nov 5 10:52:08 2008) 提到: 其次，即使两个点P1,P2（不妨令P1在左边，P2在右边）与分割线L的距离（水平距离）都小于d 我们又要求P1和P2的水平距离不能超过d 这两句是不是有矛盾啊？都和中线相差d，那P1P2不是应该小于2d么？还有如果一刀砍下去正好哪个倒霉孩子被劈中了，怎么算？单独拿出来讨论？ ☆─────────────────────────────────────☆ jokerlee (Jackal The Dire) 于 (Wed Nov 5 12:44:50 2008) 提到: 由p1p2小于d推出p1、p2到L的距离肯定都小于d，right? 你理解反了被中劈了可以随便放在左边或者右边【在 ericyosho 的大作中提到: 】 : 其次，即使两个点P1,P2（不妨令P1在左边，P2在右边）与分割线L的距离（水平距离）都小于d : 我们又要求P1和P2的水平距离不能超过d : 这两句是不是有矛盾啊？都和中线相差d，那P1P2不是应该小于2d么？ : ................... ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Wed Nov 5 12:53:00 2008) 提到: p1p2为什么要小于d，没道理啊。如果真是这样的话，就是默认，肯定一个左边一个右边的这种情况才能达到最小值。这个假设是没有根据的。【在 jokerlee 的大作中提到: 】 : 由p1p2小于d推出p1、p2到L的距离肯定都小于d，right? 你理解反了 : 被中劈了可以随便放在左边或者右边 ☆─────────────────────────────────────☆ jokerlee (Jackal The Dire) 于 (Wed Nov 5 12:59:39 2008) 提到: 。。。。。。。。没有说默认啊 d是左右两边的最小值现在需要找这样一个点对：一个点在线左边，一个点在线右边，他们的距离小于d 满足条件的点对肯定符合p1、p2到L的距离小于d，所以只要在一个2d*d的矩形中枚举检验就行了，而一个2d*d的矩形最多有6个点（应为每个点对距离>=d）,所以枚举的复杂度为6n ☆─────────────────────────────────────☆ noname (无名亡者) 于 (Wed Nov 5 20:06:28 2008) 提到: 【在 ericyosho 的大作中提到: 】 : p1p2为什么要小于d，没道理啊。 : 如果真是这样的话，就是默认，肯定一个左边一个右边的这种情况才能达到最小值。 : 这个假设是没有根据的。因为最终要求的是min(d1,d2,d3) ，所以所有到分割线的水平距离比min(d1,d2)大的都没必要考虑。。。 ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Wed Nov 5 22:28:54 2008) 提到: 正解【在 noname 的大作中提到: 】 : 因为最终要求的是min(d1,d2,d3) ，所以所有到分割线的水平距离比min(d1,d2)大的都没必要考虑。。。

[合集] [求助]求教一道算法题