19594| 39
|
[【高飞鸟】] 【越飞越高讲堂10】分治、递归、分类和最小距离(更新至2012.7) |
评分本帖被以下淘专辑推荐:
| ||
| ||
点评
楼主写的好,借楼写下自己的理解
所以任何题目都有可能使用分冶思路来提高效率,但并非一定,除非你在将问题规模缩小的同时还能找到使你提出的方法具有完备性的途径。
3.比较1.2的所有结果,答案就在其中。
剩下的就是使用我们的编程技巧来实现上面的过程并求出结果.递归或非递归任你选择,如果你习惯用用数学公式去描述解决的方法,那就使用递归编程,会简练许多。
1.对平面点集按x或y坐标分带,分带规模有你决定,对各分带运用O(n^2)算法,求出所有可能的最近点对.
2.分别对点集的分界线两侧一定范围的点求出所有可能的最近点对{注意点对的两点必然分布在分界线的两侧}.
但如果将n分成一小撮一小撮,对每撮分别使用O(n^2)算法,结果并不完备,因为最近点对可能分布在其中的一小撮中,也可能点对的两个点分布在不同的小撮中.
因此想到这里该问题的分冶解法就形成了.
简单地说,平面点集求解最近点对具有采用分冶思路解决的可能:
O(n^2)计算时间的算法是求解平面或三维点集最近点对的基础算法,该算法是完备的,但当n极大时,效率变得难以接受.
| ||
发表于 2012-5-6 19:12:23
|
显示全部楼层
| ||