算法 分治法课件.ppt

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

1、2023/1/17,分治法,第4章 分治法,4.1 概 述,4.2 排序问题中的分治法,4.3 组合问题中的分治法,4.4 几何问题中的分治法,分治法是最著名的算法设计技术。,1/56,2023/1/17,分治法,4.1 概 述,4.1.1 分治法的设计思想,4.1.2 数字旋转方阵,2/56,2023/1/17,分治法,将一个难以直接解决的大问题，划分成一些规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。,4.1.1 分治法的设计思想,如果子问题的规模仍然不够小，可继续分解下去。,3/56,2023/1/17,分治法,分治法的求解过程：分-治-合,（1）划分：把规模为n

2、的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。,（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题。,（3）合并：把各个子问题的解合并起来，分治算法的有效性很大程度上依赖于合并的实现。,4/56,2023/1/17,分治法,2.独立子问题：各子问题之间相互独立。,1.平衡子问题：最好使子问题的规模大致相同。,启发式规则：,5/56,2023/1/17,分治法,分治法的典型情况,6/56,2023/1/17,分治法,例：计算an，应用分治技术得到如下计算方法：,不是所有的分治法都比简单的蛮力法更有效。,分析时间性能,7/56,20

3、23/1/17,分治法,4.1.2 数字旋转方阵,问题：输出NN(1N10)数字旋转方阵。,20 19 18 17 1621 32 31 30 1522 33 36 29 1423 34 35 28 1324 25 26 27 127 8 9 10 11,66的旋转方阵,8/56,2023/1/17,分治法,4.2 排序问题中的分治法,4.2.1 归并排序,4.2.2 快速排序,9,2023/1/17,分治法,4.3.1 归并排序,二路归并排序的分治策略是：（1）划分：将待排序序列r1,r2,rn划分为两个长度相等的子序列r1,rn/2和rn/21,rn；（2）求解子问题：分别对这两个子序列进

4、行排序，得到两个有序子序列；（3）合并：将这两个有序子序列合并成一个有序序列。,10/56,2023/1/17,分治法,举例：8 3 2 6 7 1 5 4,11/56,2023/1/17,分治法,12/56,2023/1/17,分治法,二路归并排序的合并步的时间复杂性为O(n)，所以，二路归并排序算法存在如下递推式：,可得二路归并排序的时间代价是O(nlog2n)。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性为O(n)。,13/56,2023/1/17,分治法,14/56,2023/1/17,分治法,4.3.2 快速排序,（2）求解子问题：分别对划分后的每一

5、个子序列递归处理；（3）合并：由于对子序列r1 ri-1和ri+1 rn的排序是就地进行的，所以合并不需要执行任何操作。,快速排序的分治策略是：（1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列；,15/56,2023/1/17,分治法,归并排序按照记录在序列中的位置对序列进行划分，快速排序按照记录的值对序列进行划分。,16/56,2023/1/17,分治法,以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初始化：取第一个记录作为基准，设置两个参数i，j；,（2）右侧扫描过程：,（3）左侧扫描过程：,（4）重复（2）（3）步，直到i与j指向同一位置，即基准记录最

6、终的位置。,17,2023/1/17,分治法,一次划分示例,18,2023/1/17,分治法,19,2023/1/17,分治法,以轴值为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行排序。,13,27,50,38,49,55,j,i,i,j,13,65,27,50,38,49,55,65,20,2023/1/17,分治法,21,2023/1/17,分治法,T(n)=2 T(n/2)n=2(2T(n/4)n/2)n4T(n/4)2n=4(2T(n/8)n/4)2n8T(n/8)3n=nT(1)nlog2nO(nlog2n)因此，时间复杂度为O(nlog2n)。,最好情况:每次划分

7、后把待划分区间划分为长度相等的两个子序列。在具有n个记录的序列中，一次划分需要对整个待划分序列扫描一遍，则所需时间为O(n)。设T(n)是对n个记录的序列进行排序的时间，则有：,22,2023/1/17,分治法,因此，时间复杂度为O(n2)。,最坏情况：待排序记录序列正序或逆序。此时，必须经过n-1次递归调用，而且第i趟划分需要经过n-i次关键码的比较，因此，总的比较次数为：,23,2023/1/17,分治法,平均情况：设基准记录的关键码第k小(1kn)，则有：,这是快速排序的平均时间性能，可以用归纳法证明，其数量级也为O(nlog2n)。,快速排序的空间复杂性如何?,24/56,2023/1

8、/17,分治法,4.3 组合问题中的分治法,4.3.1 最大子段和问题,4.3.2 棋盘覆盖问题,补充：循环赛日程安排问题,25/56,2023/1/17,分治法,给定由n个整数组成的序列(a1,a2,an)，最大子段和问题要求该序列形如 的最大值(1ijn)。当序列中所有整数均为负整数时，其最大子段和为0。如，序列(-20,11,-4,13,-5,-2)的最大子段和为：,4.3.1 最大子段和问题,26/56,2023/1/17,分治法,最大子段和问题的分治策略是：（1）划分：按照平衡子问题的原则，将序列(a1,a2,an)划分成长度相同的两个子序列(a1,a)和(a 1,an)，则：,先考

9、虑最大子段和问题的简单算法,27/56,2023/1/17,分治法,a1,an的最大子段和a1,a 的最大子段和；a1,an的最大子段和a 1,an的最大子段和；a1,an的最大子段和，且,（2）求解子问题：对于划分阶段的情况和可递归求解，情况需要分别计算，,，则s1+s2为情况的最大子段和。,（3）合并：比较在划分阶段的三种情况下的最大子段和，取三者之中的较大者为原问题的解。,28,2023/1/17,分治法,29,2023/1/17,分治法,30,2023/1/17,分治法,s1=0;lefts=0;/以下对应情况，先求解s1 for(i=center;i=left;i-)lefts+=a

10、i;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(sumrightsum)sum=rightsum;return sum;,31/56,2023/1/17,分治法,算法的时间性能：对应划分得到的情况和，需要分别递归求解，对应情况，两个并列for循环的时间复杂性是O(n)，所以，存在如下递推式：,从而可得算法4.7的时间复杂性为O(nlog2

11、n)。,32,2023/1/17,分治法,4.3.2 棋盘覆盖问题,在一个2k2k（k0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。棋盘覆盖问题要求用图（b）所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,(a)k=2时的一种棋盘(b)4种不同形状的L型骨牌,33,2023/1/17,分治法,分治法求解棋盘覆盖问题的技巧在于划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。,k0时，可将2k2k的棋盘划分为4个2k-12k-1的子棋盘，这样划分后，由于

12、原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。,为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为11的子棋盘。,34,2023/1/17,分治法,(a)棋盘分割(b)构造相同子问题,35/56,2023/1/17,分治法,设T(k)是覆盖一个2k2k棋盘所需时间，从算法的划分策略可知，T(k)满足如下递推式：,解此递推式可得T(k)=O(4k)。由于覆盖一个2k2k棋盘所需的骨牌个数为

13、(4k-1)/3，所以，算法4.8是一个在渐进意义下的最优算法。,36,2023/1/17,分治法,补充：循环赛日程安排问题,设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能赛一次。,按此要求，可将比赛日程表设计成一个 n 行n-1列的二维表，其中，第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。,37/56,2023/1/17,分治法,按照分治的策略，可将所有参赛的选手分为两部分，n2k个选手的比赛日程表就可以通过为n/22k-1个选手设计的比赛日程表来决定。递归地执行这种分割，直到

14、只剩下2个选手时，比赛日程表的制定就变得很简单：只要让这2个选手进行比赛就可以了。,38/56,2023/1/17,分治法,显然，这个求解过程是自底向上的迭代过程。具有多个选手的情况可以依此类推。,(b)2k(k=2)个选手比赛(c)2k(k=3)个选手比赛,加4,加2,(a)2k(k=1)个选手比赛,39,2023/1/17,分治法,4.4 几何问题中的分治法,4.4.1 最近对问题,4.4.2 凸包问题（略）,40,2023/1/17,分治法,4.4.1 最近对问题,设p1=(x1,y1),p2=(x2,y2),pn=(xn,yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离

15、最近的点对。,蛮力法求解时间性能为O(n2)。一维情况下排序后求解，效率可提高到O(nlogn)。二维情况？,最接近点对可能多于一对。为简单起见，只找出其中的一对作为问题的解。,41/56,2023/1/17,分治法,划分：将集合S分成两个子集 S1和 S2，每个子集中有n/2个点。,在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步分两种情况，1 集合 S 中最接近的两个点都在子集 S1或 S2中，则问题很容易解决，2 这两个点分别在 S1和 S2中，问题比较复杂。,42/56,2023/1/17,分治法,求解子问题：先考虑一维的情形。,S中的点退化为x轴上的n个点x

16、1,x2,xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数相同。,43,2023/1/17,分治法,递归地在S1和S2上求出最接近点对(p1,p2)和(q1,q2)，如果集合S中的最接近点对都在子集S1或S2中，则d=min(p1,p2),(q1,q2)即为所求,如果集合S中的最接近点对分别在S1和S2中，则一定是(p3,q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。,44,2023/1/17,分治法,按这种分治策略求解最近对问题的算法效率取决于划分点m的选取，一个基本的要求是要遵循平衡子问题的原则。,如果选取m=(maxS+minS)/2，

17、则有可能因集合S中点分布的不均匀而造成子集S1和S2的不平衡，如果用S中各点坐标的中位数（即S的中值）作为分割点，则会得到一个平衡的分割点m，使得子集S1和S2中有个数大致相同的点。,45/56,2023/1/17,分治法,下面考虑二维的情形，此时S中的点为平面上的点。,选取垂直线x=m来作为分割线，其中，m为S中各点x坐标的中位数。由此将S分割为两个子集S1=pS|xpm和S2=qS|xqm。此时，S1和S2包含点的个数大致相同。,46,2023/1/17,分治法,递归地在S1和S2上求解最近对问题，分别得到S1中的最近距离d1和S2中的最近距离d2，令d=min(d1,d2)，若S的最近对

18、(p,q)之间的距离小于d，则p和q必分属于S1和S2。,不妨设pS1，qS2，则p和q距直线x=m的距离均小于d，所以，可以将求解限制在以x=m为中心、宽度为2d的垂直带P1和P2中，垂直带之外的任何点对之间的距离都一定大于d。,47,2023/1/17,分治法,S1=pS|xpm,S2=qS|xqm,48,2023/1/17,分治法,对于点pP1，需要考察P2中的各个点和点p之间的距离是否小于d，显然，P2中这样点的y轴坐标一定位于区间y-d,y+d之间，而且，这样的点不会超过6个。,49,2023/1/17,分治法,应用分治法求解含有n个点的最近对问题，其时间复杂性可由下面的递推式表示：

19、,分解合并子问题的解的时间f(n)O(n)，从而可得T(n)=O(nlog2n)。,50/56,2023/1/17,分治法,阅读材料 递归函数的执行过程,递归的定义,递归函数的运行轨迹,递归函数的内部执行过程,51/56,2023/1/17,分治法,递归的定义,递归（Recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。,递归的两个基本要素：边界条件：确定递归到何时终止；递归模式：大问题是如何分解为小问题的。,递归通常用来解决结构自相似的问题。,52/56,2023/1/17,分治法,递归函数的运行轨迹,在递归函数中，调用函数

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

21、Move(B,C),Hanio(1,A,B,C),Move(A,C),Move(B,A),54,2023/1/17,分治法,递归函数的内部执行过程,一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。,55,2023/1/17,分治法,递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。,递归算法的特点,56,