算法设计与分析王红梅第二分治法PPT课件

1、2021-11-171本章要点本章要点4.1 概概 述述 4.2 排序问题中的分治法排序问题中的分治法4.3 组合问题中的分治法组合问题中的分治法4.4 几何问题中的分治法几何问题中的分治法阅读材料阅读材料 递归函数的执行过程递归函数的执行过程第1页/共85页2021-11-172教学重点分治法的设计思想，各种经典问题的分治思想教学难点几何问题的分治算法教学内容及目标知识点教学要求了解理解掌握熟练掌握分治法设计思想归并排序和快速排序最大子段和问题棋盘覆盖问题最近对问题凸包问题学习目标学习目标第2页/共85页2021-11-1734.1.1 分治法的设计思想分治法的设计思想 4.1.2 分治法的

2、求解过程分治法的求解过程概概 述述第3页/共85页2021-11-174 将一个难以直接解决的大问题，划分成将一个难以直接解决的大问题，划分成一些规模较小的一些规模较小的子问题子问题，以各个击破，以各个击破，分而治之分而治之。更一般地说，将要求解的。更一般地说，将要求解的原问题原问题划分成划分成k个较小规模的子问题个较小规模的子问题，对这，对这k个子问题分别求个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分解。如果子问题的规模仍然不够小，则再将每个子问题划分为为k个规模更小的子问题，如此分解下去，个规模更小的子问题，如此分解下去，直到问题规模足够直到问题规模足够小，很容易求出

3、其解为止小，很容易求出其解为止，再将子问题的解合并为一个更大，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。规模的问题的解，自底向上逐步求出原问题的解。 分治法的设计思想：分治法的设计思想： 概述概述-分治法思想分治法思想第4页/共85页2021-11-1752. 独立子问题：独立子问题：各子问题之间相互独立，这涉及到分治法的各子问题之间相互独立，这涉及到分治法的效率，如果各子问题效率，如果各子问题不是独立的不是独立的，则，则分治法需要重复地解公分治法需要重复地解公共的子问题共的子问题。 1. 平衡子问题：平衡子问题：最好使子问题的规模大致相同。也就是将一最好使子问题

4、的规模大致相同。也就是将一个问题个问题划分成大小相等的划分成大小相等的k个子问题个子问题（通常（通常k2、4,），这），这种使子问题规模大致相等的做法是种使子问题规模大致相等的做法是出自一种平衡（出自一种平衡（Balancing）子问题的思想子问题的思想，它几乎，它几乎总是比总是比子问题规模不等子问题规模不等的做法要好。的做法要好。启发式规则：启发式规则：概述概述-分治法思想分治法思想第5页/共85页2021-11-176 子问题1的规模是n/2 子问题子问题1的解的解 子问题子问题2的解的解 子问题2的规模是n/2 原问题的解原问题的解 原问题的规模是n分治法的典型情况分治法的典型情况概述概

5、述-分治法思想分治法思想第6页/共85页2021-11-177 一般来说，分治法的求解过程由以下三个阶段组成：一般来说，分治法的求解过程由以下三个阶段组成： （1 1）划分：划分：既然是分治，当然要把规模为既然是分治，当然要把规模为n n 的原问题划的原问题划分为分为 k k 个个规模较小的子问题，并尽量使这规模较小的子问题，并尽量使这 k k 个子问题的规个子问题的规模大致相同。模大致相同。 （2 2）求解子问题：求解子问题：各子问题的解法与原问题的解法通常各子问题的解法与原问题的解法通常是相同的，可以是相同的，可以用递归用递归的方法求解各个子问题，有时递归的方法求解各个子问题，有时递归处理

6、也可以用循环来实现。处理也可以用循环来实现。 （3 3）合并：合并：把各个子问题的解合并起来，合并的代价因把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的情况不同有很大差异，分治算法的有效性很大程度上依赖有效性很大程度上依赖于合并的实现于合并的实现。 概述概述-分治法的求解过程分治法的求解过程第7页/共85页2021-11-178概述概述-分治法的求解过程分治法的求解过程分治法的一般过程分治法的一般过程 1 DivideConquer(P)(P) /求解规模为求解规模为n的问题的问题P 2 3 if (P(P的规模足够小的规模足够小) ) 直接求解直接求解P; 分解为分解为

7、k个子问题个子问题P1, P2, , Pk; 4 for (i=1;i * *= = =1122naanaannn如果如果第9页/共85页2021-11-17104.1.1 分治法的设计思想分治法的设计思想 4.1.2 一个简单的例子一个简单的例子数字旋转方阵数字旋转方阵概概 述述第10页/共85页2021-11-1711问题问题 输出如图输出如图4.3(a)所示所示N*N（1N10）的数字旋转方阵）的数字旋转方阵思路思路用二维数组表示方阵，从外层向里层填数，如图用二维数组表示方阵，从外层向里层填数，如图(b)所示，所示，将每一层的填数过程分为将每一层的填数过程分为ABCD四个区域。每填一层四

8、个区域。每填一层size减减2，终止条件是终止条件是size1。数字旋转方阵数字旋转方阵第11页/共85页2021-11-1712算法4.1：数字旋转方阵Full输入：当前层左上角要填的数字number，左上角的坐标begin，方阵的阶数size输出：数字旋转方阵1. 如果size=0，则算法结束；2. 如果size=1，则databeginbegin=number，算法结束；3. 初始化行、列下标i=begin，j=begin；4. 重复下述操作size-1次，填写区域A1. Dataij=number; number+; i+;数字旋转方阵数字旋转方阵第12页/共85页2021-11-17

9、135. 重复下述操作重复下述操作size-1次，填写区域次，填写区域B1. Dataij=number; number+; j+;6. 重复下述操作重复下述操作size-1次，填写区域次，填写区域C1. Dataij=number; number+; i-;7. 重复下述操作重复下述操作size-1次，填写区域次，填写区域D1. Dataij=number; number+; j-;8. 递归调用函数递归调用函数Full在在size-2阶方阵中左上角阶方阵中左上角begin+1处从数字处从数字number开始填数开始填数数字旋转方阵数字旋转方阵第13页/共85页2021-11-1714算法分

10、析算法分析填写填写n阶方阵，四个区域由阶方阵，四个区域由4个循环实现，每个循环个循环实现，每个循环均执行均执行n-1，然后执行递归调用，填写，然后执行递归调用，填写n-2阶方阵。递推式：阶方阵。递推式：数字旋转方阵数字旋转方阵 = =T(n-2)+4(n-1)当n=0时0nT1)(当n=1时当n1时设设n为偶数，用扩展递归技术解此递推式，得为偶数，用扩展递归技术解此递推式，得T(n)=T(n-2)+4(n-1)=T(n-4)+4(n-3)+4(n-1)=T(0)+4(n-5)+4(n-3)+4(n-1)=O(n2)第14页/共85页2021-11-1715本章要点本章要点4.1 概概 述述 4

11、.2 排序问题中的分治法排序问题中的分治法4.3 组合问题中的分治法组合问题中的分治法4.4 几何问题中的分治法几何问题中的分治法阅读材料阅读材料 递归函数的执行过程递归函数的执行过程第15页/共85页2021-11-1716排序问题中的分治法排序问题中的分治法4.2.1 4.2.1 归并排序归并排序4.2.2 4.2.2 快速排序快速排序第16页/共85页2021-11-1717n归并排序归并排序 二路归并排序的分治策略是：二路归并排序的分治策略是：（1）划分：划分：将待排序序列将待排序序列r1, r2, , rn划分为两个长划分为两个长度相等的子序列度相等的子序列r1, , rn/2和和r

12、n/21, , rn；（2）求解子问题：求解子问题：分别对这两个子序列进行排序，分别对这两个子序列进行排序，得到两个有序子序列；得到两个有序子序列；（3）合并：合并：将这两个有序子序列合并成一个有序将这两个有序子序列合并成一个有序序列。序列。4.2.1 4.2.1 归并排序归并排序第17页/共85页2021-11-1718 r1 rn/2 rn/21 rn 划分划分r1 rn/2 rn/21 rn 递归处理递归处理r1rn/2rn/21 r n 合并解合并解 4.2.1 4.2.1 归并排序归并排序第18页/共85页2021-11-1719想法想法 首先将序列划分为两个子序列，如子序列长度为首

13、先将序列划分为两个子序列，如子序列长度为1，则划分结束，否则继续执行划分，结果将具有则划分结束，否则继续执行划分，结果将具有n个待排序的个待排序的记录序列划分为记录序列划分为n个长度为个长度为1的有序子序列；然后两两合并，的有序子序列；然后两两合并，得到得到n/2个长度为个长度为2的有序子序列，再进行两两合并的有序子序列，再进行两两合并直到得直到得到一个长度为到一个长度为n的有序序列。的有序序列。4.2.1 4.2.1 归并排序归并排序第19页/共85页2021-11-1720 算法算法4.3归并排序归并排序 void MergeSort( (int r , int r1 , int s, i

14、nt t) ) /r 原序列数组，原序列数组，r1 归并后序列数组归并后序列数组 if ( (s= =t) ) r1s=rs; else m=( (s+t) )/2; Mergesort( (r, r1, s, m) ); /归并排序前半个子序列归并排序前半个子序列 Mergesort( (r, r1, m+1, t) ); /归并排序后半个子序列归并排序后半个子序列 Merge( (r1, r, s, m, t) ); /合并两个已排序的子序列合并两个已排序的子序列 4.2.1 4.2.1 归并排序归并排序rs,rm rm+1,rt第20页/共85页2021-11-1721算法算法4.4合并

15、有序子序列合并有序子序列 void Merge( (int r , int r1 , int s, int m, int t) ) / i,j分别指向两个待合并的有序子序列，分别指向两个待合并的有序子序列，k指向最终有序序列的当前记录指向最终有序序列的当前记录 i=s; j=m+1; k=s; while ( (i=m & j=t) ) if ( (ri=rj) ) r1k+=ri+; /取取ri和和rj中较小者放入中较小者放入r1k else r1k+=rj+; if ( (i=m) ) while ( (i=m) ) /若第一个子序列没处理完，则进行收尾处理若第一个子序列没处理完，

16、则进行收尾处理 r1k+=ri+; else while ( (j+=2)2(221)(nnnTnnT4.2.1 4.2.1 归并排序归并排序第22页/共85页2021-11-1723（2）求解子问题：分别对划分后的每一个子序列递归处理；（3）合并：由于对子序列r1 ri-1和ri+1 rn的排序是就地进行的，所以合并不需要执行任何操作。n快速排序的分治策略快速排序的分治策略（1）划分：划分：选定一个记录作为轴值，以轴值为基准将整个序选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列列划分为两个子序列r1 ri- -1和和ri+1 rn，前一个子序列前一个子序列中记录中记录的值均的值

17、均小于或等于轴值小于或等于轴值，后一个子序列后一个子序列中记录的值均中记录的值均大于或等大于或等于轴值于轴值；4.2.2 4.2.2 快速排序快速排序 r1 ri- -1 ri ri+1 rn 均均ri 轴值轴值 均均ri 位于最终位置位于最终位置 第23页/共85页2021-11-1724以第一个记录为轴值（可随机），对待排序序列进行划分的以第一个记录为轴值（可随机），对待排序序列进行划分的过程过程：（1）初始化：初始化：取第一个记录作为取第一个记录作为基准基准，设置两个参数，设置两个参数i，j分别用分别用来指示将要与基准记录进行比较的来指示将要与基准记录进行比较的左侧记录位置左侧记录位置和

18、和右侧记录位置右侧记录位置，也就是也就是本次划分的区间本次划分的区间；（2）右侧扫描过程：右侧扫描过程：将基准记录与将基准记录与j指向的记录进行比较，如果指向的记录进行比较，如果j指向记录的关键码大，则指向记录的关键码大，则j-,即前移一个记录位置。重复右侧扫即前移一个记录位置。重复右侧扫描过程，直到描过程，直到右侧的记录小右侧的记录小（即反序），若（即反序），若ij，则将基准记录则将基准记录与与j指向的记录进行交换指向的记录进行交换；（3）左侧扫描过程：左侧扫描过程：将基准记录与将基准记录与i指向的记录进行比较，如果指向的记录进行比较，如果i指向记录的关键码小，则指向记录的关键码小，则i+，

19、即后移一个记录位置。重复左侧，即后移一个记录位置。重复左侧扫描过程，直到扫描过程，直到左侧的记录大左侧的记录大（即反序），若（即反序），若ij，则将基准记则将基准记录与录与i指向的记录交换指向的记录交换；4.2.2 4.2.2 快速排序快速排序第24页/共85页2021-11-1725（4）重复重复（2）（）（3）步，直到）步，直到i与与j指向同一位置，即基准记指向同一位置，即基准记录最终的位置。录最终的位置。4.2.2 4.2.2 快速排序快速排序一次划分示例: （1）i=1, j=7，r1为基准记录; （2）rirj? i+: ri rj /左侧扫描 （4）i=j? if i=j, the

20、n 第一次划分基准记录位置找到第25页/共85页2021-11-1726jijjjiiiijjj一次划分示例第26页/共85页2021-11-1727算法算法4.5一次划分一次划分 int Partition( (int r , int first, int end) ) i=first; j=end; /初始化初始化 while ( (ij) ) while ( (ij & ri= rj) ) j-； /右侧扫描右侧扫描 if ( (ij) ) rirj; /将较小记录交换到前面将较小记录交换到前面 i+; while ( (ij & ri= rj) ) i+； /左侧扫描左

21、侧扫描 if ( (ij) ) rjri; /将较大记录交换到后面将较大记录交换到后面 j-; retutn i; / i为轴值记录的最终位置为轴值记录的最终位置 4.2.2 4.2.2 快速排序快速排序第27页/共85页2021-11-1728 以轴值以轴值(如此处为轴值：如此处为轴值：38) 为基准将待排序序列为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行划分为两个子序列后，对每一个子序列分别递归进行排序。排序。jiij4.2.2 4.2.2 快速排序快速排序第28页/共85页2021-11-1729算法算法4.6快速排序快速排序 void QuickSort(int r

22、 , int first, int end) if (first0) sum=aleft; else sum=0; else center=(left+right)/2; /划分划分 leftsum=MaxSum (a, left, center); /对应情况，递归求解对应情况，递归求解 rightsum=MaxSum (a, center+1, right); /对应情况，递归求解对应情况，递归求解最大子段和问题最大子段和问题 第39页/共85页2021-11-1740 s1=0; lefts=0; /以下对应情况，先求解以下对应情况，先求解s1 for (i=center; i=left

23、; i-) lefts+=ai; if (leftss1) s1=lefts; s2=0; rights=0; /再求解再求解s2 for (j=center+1; js2) s2=rights; sum=s1+s2; /计算情况的最大子段和计算情况的最大子段和 if (sumleftsum) sum=leftsum; /合并，在合并，在sum、leftsum和和rightsum中取较大者中取较大者 if (sum+=1)2(211)(nnnTnnT最大子段和问题最大子段和问题 第41页/共85页2021-11-1742组合问题中的分治法组合问题中的分治法 4.3.1 最大子段和问题最大子段和

24、问题 4.3.2 棋盘覆盖问题棋盘覆盖问题第42页/共85页2021-11-1743棋盘覆盖问题棋盘覆盖问题 在一个在一个2k2k （k0）个方格组成的棋盘中，恰）个方格组成的棋盘中，恰有一个方有一个方格与其他方格不同格与其他方格不同，称该方格为，称该方格为特殊方格特殊方格。特殊方格在棋盘中。特殊方格在棋盘中出现的位置有出现的位置有4k 种情形，因而有种情形，因而有4k种不同的棋盘，种不同的棋盘，(a)图是其中图是其中的一个。的一个。棋盘覆盖问题？棋盘覆盖问题？要求用图要求用图4.11（b）所示的）所示的4种不同形状的种不同形状的L型骨牌型骨牌覆盖给定棋覆盖给定棋盘上盘上除特殊方格除特殊方格以

25、外的所有方格，以外的所有方格，且任何且任何2个个L型骨牌不得重叠型骨牌不得重叠覆盖覆盖。(a) k=2时的一种棋盘时的一种棋盘 (b) 4种不同形状的种不同形状的L型骨牌型骨牌第43页/共85页2021-11-1744 分治法求解棋盘覆盖问题的分治法求解棋盘覆盖问题的技巧技巧在于在于划分棋盘划分棋盘，使划，使划分后的分后的子棋盘的大小相同子棋盘的大小相同，并且每个子棋盘均，并且每个子棋盘均包含一个特包含一个特殊方格殊方格，从而将，从而将原问题分解为规模较小的棋盘覆盖问题原问题分解为规模较小的棋盘覆盖问题。 k0时，可将时，可将2k2k的棋盘划分为的棋盘划分为4个个2k-12k-1的子棋盘，的子

26、棋盘，这样划分后，由于这样划分后，由于原棋盘只有一个特殊方格原棋盘只有一个特殊方格，所以，这，所以，这4个个子棋盘中只有一个子子棋盘中只有一个子棋盘包含该特殊方格棋盘包含该特殊方格，其余，其余3个子棋盘个子棋盘中没有特殊方格。为了将这中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，为特殊棋盘，以便采用递归方法求解，可以用一个可以用一个L型骨牌型骨牌覆盖这覆盖这3个较小棋盘的会合处个较小棋盘的会合处，从而将原问题转化为，从而将原问题转化为4个较个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至小规模的棋盘覆盖问题。递归地使用这种

27、划分策略，直至将棋盘分割为将棋盘分割为11的子棋盘。的子棋盘。 棋盘覆盖问题棋盘覆盖问题 第44页/共85页2021-11-17452k-12k-12k-12k-12k-12k-12k-12k-1(a)棋盘分割棋盘分割 (b) 构造相同子问题构造相同子问题棋盘覆盖问题棋盘覆盖问题 第45页/共85页2021-11-1746下面讨论棋盘覆盖问题中数据结构的设计。下面讨论棋盘覆盖问题中数据结构的设计。（1）棋盘：棋盘：可以用一个二维数组可以用一个二维数组boardsizesize表示一个棋表示一个棋盘，其中，盘，其中，size=2k。为了在递归处理的过程中使用同一个棋盘，。为了在递归处理的过程中使

28、用同一个棋盘，将数组将数组board设为全局变量设为全局变量；（2）子棋盘：子棋盘：整个棋盘用二维数组整个棋盘用二维数组boardsizesize表示，其表示，其中的子棋盘由棋盘左上角的下标中的子棋盘由棋盘左上角的下标tr、tc 和和 棋盘大小棋盘大小s 表示；表示；（3）特殊方格：特殊方格：用用boarddrdc表示特殊方格，表示特殊方格，dr和和dc是该特是该特殊方格在二维数组殊方格在二维数组board中的下标中的下标;（4） L型骨牌：型骨牌：一个一个2k2k的棋盘中有一个的棋盘中有一个特殊方格特殊方格，所以，所以，用到用到 L 型骨牌的个数型骨牌的个数为为(4k-1)/3，将所有，将所

29、有L型骨牌从型骨牌从 1 开始连续开始连续编号，用一个全局变量编号，用一个全局变量 t 表示。表示。 棋盘覆盖问题棋盘覆盖问题 第46页/共85页2021-11-1747dcdrtrtcsize棋盘覆盖问题中的数据结构棋盘覆盖问题中的数据结构棋盘覆盖问题棋盘覆盖问题 第47页/共85页2021-11-1748算法算法4.8棋盘覆盖棋盘覆盖void ChessBoard(int tr, int tc, int dr, int dc, int size)/ tr和和tc是子棋盘左上角的下标，是子棋盘左上角的下标，dr和和dc是特殊方格的下标，是特殊方格的下标，/ size是棋盘的大小，是棋盘的大小

30、，t 是骨牌编号，已初始化为是骨牌编号，已初始化为0 if (size = = 1) return; /棋盘只有一个方格且是特殊方格棋盘只有一个方格且是特殊方格 t+; / L型骨牌号型骨牌号 s = size/2; / 划分棋盘划分棋盘 / 覆盖左上角子棋盘覆盖左上角子棋盘 if (dr tr + s & dc tc + s) / 特殊方格在左上角子棋盘中特殊方格在左上角子棋盘中 ChessBoard (tr, tc, dr, dc, s); /递归处理子棋盘递归处理子棋盘 else / 用用 t 号号L型骨牌覆盖右下角，再递归处理子棋盘型骨牌覆盖右下角，再递归处理子棋盘 board

31、 tr + s - - 1tc + s - - 1 = t; ChessBoard (tr, tc, tr+s- -1, tc+s- -1, s); 棋盘覆盖问题棋盘覆盖问题 第48页/共85页2021-11-1749 / 覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在右上角子棋盘中 ChessBoard(tr, tc+s, dr, dc, s); /递归处理子棋盘 else / 用 t 号L型骨牌覆盖左下角，再递归处理子棋盘 board tr + s - 1tc + s = t; ChessBoard (tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下

32、角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在右下角子棋盘中 ChessBoard (tr+s, tc+s, dr, dc, s); /递归处理子棋盘 else / 用 t 号L型骨牌覆盖左上角，再递归处理子棋盘 board tr + s tc + s = t; ChessBoard (tr+s, tc+s, tr+s, tc+s, s); 棋盘覆盖问题棋盘覆盖问题 第50页/共85页2021-11-1751 设设T( (k) )是覆盖一个是覆盖一个2k2k棋盘所需时间，从算棋盘所需时间，从算法的划分策略可知，

33、法的划分策略可知，T( (k) )满足如下递推式：满足如下递推式： =+=00)1()1(4)1()(kkOkTOkT 解此递推式可得解此递推式可得T( (k) )=O( (4k) )。由于覆盖一个。由于覆盖一个2k2k棋盘所需的骨牌个数为棋盘所需的骨牌个数为(4k- -1)/ /3，所以，算，所以，算法法4 4.8是一个在渐进意义下的最优算法。是一个在渐进意义下的最优算法。 棋盘覆盖问题棋盘覆盖问题 第51页/共85页2021-11-1752本章要点本章要点4.1 概概 述述 4.2 排序问题中的分治法排序问题中的分治法4.3 组合问题中的分治法组合问题中的分治法4.4 几何问题中的分治法几

34、何问题中的分治法阅读材料阅读材料 递归函数的执行过程递归函数的执行过程第52页/共85页2021-11-17534.4 几何问题中的分治法几何问题中的分治法4.4.1 最近对问题最近对问题 4.4.2 凸包问题凸包问题第53页/共85页2021-11-1754最近对问题最近对问题 设设p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面是平面上上n个点构成的集合个点构成的集合S，最近对问题最近对问题就是找出就是找出集合集合S中距离最近的点对中距离最近的点对。 严格地讲，严格地讲，最接近点对最接近点对可能多于一对，简单可能多于一对，简单起见，只找出其中的一对作为问

35、题的解。起见，只找出其中的一对作为问题的解。 第54页/共85页2021-11-1755 用分治法解决最近对问题，很自然的想法就是将集合S 分成两个子集 S1和 S2，每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合 S 中最接近的两个点都在子集 S1或 S2中，则问题很容易解决，如果这两个点分别在 S1和 S2中，问题就比较复杂了。最近对问题最近对问题 第55页/共85页2021-11-1756为了使问题易于理解，先考虑为了使问题易于理解，先考虑一维一维的情形。的情形。此时，此时，S 中的点退化为中的点退化为 x 轴上的轴上的

36、n个点个点x1, x2, , xn。用。用x 轴上的轴上的某个点某个点 m 将将 S 划分为两个集合划分为两个集合S1和和S2，并且，并且S1和和S2含有点的个含有点的个数相同。递归地在数相同。递归地在S1和和S2上求出最接近点对上求出最接近点对 (p1, p2) 和和(q1, q2)，如果集合如果集合S中的最接近点对都在子集中的最接近点对都在子集S1或或S2中，则中，则d=min(p1, p2), (q1, q2)即为所求即为所求，如果集合，如果集合S中的最接近点对分别在中的最接近点对分别在S1和和S2中，则一定是中，则一定是(p3, q3)，其中，其中，p3是子集是子集S1中的最大值，中的

37、最大值，q3是子是子集集S2中的最小值。中的最小值。S1S2p2p1p3q3q1q2m最近对问题最近对问题 第56页/共85页2021-11-1757 按这种分治策略求解最近对问题的算法效率取按这种分治策略求解最近对问题的算法效率取决于决于划分点划分点m的选取的选取，一个基本的要求是要遵循平衡，一个基本的要求是要遵循平衡子问题的原则。如果选取子问题的原则。如果选取m=(maxS+minS)/2，则，则有可能因集合有可能因集合S中点分布的不均匀而造成子集中点分布的不均匀而造成子集S1和和S2的不平衡，的不平衡，如果用如果用S中各点坐标的中各点坐标的中位数中位数（即即S的中的中值值）作为分割点作为

38、分割点，则会得到一个，则会得到一个平衡的分割点平衡的分割点m，使，使得子集得子集S1和和S2中有中有个数大致相同个数大致相同的点。的点。最近对问题最近对问题 第57页/共85页2021-11-1758下面考虑下面考虑二维二维的情形，此时的情形，此时S中的点为平面上的点中的点为平面上的点。为了将平面上的点集为了将平面上的点集S 分割为点的个数大致相同的两个子集分割为点的个数大致相同的两个子集S1和和S2，选取垂直线，选取垂直线 x=m来作为分割线来作为分割线，其中，其中，m为为S中各点中各点x坐坐标的中位数标的中位数。由此将。由此将S分割为分割为S1=pS | xpm和和S2=qS | xqm。

39、递归地在递归地在S1和和S2上求解最近对问题上求解最近对问题，分别得到，分别得到S1中的最近中的最近距离距离d1和和S2中的最近距离中的最近距离d2，令令d=min(d1, d2)，若，若S的最近对的最近对(p, q)之间的之间的距离小于距离小于d，则，则p和和q必分属于必分属于S1和和S2，不妨设，不妨设pS1，qS2，则，则p和和q距直线距直线x=m的距离均小于的距离均小于d，所以，可以将求解，所以，可以将求解限制在以限制在以x=m为中心、宽度为为中心、宽度为2d的垂直带的垂直带P1和和P2中，垂直带之中，垂直带之外的任何点对之间的距离都一定大于外的任何点对之间的距离都一定大于d。 最近对

40、问题最近对问题 第58页/共85页2021-11-1759x=mddd2d1S1S2pq 最近对问题的分治思想最近对问题的分治思想P1P2S1=pS | xpmS2=qS | xqm最近对问题最近对问题 第59页/共85页2021-11-1760 x=mddp(a) 包含点包含点q的的d2d的矩形区域的矩形区域 (b) 最坏情况下需要检查的最坏情况下需要检查的6个点个点P1P22dx=mddpP1P22d 对于点对于点pP1，需要考察，需要考察P2中的各个点和点中的各个点和点p之间的距离之间的距离是否小于是否小于d，显然，显然，P2中这样点的中这样点的y轴坐标一定位于区间轴坐标一定位于区间y-

41、 -d, y+d之间，而且，之间，而且，这样的点不会超过这样的点不会超过6个个( (因因P2P2中点之间的距中点之间的距离不能小于离不能小于d)d)。故可将。故可将P1P1和和P2P2中的点按照中的点按照y y轴坐标值升序排轴坐标值升序排列，顺序处理列，顺序处理P1P1中的点中的点p p，同时在，同时在P2P2中取出中取出6 6个候选点，计算个候选点，计算它们与点它们与点p p之间的距离。之间的距离。 第60页/共85页2021-11-1761算法算法4.9分治法求解最近对问题分治法求解最近对问题输入：按输入：按x坐标升序排列的坐标升序排列的n(n2)个点的集合个点的集合S=(x1,y1),(

42、xn,yn)输出：最近点对的距离输出：最近点对的距离1.如果如果n=2，则返回，则返回(x1,y1)和和(x2,y2)间的距离，算法结束；间的距离，算法结束；2.划分：划分：m=S中各点中各点x坐标的中位数；坐标的中位数；3.d1=计算计算(x1,y1),(xm,ym)的最近对距离；的最近对距离；4.d2=计算计算(xm,ym),(xn,yn)的最近对距离；的最近对距离；5.d=mind1,d2;6.依次考察集合依次考察集合S中的点中的点p(x,y)，如果，如果(xxm 并且并且xxm-d)，则将点，则将点p放入集放入集合合P1中；如果中；如果(xxm 并且并且xxm+d)，则将点，则将点p放

43、入集合放入集合P2中；中；7.将集合将集合P1和和P2按按y坐标升序排列；坐标升序排列；8.对集合对集合P1中的每个点中的每个点p(x,y)，对集合，对集合P2在在y坐标区间坐标区间y-d,y+d内最多取出内最多取出6个候选点个候选点,计算与点计算与点p的最近距离的最近距离d3;9.返回返回mind, d3;最近对问题最近对问题 第61页/共85页2021-11-1762 应用分治法求解含有应用分治法求解含有n个点的最近对问题，其时个点的最近对问题，其时间复杂性可由下面的递推式表示：间复杂性可由下面的递推式表示：根据根据2.1.5节的主定理，可得节的主定理，可得T(n)=O(nlog2n)。最

44、近对问题最近对问题 12()2(/ 2)2nTnTnnn=+第62页/共85页2021-11-17634.4 几何问题中的分治法几何问题中的分治法4.4.1 最近对问题最近对问题 4.4.2 凸包问题凸包问题第63页/共85页2021-11-1764凸包问题凸包问题 问题问题 设设p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上是平面上n个点构个点构成的集合成的集合S，凸包问题是为集合凸包问题是为集合S S构造最小凸多边形构造最小凸多边形。 想法想法 划分：设划分：设S S中的点按照中的点按照x轴坐标升序排列，几何学中有轴坐标升序排列，几何学中有这样一个明

45、显的事实：最左边的点这样一个明显的事实：最左边的点p1和最右边的点和最右边的点pn一定是该一定是该集合的凸包集合的凸包顶点顶点（即极点）。设（即极点）。设p1pn是从是从p1到到pn的直线，这条的直线，这条直线把集合直线把集合S分成两个子集：分成两个子集：S1是位于直线左侧和直线上的点是位于直线左侧和直线上的点构成的集合，构成的集合，S2是位于直线右侧和直线上的点构成的集合。是位于直线右侧和直线上的点构成的集合。S1的凸包由下列线段构成：以的凸包由下列线段构成：以p1和和pn为端点的线段构成的下边界，为端点的线段构成的下边界，以及由多条线段构成的上边界，这条上边界称为以及由多条线段构成的上边界

46、，这条上边界称为上包上包。类似。类似地，地，S2中的多条线段构成的下边界称为中的多条线段构成的下边界称为下包下包。整个集合。整个集合S的凸的凸包是由上包和下包构成的。包是由上包和下包构成的。 第64页/共85页2021-11-1765p1pn 点集合点集合S的上包和下包的上包和下包S1S2凸包问题凸包问题 pmax第65页/共85页2021-11-1766p1pmaxpn求解子问题：首先找到求解子问题：首先找到S1中的顶点中的顶点pmax，它是距离直线，它是距离直线p1pn最最远的顶点，远的顶点，则三角形则三角形pmaxp1pn的面积最大的面积最大。S1中所有在直线中所有在直线 p1 pmax

47、左侧的点构成集合左侧的点构成集合S1,1，S1中所有在中所有在直线直线pn pmax右侧的点右侧的点构成集合构成集合S1,2，包含在三角形，包含在三角形pmaxp1pn之中的点可以不考虑了。之中的点可以不考虑了。递归地继续构造集合递归地继续构造集合S1,1的上包的上包和和集合集合S1,2的上包的上包，然后将求解，然后将求解过程中得到的过程中得到的所有最远距离的点连接起来所有最远距离的点连接起来，就可以得到集合，就可以得到集合S1的上包。的上包。凸包问题凸包问题 S1,1S1,2第66页/共85页2021-11-1767 接下来的问题是如何判断接下来的问题是如何判断一个点一个点是否在给定是否在给

48、定直线的左侧直线的左侧（或右侧）（或右侧）？几何学中有这样一个定理：如果？几何学中有这样一个定理：如果p1=(x1, y1), p2=(x2, y2), p3=(x3, y3)是平面上的任意三个点，则是平面上的任意三个点，则三角形三角形p1p2p3的面积的面积等于下面这个行列式的绝对值的一半：等于下面这个行列式的绝对值的一半： 当且仅当点当且仅当点p3=(x3, y3)位于直线位于直线p1p2的左侧时的左侧时，该式的符该式的符号为正号为正。可以在一个常数时间内检查一个点是否位于两个点。可以在一个常数时间内检查一个点是否位于两个点确定的直线的左侧，并且可以求得这个点到该直线的距离。确定的直线的左

49、侧，并且可以求得这个点到该直线的距离。311223321321332211111yxyxyxyxyxyxyxyxyx + + += =凸包问题凸包问题 第67页/共85页2021-11-1768算法算法4.10求直线求直线pipj的上包的上包输入：按输入：按x坐标升序排列的坐标升序排列的n(n2)个点的集合个点的集合S=(xi,yi),(xj,yj)输出：凸包的极点输出：凸包的极点1.如果如果n=2，则返回，则返回(xi,yi)和和(xj,yj) ，算法结束；，算法结束；2.maxd=0; max=i+1；3.循环变量循环变量k从从i+1j-1，依次对集合，依次对集合S中点中点pk(xk,yk

50、)执行下列操作；执行下列操作；3.1 如果点如果点pk在直线在直线pipj的上侧，则的上侧，则d=该点到直线的距离；该点到直线的距离；3.2 如果如果(dmaxd), 则则maxd=d，max=k;4.递归求解递归求解pipmax的上包和的上包和pmaxpj的上包的上包凸包问题凸包问题 第68页/共85页2021-11-1769 复杂度的讨论首先要对点集合S进行排序，设有n个点，则时间代价是O(nlog2n)。 最好情况：每次划分都得到规模大致相等的子集合，O(nlog2n) 最坏情况：每次划分只得到比上一次划分少一个元素的子集合（另一个为空），O(n2) 蛮力法：O(n3)凸包问题凸包问题

51、第69页/共85页2021-11-1770补充阅读材料：递归的概补充阅读材料：递归的概念念 直接或间接地调用自身的算法称为递归算法递归算法（Recursion）。用函数自身给出定义的函数称为递归函数递归函数。是一种描述问题和解决问题的基本方法。 由分治法产生的子问题分治法产生的子问题往往是原问题的较小模式原问题的较小模式，这就为使用递归技术提供了方便这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小而其规模却不断缩小，最终使子问题缩小到最终使子问题缩小到很容易直接求出其解很容易直接求出其解。这自然导致递归过程的产生。第70页/共85页2

52、021-11-1771递归的概念递归的概念 分治与递归像一对孪生兄弟分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法并由此产生许多高效算法。 递归有两个基本要素： 边界条件：确定递归到何时终止； 递归模式：大问题是如何分解为小问题的。也称为递归体。 递归的几个实例第71页/共85页2021-11-1772例例1 1 阶乘（阶乘（ Factorial ）函数）函数阶乘函数可递归地定义为：00)!1(1!=nnnnn边界条件递归方程递归的概念第72页/共85页2021-11-1773Factorial 递归算法递归算法 1 public static int facto

53、rial(int n)(int n) 2 3 if ( n=0 ) return 1( n=0 ) return 1; 4 return n*factorial (n-1); 5 递归的概念第73页/共85页递归函数的经典问题递归函数的经典问题汉诺塔问题汉诺塔问题在世界刚被创建的时候有一座钻石宝塔（塔在世界刚被创建的时候有一座钻石宝塔（塔A），），其上有其上有64个金碟。所有碟子按从大到小的次序从个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔宝塔（塔B和塔和塔C）。从世界创始之日起，婆罗）。从世界创始之日起，婆罗门

54、的牧师们就一直在试图把塔门的牧师们就一直在试图把塔A上的碟子移动到上的碟子移动到塔塔C上去，其间借助于塔上去，其间借助于塔B的帮助。每次只能移的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末它小的碟子上面。当牧师们完成任务时，世界末日也就到了。日也就到了。 第74页/共85页汉诺塔问题可以通过以下三个步骤实现：（1）将塔A上的n-1个碟子借助塔C先移到塔B上。（2）把塔A上剩下的一个碟子移到塔C上。（3）将n-1个碟子从塔B借助塔A移到塔C上。 显然，这是一个递归求解的过程递归的概念第75页/共85

55、页第76页/共85页算法4.2汉诺塔算法 1 void Hanoi( (int n, char A, char B, char C) ) /第一列为语句行号第一列为语句行号 2 3 if ( (n=1) ) Move( (A, C) ); /Move是一个抽象操作，表示将碟子从是一个抽象操作，表示将碟子从A移到移到C上上 4 else 5 Hanoi( (n- -1, A, C, B) ); 6 Move( (A, C) ); 7 Hanoi( (n- -1, B, A, C) ); 8 9 第77页/共85页4.2.2 递归函数的运行轨迹递归函数的运行轨迹 在递归函数中，调用函数和被调用函数

56、是同一在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第把调用递归函数的主函数称为第0 0层，进入函数后，层，进入函数后，首次递归调用自身称为第首次递归调用自身称为第1层调用；从第层调用；从第i层递归调层递归调用自身称为第用自身称为第i+1层。反之，退出第层。反之，退出第i+1层调用应该层调用应该返回第返回第i层。采用图示方法描述递归函数的运行轨层。采用图示方法描述递归函数的运行轨迹，从中可较直观地了解到各调用层次及其执行情迹，从中可较直观地了解到各调用层次及其执行情况。况。第78页/共85页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)结束结束第79页/共85页