4.6 实验项目——最近对问题.ppt

* 4.6 实验项目——最近对问题 1. 实验题目 设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。 2. 实验目的 （1）进一步掌握途归算法的设计思想以及途归程序的调试技术； （2）理解这样一个观点：离治与途归经常同时应用在算法设计之中。 3. 实验要求 （1）分别用蛮力法和离治法求解最近对问题； （2）分析算法的时间性能，设计实验程序验证分析结论。 将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。 （1）划分：既然是离治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。 （2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用途归的方法求解各个子问题，有时途归处理也可以用循环来实现。 （3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，离治算法的有效性很大程度上依赖于合并的实现。 例：计算an，应用离治技术得到如下计算方法： 34 32 32 81 31 31 9 31 31 9 3 3 3 3 分解问题 求解每个子问题 合并子问题的解 不是所有的离治法都比简单的蛮力法更有效。 分析时 间性能 ? ? é ù ? í ì ′ = = 1 1 2 2 n a a n a a n n n 如果 如果 在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。 Hanio(3,A,B,C) Hanio(2,A,C,B) Hanio(1,A,B,C) Move (A,C) Move (A,B) Hanio(1,C,A,B) Hanio(1,A,B,C) Hanio(2,A,C,B) Move (C,B) Hanio(1,C,A,B) Move (A,C) Hanio(2,B,A,C) Hanio(1,B,C,A) Move (B,C) Hanio(1,A,B,C) Hanio(1,B,C,A) Move (A,C) Hanio(2,B,A,C) Move (B,A) Hanio(1,A,B,C) 结束 （1）划分：将待排序序列r1, r2, …, rn划分为两个长度相等的子序列r1, …, rn/2和rn/2＋1, …, rn； （2）求解子问题：分别对这两个子序列进行排序，得到两个有序子序列； （3）合并：将这两个有序子序列合并成一个有序序列。 r1 … … rn/2 rn/2＋1 … … rn 划分 r‘1… …r’n/2 r’n/2＋1… …r’n 途归处理 r1……rn/2rn/2＋1 ……r n 合并解 [ r1 … … ri-1 ] ri [ ri+1 … … rn ] 均≤ri 轴值 均≥ri 位于最终位置 *