常用算法设计方法5
发布时间：2006-07-25 12:02
点击：
2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。
最接近点对问题的提法是：给定平面上
n个点，找其中的一对点，使得在
n个点的所有点对中，该点对的距离最小。
严格地说，最接近点对可能多于
1对。为了简单起见，这里只限于找其中的一对。
这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他
n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要
O(n2)的计算时间。我们能否找到问题的一个
O (nlogn)算法。
这个问题显然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上
n个点的集合
S分成
2个子集
S1和
S2，每个子集中约有
n/2个点，然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由
S1和
S2的最接近点对，如何求得原集合
S中的最接近点对，因为
版权申明:未经书面授权请勿转载本站信息!!作品版权归所属媒体与作者所有!!
|
您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任
留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。 |
2003-2005 Ksw123.com All Rights Reserved. - TOP
Copyright © 2006 Ksw123.com. All rights reserved.中国考题网 版权所有