《递归与分治》PPT课件.ppt

《《递归与分治》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《递归与分治》PPT课件.ppt（117页珍藏版）》请在三一办公上搜索。

1、 2005,第2章 递归与分治策略,几个例子2.1 递归的概念2.2 分治法的基本思想2.3 分治法的应用本章小结,2,几个例子,称球游戏给定n个球，其中一个球为次品。次品在外表上与正常球无区别，但重量有分别（可能偏重或偏轻）。现在给一个天平，问：需要称几次才能将次品甄别出来？募捐问题向贫困山区儿童募捐10,000元。世界杯足球赛全球200多支球队里，选出最好的。,分治法的设计思想是:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。凡治众如治寡，分数是也。-孙子兵法,3,2.1 递归的概念,例1:阶乘函数 阶乘函数可递归地定义为：,注意：(1)边界条件与递归方

2、程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。(2)非递归定义：,4,2.1 递归的概念,例2:Fibonacci数列问题引入裴波那契（Fibonacci leonardo，约1170-1250）是意大利著名数学家在他的著作算盘书中许多有趣的问题，最富成功的问题是著名的“兔子繁殖问题”：如果每对兔子每月繁殖一对子兔，而子兔在出生后第二个月就有生殖能力，试问一对兔子一年能繁殖多少对兔子？问题分析,5,2.1 递归的概念,6,2.1 递归的概念,数列的特点（1）数列的增长速度（2）自然科学中的若干实例（3）构造一个新数列,7,定义：,2.1 递归的概念,8,2.

3、1 递归的概念,如何求解？解法1：O(0.618n)int fib(int n)if(n=0)|(n=1)return n;return fibonacci(n-1)+fibonacci(n-2);解法2：O(n)解法3：O(logn),fib(110)：O(0.618n)1022 次运算 O(n)111 次运算 O(logn)7 次运算,9,2.1 递归的概念,思考：楼梯问题有一楼梯共有n阶，上楼可以一步上一阶，也可以一步上两阶。编一个程序，计算共有多少种不同的走法？,10,例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A

4、(n,m)定义如下：,2.1 递归的概念,11,2.1 递归的概念,Ackerman函数A(n,0)n+2A(n,1)2nA(n,2)2n。A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。,12,2.1 递归的概念,例4 排列问题设计一个递归算法生成n个元素r1,r2,rn的全排列。设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。集合X中元素的全排列记为perm(X)，(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。,13,2.1 递归的概念,R的全排列可归纳定义如下：当n=1时，perm(R)=(r)，其中r是集合R中唯一

5、的元素；当n1时，perm(R)由:(r1)perm(R1)(r2)perm(R2)(rn)perm(Rn)构成。参考算法：,14,2.1 递归的概念,例5 整数划分问题将一个正整数n表示成形如下式的一系列正整数的和，称为n的一个划分。形如：nn1n2nk其中：(ni1，i1,2,k，k1)且 nn1n2nk 1,15,2.1 递归的概念,例如：整数6的分划数有11种:6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1;,16,2.1 递归的概念,分析：将最大加数n1不大于m的划分个数记作q(n,m)(1)

6、q(n,1)=1,n1;(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1 n-1的划分组成。(4)q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1 m-1 的划分组成。,17,而：正整数n的划分数p(n)=q(n,n)。,2.1 递归的概念,因此：q(n,m)的递归定义如下,18,2.1 递归的概念,例6 Hanoi塔问题问题描述：,19,问题分析：,2.1 递归的概念,Hanoi(n,A,B,C),圆盘

7、数 源柱 辅助柱 目标柱,20,=,+,+,2.1 递归的概念,21,递归求解void hanoi(int n,int a,int b,int c)if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);递归函数的运行轨迹,2.1 递归的概念,22,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),Move(C,B),Move(A,C),Hanio(2,B,A,C),Hanio(1,B,C,A),Move(B,C),Hanio(1,A,B,

8、C),Move(A,C),Move(B,A),23,分析：规模为n的Hanoi(n)问题，可以分解为2个规模为n-1的Hanoi(n-1)问题和一个Move 操作。所以，n个盘子的移动次数为,2.1 递归的概念,若n=64，则移动次数为264-1,264118,446,744,073,709,551,615,24,2.1 递归的概念,264118,446,744,073,709,551,615是个什么概念？实例1：假设每秒钟移动一次，一年约31556926秒，计算表明：移动64个盘子需要5800多亿年。实例2：国王的麦子问题一个高4米、宽10米的粮仓装麦子，这个粮仓有3000万公里长，能绕地球

9、赤道700圈，可以把地球全部表面（包括海洋）铺上2米厚的小麦层！它相当于全世界两千多年小麦产量的总和,25,广义hanoi问题问题描述算法分析,Hanoi(n,A,B,C,D),圆盘数 源柱 辅助柱 目标柱,2.1 递归的概念,26,2.1 递归的概念,递归的优点和缺点优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,27,2.1 递归的概念,28,2.1 递归的概念,消除递归的方法采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本

10、质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。用递推来实现递归函数。通过变换能将一些递归转化为尾递归，从而迭代求出结果。注意：后两种方法在时空复杂度上均有较大改善，但其适用范围有限。,29,分治法的设计思想是:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。凡治众如治寡，分数是也。-孙子兵法,2.2 分治法的基本思想,30,2.2 分治法的基本思想,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，且各个子问题是相互独立的，即子问题之间不包含公共的子问题。利用该

11、问题分解出的子问题的解可以合并为该问题的解；,31,2.2 分治法的基本思想,分治法（Divide and Conquer）的基本思想:分解(Divide)：将一个规模为n的问题，分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同。求解(Conquer):若子问题规模较小而容易被解决则直接解，否则递归地解这些子问题。合并(Merge)：将各个子问题的解合并得到原问题的解。,32,2.2 分治法的基本思想,分治法的 设计模式divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题 divide P into smaller subinsta

12、nces P1,P2,.,Pk；/分解问题 for(i=1;i=k;i+)/递归的解各子问题 yi=divide-and-conquer(Pi);return merge(y1,.,yk);/将各子问题的解合并/为原问题的解,33,2.2 分治法的基本思想,启发式规则：平衡子问题：在用分治法设计算法时，最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重

13、复地解公共的子问题。,34,2.2 分治法的基本思想,分治法的典型情况,35,分治法的时间复杂性分析,通过迭代法求得方程的解：,2.2 分治法的基本思想,36,例：二分搜索技术,问题提出：给定已按升序排好序的n个元素a0:n1，现要在这n个元素中找出一特定元素x。分析：,37,2.3 分治法的应用,数值计算问题中的分治法组合问题中的分治法排序问题中的分治法几何问题中的分治法,38,应用专题一,数值计算问题中的分治法大数及其存储大整数的乘法strassen矩阵乘法,39,大数及其存储,大数计算机存储数据是按类型分配空间的。例如：在微型机上,40,大数的存储方案数组数值数组从计算的方便性考虑，决定

14、将数据是由低到高还是由高到低存储到数组中；可以每位占一个数组元素空间，也可几位占一个数组元素空间。字符型数组从键盘输入要处理的高精度数据，无需对高精度数据进行分段输入，但计算是需要类型转换的操作。,大数及其存储,41,大数及其存储,大数的运算加法减法乘法100！=93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963 895217 599993 229915 608914 463976 156578 286253 697920 827223 758251 185210 916864 000000 0000

15、00 000000 000000除法,42,问题描述：设X和Y都是n位的二进制整数，请设计一个有效的算法，可以进行两个n位大整数的乘法运算。分析：1.小学的方法：O(n2)效率太低,大整数的乘法,43,2.可以用分治法的原理设计一个更有效的算法。将n位的二进制整数分为2段：,则：X=A2n/2+B（乘2n/2，相当于左移n/2位）Y=C2n/2+D于是：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD(1),大整数的乘法,44,大整数的乘法,效率：4次n/2位整数乘法(AC,AD,BC,BD)；3次不超过n位整数加法；2次移位(分别对应乘以2n和2n/2)所有

16、加法和移位共用O(n)步计算。,时间复杂性分析T(n)=O(n2)没有改进,45,时间复杂性分析 T(n)=O(nlog3)=O(n1.59)较大的改进,大整数的乘法,改进：把(1)式稍作修改：XY=AC2n+(AB)(DC)+AC+BD)2n/2+BD(2)效率：3次n/2位整数乘法(AC,BD,(AB)(DC)；6次不超过n位整数加、减法和2次移位；,46,大整数的乘法,Char*Mult(char X,char Y,int n)/两个n位整数相乘 S=sign(X)*sign(Y);/取乘积的符号 X=abs(X);Y=abs(Y);if(n=1)return(S*X*Y);else A

17、=X的左边n/2位；B=X的右边n/2位；C=Y的左边n/2位；D=Y的右边n/2位；m1=Mult(A,C,n/2);m2=Mult(A-B,D-C,n/2);m3=Mult(B,D,n/2);S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);return S;,注意：该算法可改为十进制数乘法，只需将基数2变为10，即：2n 10n,2n/2 10n/2,47,大整数的乘法,分析传统的方法：O(n2)效率太低分治法:O(n1.59)较大的改进更快的方法？对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。,48,strassen矩阵乘法

18、,矩阵乘法问题描述AnnBnn=Cnn求解方法传统方法：O(n3)分治法O(n2.81)O(n2.376),49,分治法将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵，每个子矩阵都是n/2n/2的方阵。由此可将方程C=AB重写为：,由此可得：,strassen矩阵乘法,50,为了降低时间复杂度，必须减少乘法的次数。Strassen矩阵乘法,strassen矩阵乘法,51,验证:C22=M5+M1-M3-M7=(A11+A22)(B11+B22)+A11(B12-B21)-(A21+A22)B11-(A11-A21)(B11+B12)=A11B11+A11B22+A22B11+A22B2

19、2+A11B12-A11B22-A21B11-A22B11-A11B11-A11B12+A21B11+A21B12=A21B12+A22B22,strassen矩阵乘法,52,strassen矩阵乘法,53,完整的Strassen算法如下：STRASSEN(n,A,B,C)if(n=2)MATRIX-MULTIPLY(A，B，C);/普通2*2矩阵相乘 else/将矩阵A和B分块;STRASSEN(n/2,A11,B12-B22,M1);STRASSEN(n/2,A11+A12,B22,M2);STRASSEN(n/2,A21+A22,B11,M3);STRASSEN(n/2,A22,B21-

20、B11,M4);STRASSEN(n/2,A11+A22,B11+B22,M5);STRASSEN(n/2,A12-A22,B21+B22,M6);STRASSEN(n/2,A11-A21,B11+B12,M7);,strassen矩阵乘法,54,应用专题二,组合问题中的分治法棋盘覆盖问题循环日程赛安排问题最大子段和问题,55,问题描述：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,棋盘覆盖问题,56,棋

21、盘覆盖问题,例如：k2时的一个特殊棋盘,2k2k 的棋盘覆盖中，用到的骨牌数为(4k-1)/3,57,例如：,棋盘覆盖问题,58,分析：当k=0时，有1种覆盖方案当k 0时，考虑采用分治策略：,棋盘覆盖问题,59,算法实现P18算法分析:设T(k)为覆盖2k2k残缺棋盘的时间,当k=0时覆盖它需要常数时间O(1);当k0时,测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1),覆盖4个残缺子棋盘需四次递归调用,共需时间4T(k1)。,T(k)=O(4k)渐进意义下的最优算法,棋盘覆盖问题,60,还可以将棋盘覆盖推广到一般情况：,棋盘覆盖问题,61,问题描述：设计一个满足以下要求的比赛日程表：(

22、1)每个选手必须与其他n1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n1天。,循环赛日程表,62,循环赛日程表,例如：,63,循环赛日程表,分析：法1：分治策略按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,64,循环赛日程表,分析法2：递推法(迭代法),65,循环赛日程表,递推法(迭代法)即2k个选手的比赛日程在2k-1个选手的比赛日程基础上通过迭代完成，每次迭代，将问题分为4个部分：左上角：2k-1

23、个选手前半程的比赛日程左下角：另2k-1个选手前半程的比赛日程，由左上角加2k-1得到右上角：将左下角抄到右上角，得到另2k-1个选手后半程的比赛日程。右下角：将左上角抄到右下角，得到2k-1个选手后半程的比赛日程。,66,问题提出(P59)：给定由n个整数（可能为负数）组成的序列：a1,a2,an,求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为0。依其定义，所求的最优值为：,最大子段和问题,67,1.最大子段和问题的简单算法int MaxSum(int n,int*a,int 显然：T(n)=O(n3),最大子段和问题,68,2.一点改进int MaxSum(int n,int

24、 an,int 显然：T(n)=O(n2),最大子段和问题,69,3.最大子段和问题的分治策略划分：按照平衡子问题的原则，将序列(a1,a2,an)划分成长度相同的两个子序列(a1,an/2)和(an/21,an)；求解子问题：合并：比较在划分阶段的三种情况下的最大子段和，取三者之中的大者为原问题的解。,最大子段和问题,70,最大子段和问题,71,int MaxSubSum(int*a,int left,int right)int sum=0;if(left=right)sum=aleft0?aleft:0;else int center=(left+right)/2;int leftsum=

25、MaxSubSum(a,left,center);int rightsum=MaxSubSum(a,center+1,right);int s1=0,lefts=0;for(int i=center;i=left;i-)lefts+=ai;if(lefts s1)s1=lefts;/for,最大子段和问题,72,int s2=0,rights=0;for(int j=center+1;j s2)s2=rights;sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;/elsereturn sum;,最大子段和问题,73

26、,最大子段和问题,int MaxSum(int n,int*a)return MaxSubSum(a,1,n);,复杂度分析,74,最大子段和问题,应用举例：最佳游览路线问题问题描述：某旅游区的街道成网格状。其中：东西向的街道为旅游街，南北向的为林荫道。规定旅游街为单行道，旅客只能从西向东走；在林荫道即可从南向北，也可从北向南。一个旅游者可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助这位旅游者寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。,75,最大子段和问题,例如：,76,应用专题三,排序问题中的分治法排序无处不在，“乾坤有序，万物有律”几种典型的排序方法合并排序

27、快速排序选择问题,77,合并排序,基本思想：划分：将待排序元素分成大小大致相同的2个子序列求解子问题分别对2个子序列进行排序合并将排好序的两个子序列合并成为一个有序序列。,78,合并排序,二路归并排序的分治策略是：划分：将待排序序列r1,r2,rn划分为两个长度相等的子序列r1,rn/2和rn/21,rn；求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；合并：将这两个有序子序列合并成一个有序序列。,79,合并排序,如图所示,80,合并排序,算法描述（递归）：void MergeSort(Type a,int left,int right)if(leftright)/至少有2个元素

28、int i=(left+right)/2;/取中点 mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组b copy(a,b,left,right);/复制回数组a,复杂度分析T(n)=O(nlogn)渐进意义下的最优算法,81,合并排序,实验表明合并排序在n30后即体现出比（标准）插入排序更加优越的性能。需要注意的是：合并排序的时间复杂性适合于所有情况：最好、最坏或平均。这是合并排序的最大的特点“一视同仁”复杂性的关键体现在合并过程，“先享受，然后付出代价”合并排序的另一个缺陷：“异地排序”（out

29、 of place sort）,82,快速排序,快速排序的分治策略：（1）划分选定一个记录作为轴值(杠杆点)，以轴值为基准将整个序列划分为两个子序列r1 ri-1和ri+1 rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；,83,快速排序,（2）求解子问题分别对划分后的每一个子序列递归处理；（3）合并由于对子序列r1 ri-1和ri+1 rn的排序是就地进行的，所以合并不需要执行任何操作。,“先付出，然后享受劳动成果”,84,快速排序,例如：,38,85,templateint Partition(Type a,int p,int r)int i=p,j=

30、r;Type x=ap;while(ix)j-;ai=aj;while(ij,快速排序,86,快速排序算法,void QuickSort(Type a,int p,int r)if(pr)int q=Partion(a,p,r)QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,r);/对右半段排序,87,快速排序,快速排序算法的性能取决于划分的对称性。,最坏情况复杂度分析,最好情况复杂度分析,平均情况复杂度分析,88,2006计算机科学学院 刘芳 60,各排序算法平均时间的曲线图,89,快速排序,快速排序算法的优点算法的韧性很强，只要分解不是按照最坏情况进行

31、，其排序的结果就能达到最优。原地排序算法另外，人们可以通过对轴值的选择进行微调，就能使算法得到巨大改善，实验表明：快速排序的速度是合并排序的2倍。思考：轴值的选取？传统的方法 一种安全的做法随机选取中值法三值中值法,90,随机化快速排序,基本思想ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。算法描述随机数发生器int random(int a,int b)return rand()%(ba)+a,91,随机化快速排序,随机化的划分算法int randomizedPartion(type a,int p,int r)int i=ramdom

32、(p,r);swap(ai,ap);return Partition(a,p,r);,92,随机化快速排序,随机化快速排序算法void QuickSort_random(Type a,int p,int r)if(pr)int q=randomizedpartion(a,p,r)QuickSort_random(a,p,q-1);/对左半段排序 QuickSort_random t(a,q+1,r);/对右半段排序,93,选择问题,问题提出：设无序序列T=r1,r2,rn，T的第k（1kn）小的元素定义为T按升序排列后在第k个位置上的元素。对给定序列T和一个整数k，寻找T的第k小的元素的问题称

33、为选择问题。应用：选择问题的一个应用就是寻找中值元素。,94,选择问题,应用实例中值滤波在信号采集过程中，由于电子设备的不稳定性会对获取的信号产生噪声，中值滤波就是一种降噪技术。一维信号中值滤波是用中值代替规定位置（一般是原始信号序列的中心位置）的信号值。对二维的数字图像而言，中值滤波就是用一个活动窗口沿图像移动，窗口中心位置的象素灰度用窗口内所有象素灰度的中值来代替。,95,解决方法法1：排序法 O(nlogn)法2：基于随机划分的选择算法平均情况：T(n)O(n)法3：线性时间选择 最坏情况：T(n)O(n),选择问题,96,法2：基于划分的选择算法：Template Type rando

34、mizedSelect(int p,int r,int k)if(p=r)return ap;int i=randomizedpartition(p,r),j=ip+1;if(k=j)return ai;else if(kj)return randomizedSelect(p,i,k);else return randomizedSelect(i+1,r,kj);,选择问题,97,选择问题,分析：,最好情况复杂度分析（若分点总是等分点）,最坏情况复杂度分析(分点左半总为空),平均情况复杂度分析,98,法3：线性时间选择：,选择问题,99,算法的时间复杂度分析,选择问题,100,应用专题四,几何

35、问题中的分治法最接近点对问题凸包问题,101,问题描述：设p1=(x1,y1),p2=(x2,y2),pn=(xn,yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。严格地讲，最接近点对可能多于一对，简单起见，只找出其中的一对作为问题的解。,最接近点对问题,102,最接近点对问题,简单应用假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。,103,最接近点对问题,分析：直接方法：通过检查所有的n(n1)/2对点，并计算每一对点的距离，可以找出距离最近的一对点

36、。这种方法所需要的时间为O(n2)。分治法,104,最接近点对问题,算法描述：if(n=2)用直接法寻找最近点对;else 将点集分成大致相等的两个部分A和B 确定A中最近的点对；确定B中的最近点对；确定一点在A中、另一点在B中的最近点对；从上面得到的三对点中，找出距离最小的一对点,105,最接近点对问题,一维的情形,106,最接近点对问题,分析：按这种分治策略求解最近对问题的算法效率取决于划分点m的选取，一个基本的要求是要遵循平衡子问题的原则。如果选取m(maxS+minS)/2，则有可能因集合S中点分布的不均匀而造成子集S1和S2的不平衡，如果用S中各点坐标的中位数（即S的中值）作为分割点

37、，则会得到一个平衡的分割点m，使得子集S1和S2中有个数大致相同的点。,107,最接近点对问题,下面来考虑二维的情形,108,最接近点对问题,应用分治法求解含有n个点的最近点对问题，其时间复杂性可由下面的递推式表示：,109,凸包问题,问题描述设p1=(x1,y1),p2=(x2,y2),pn=(xn,yn)是平面上n个点构成的集合S。S的凸包是包含所有点的最小凸多边形，或说是围绕所有点的最短路径。凸包应用：求凸包问题是一个基本计算几何。它在许多统计计算，特别是高维统计计算中起着重要的作用。许多计算几何的问题都是从求凸包开始，所以它是计算几何的基础问题。,110,凸包问题,分析,111,凸包问

38、题,求解凸包问题的分治算法,112,凸包问题,以上包为例,S1,1,S1,2,上包,113,凸包问题,算法实现关键问题:如何判断一个点是否在给定直线的左侧（或右侧）？分析：几何学中有这样一个定理：如果p1=(x1,y1),p2=(x2,y2),p3=(x3,y3)是平面上的任意三个点，则三角形p1p2p3的面积等于下面这个行列式的绝对值的一半：,114,凸包问题,并且有结论:当且仅当点p3=(x3,y3)位于直线p1p2的左侧时，该式的符号为正。于是：可以在一个常数时间内检查一个点是否位于两个点确定的直线的左侧，并且可以求得这个点到该直线的距离。,115,本章小结,知识点理解递归的概念。掌握设计有效算法的分治策略及时间复杂性递归方程的求解；掌握分治法的典型范例的求解思想，并加以应用数值计算问题组合问题排序问题几何问题,116,本章小结,分治法的实施基于以下几点认识小问题比大问题更容易解决将小问题解答组装成大问题的解所需要的成本低于直接解决大问题的成本。小问题又可以按照同样的方法分解为更小的问题。,117,本章小结,习题分析题：2-8，2-9，2-31算法实现题：2-1，2-3，2-4，2-5，2-8，2-10，2-14实验实验大纲作品计算器(大数)凸包线性时间选择,