算法-分治法课件.ppt

《算法-分治法课件.ppt》由会员分享，可在线阅读，更多相关《算法-分治法课件.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/1/25分治法第第4章章分治法分治法4.1 概概 述述 4.2 排序问题中的分治法排序问题中的分治法4.3 组合问题中的分治法组合问题中的分治法4.4 几何问题中的分治法几何问题中的分治法 分治法是最著名的算法设计技术。分治法是最著名的算法设计技术。1/562023/1/25分治法4.1 概概 述述 4.1.1分治法的设计思想分治法的设计思想4.1.2数字旋转方阵数字旋转方阵2/562023/1/25分治法 将一个难以直接解决的大问题，划分成一些规模将一个难以直接解决的大问题，划分成一些规模较小的子问题，分别求解各个子问题，再合并子问较小的子问题，分别求解各个子问题，再合并子问题的解

2、得到原问题的解。题的解得到原问题的解。4.1.1分治法的设计思想分治法的设计思想如果子问题的规模仍然不够小，可继续分解下去。如果子问题的规模仍然不够小，可继续分解下去。3/562023/1/25分治法分治法的求解过程：分分治法的求解过程：分-治治-合合 （1 1）划分划分：把规模为：把规模为n n的原问题划分为的原问题划分为k k个规模较个规模较小的子问题，并尽量使这小的子问题，并尽量使这k k个子问题的规模大致相同。个子问题的规模大致相同。（2 2）求解子问题求解子问题：各子问题的解法与原问题的解：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题。法通常是相同的，可以

3、用递归的方法求解各个子问题。（3 3）合并合并：把各个子问题的解合并起来，分治算法：把各个子问题的解合并起来，分治算法的有效性很大程度上依赖于合并的实现。的有效性很大程度上依赖于合并的实现。4/562023/1/25分治法2.独立子问题独立子问题：各子问题之间相互独立。：各子问题之间相互独立。1.平衡子问题平衡子问题：最好使子问题的规模大：最好使子问题的规模大致相同。致相同。启发式规则：启发式规则：5/562023/1/25分治法子问题子问题1的规模是的规模是n/2子问题子问题1的解的解子问题子问题2的解的解子问题子问题2的规模是的规模是n/2原问题的解原问题的解原问题原问题的规模是的规模是n

4、分治法的典型情况分治法的典型情况6/562023/1/25分治法例：计算例：计算an，应用分治技术得到如下计算方法：，应用分治技术得到如下计算方法：3432328131319313193333分解问题分解问题求解每个子问题求解每个子问题合并子问题的解合并子问题的解v 不是所有的分治法都比简单的蛮力法更有效。不是所有的分治法都比简单的蛮力法更有效。分析时间性能 =1122naanaannn如果如果如果如果7/562023/1/25分治法4.1.2数字旋转方阵数字旋转方阵问题：问题：输输出出N N(1 N 10)数字旋数字旋转转方方阵阵。120 19 18 17 16221 32 31 30 15

5、322 33 36 29 14423 34 35 28 13524 25 26 27 1267 8 9 10 116 6的旋转方阵的旋转方阵8/562023/1/25分治法4.2排序问题中的分治法排序问题中的分治法4.2.1 4.2.1 归并排序归并排序4.2.2 4.2.2 快速排序快速排序92023/1/25分治法4.3.1归并排序归并排序二路归并排序的分治策略是：二路归并排序的分治策略是：（1）划划分分：将将待待排排序序序序列列r1,r2,rn划划分分为为两两个个长度相等的子序列长度相等的子序列r1,rn/2和和rn/21,rn；（2）求求解解子子问问题题：分分别别对对这这两两个个子子序

6、序列列进进行行排排序序，得到两个有序子序列；得到两个有序子序列；（3）合合并并：将将这这两两个个有有序序子子序序列列合合并并成成一一个个有有序序序列。序列。10/562023/1/25分治法 r1 rn/2rn/21rn划分划分r1rn/2rn/21rn递归处理递归处理r1rn/2rn/21r n合并解合并解举举例：例：8326715411/562023/1/25分治法算法算法4.3归并排序归并排序voidMergeSort(intr,ints,intt)intm,r11000;if(s=t)return;elsem=(s+t)/2;Mergesort(r,s,m);/归并排序前半个子序列归并

7、排序前半个子序列Mergesort(r,m+1,t);/归并排序后半个子序列归并排序后半个子序列Merge(r,r1,s,m,t);/合并两个已排序的子序列合并两个已排序的子序列for(inti=s;i+=1)2(211)(nnnTnnT13/562023/1/25分治法算法算法4.4合并有序子序列合并有序子序列voidMerge(intr,intr1,ints,intm,intt)i=s;j=m+1;k=s;while(i=m&j=t)if(ri=rj)r1k+=ri+;/取取ri和和rj中较小者放入中较小者放入r1kelser1k+=rj+;if(i=m)while(i=m)/若第一个子序

8、列没处理完，则进行收尾处理若第一个子序列没处理完，则进行收尾处理r1k+=ri+;elsewhile(j=t)/若第二个子序列没处理完，则进行收尾处理若第二个子序列没处理完，则进行收尾处理r1k+=rj+;14/562023/1/25分治法4.3.2快速排序快速排序（2）求解子问题求解子问题：分别对划分后的每一个子序列递：分别对划分后的每一个子序列递归处理；归处理；（3）合并合并：由于对子序列：由于对子序列r1ri-1和和ri+1rn的排序的排序是就地进行的，所以合并不需要执行任何操作。是就地进行的，所以合并不需要执行任何操作。快速排序的分治策略是：快速排序的分治策略是：（1）划划分分：选选定

9、定一一个个记记录录作作为为轴轴值值，以以轴轴值值为为基基准准将整个序列划分为两个子序列；将整个序列划分为两个子序列；15/562023/1/25分治法r1ri-1 ri ri+1rn 均均ri 轴值轴值均均ri 位于最终位置位于最终位置v归并排序按照记录在序列中的位置对序列进行划分，归并排序按照记录在序列中的位置对序列进行划分，v快速排序按照记录的值对序列进行划分。快速排序按照记录的值对序列进行划分。16/562023/1/25分治法以第一个记录作为轴值，对待排序序列进行划分的过程为：以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初始化初始化：取第一个记录作为基准，设置两个参数：取

10、第一个记录作为基准，设置两个参数i，j；（2 2）右侧扫描过程右侧扫描过程：（3 3）左侧扫描过程左侧扫描过程：（4 4）重复重复（2 2）（）（3 3）步，直到）步，直到i i与与j j指向同一位置，即基准记指向同一位置，即基准记录最终的位置。录最终的位置。172023/1/25分治法1313656527275050383849495555jijj1313656527275050383849495555jiii1313656527275050383849495555ijjj一次划分示例一次划分示例一次划分示例一次划分示例182023/1/25分治法算法算法4.5一次划分一次划分intPart

11、ition(intr,intfirst,intend)i=first;j=end;/初始化初始化while(ij)while(ij&ri=rj)j-；/右侧扫描右侧扫描if(ij)rirj;/将较小记录交换到前面将较小记录交换到前面i+;while(ij&ri=rj)i+；/左侧扫描左侧扫描if(ij)rjri;/将较大记录交换到后面将较大记录交换到后面j-;retutni;/i为轴值记录的最终位置为轴值记录的最终位置192023/1/25分治法以以轴轴值值为为基基准准将将待待排排序序序序列列划划分分为为两两个个子子序序列后，对每一个子序列分别递归进行排序。列后，对每一个子序列分别递归进行排序

12、。131327275050383849495555jiij13136565272750503838494955556565202023/1/25分治法算法算法4.6快速排序快速排序voidQuickSort(intr,intfirst,intend)if(first0)sum=aleft;elsesum=0;elsecenter=(left+right)/2;/划分划分leftsum=MaxSum(a,left,center);/对应情况对应情况，递归求解，递归求解rightsum=MaxSum(a,center+1,right);/对应情况对应情况，递归求解，递归求解302023/1/25分

13、治法s1=0;lefts=0;/以下对应情况以下对应情况，先求解，先求解s1for(i=center;i=left;i-)lefts+=ai;if(leftss1)s1=lefts;s2=0;rights=0;/再求解再求解s2for(j=center+1;js2)s2=rights;sum=s1+s2;/计算情况计算情况的最大子段和的最大子段和if(sumleftsum)sum=leftsum;/合并，在合并，在sum、leftsum和和rightsum中取较大者中取较大者if(sum0 k0时，可将时，可将2k2k2k2k的棋盘划分为的棋盘划分为4 4个个2k-12k-12k-12k-1的

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

15、这种划分策略，直至将棋盘分割为题。递归地使用这种划分策略，直至将棋盘分割为1 11 1的子的子棋盘。棋盘。342023/1/25分治法2k-12k-12k-12k-12k-12k-12k-12k-1(a)棋盘分割棋盘分割(b)构造相同子问题构造相同子问题35/562023/1/25分治法 设设T(k)是覆盖一个是覆盖一个2k2k棋盘所需时间，从算棋盘所需时间，从算法的划分策略可知，法的划分策略可知，T(k)满足如下递推式：满足如下递推式：解此递推式可得解此递推式可得T(k)=O(4k)。由于覆盖一个。由于覆盖一个2k2k棋盘所需的骨牌个数为棋盘所需的骨牌个数为(4k-1)/3，所以，算，所以，

16、算法法4.8是一个在渐进意义下的最优算法。是一个在渐进意义下的最优算法。362023/1/25分治法补充：补充：循环赛日程安排问题循环赛日程安排问题设设有有n=2k个个选选手手要要进进行行网网球球循循环环赛赛，要要求求设设计计一个满足以下要求的比赛日程表：一个满足以下要求的比赛日程表：（1）每个选手必须与其他）每个选手必须与其他n-1个选手各赛一次；个选手各赛一次；（2）每个选手一天只能赛一次。）每个选手一天只能赛一次。按此要求，可将比赛日程表设计成一个按此要求，可将比赛日程表设计成一个 n n 行行n n-1-1列的二维表，其中，第列的二维表，其中，第 i i 行第行第 j j 列表示和第列

17、表示和第 i i 个选手在第个选手在第 j j 天比赛的选手。天比赛的选手。37/562023/1/25分治法n按照分治的策略，可将所有参赛的选手分为两按照分治的策略，可将所有参赛的选手分为两部分，部分，n2k个选手的比赛日程表就可以通过个选手的比赛日程表就可以通过为为n/22k-1个选手设计的比赛日程表来决定。个选手设计的比赛日程表来决定。n 递归地执行这种分割，直到只剩下递归地执行这种分割，直到只剩下2个选手时，个选手时，比赛日程表的制定就变得很简单：只要让这比赛日程表的制定就变得很简单：只要让这2个选手进行比赛就可以了。个选手进行比赛就可以了。38/562023/1/25分治法 显然，这

18、个求解过程是自底向上的迭代过程。显然，这个求解过程是自底向上的迭代过程。具有多个选手的情况可以依此类推。具有多个选手的情况可以依此类推。(b)2k(k=2)个选手比赛个选手比赛(c)2k(k=3)个选手比赛个选手比赛加加4加加2(a)2k(k=1)个选手比赛个选手比赛122112213443344312211234214334124321567865877856876556786587785687651234214334124321392023/1/25分治法4.4 几何问题中的分治法几何问题中的分治法4.4.1最近对问题最近对问题4.4.2 凸包问题（略）凸包问题（略）402023/1/25

19、分治法4.4.1最近对问题最近对问题设设p1=(x1,y1),p2=(x2,y2),pn=(xn,yn)是是平平面面上上n个个点点构构成成的的集集合合S，最最近近对对问问题题就就是是找找出出集集合合S中距离最近的点对。中距离最近的点对。蛮力法求解时间性能为蛮力法求解时间性能为O(n2)。一维情况下排序。一维情况下排序后求解，效率可提高到后求解，效率可提高到O(nlogn)。二维情况？。二维情况？最接近点对可能多于一对。为简单起见，只找最接近点对可能多于一对。为简单起见，只找出其中的一对作为问题的解。出其中的一对作为问题的解。41/562023/1/25分治法划分：划分：将集合将集合S分成两个子

20、集分成两个子集 S1和和 S2，每个子集，每个子集中有中有n/2个点。个点。在每个子集中递归地求其最接近的点对，在求在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步分两种情况，出每个子集的最接近点对后，在合并步分两种情况，1 集合集合 S 中最接近的两个点都在子集中最接近的两个点都在子集 S1或或 S2中，中，则问题很容易解决，则问题很容易解决，2 这两个点分别在这两个点分别在 S1和和 S2中，中，问题比较复杂。问题比较复杂。42/562023/1/25分治法求解子问题：求解子问题：先考虑先考虑一维一维的情形。的情形。S中的点退化为中的点退化为x轴上的轴上的n个点个

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

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

23、使得子集得子集S1和和S2中有个数大致相同的点。中有个数大致相同的点。45/562023/1/25分治法下面考虑下面考虑二维二维的情形，此时的情形，此时S中的点为平面上的点。中的点为平面上的点。选取垂直线选取垂直线x=m来作为分割线，其中，来作为分割线，其中，m为为S中各点中各点x坐标的中位数。由此将坐标的中位数。由此将S分割为两个子集分割为两个子集S1=pS|xpm和和S2=qS|xqm。此时，。此时，S1和和S2包含点包含点的个数大致相同。的个数大致相同。462023/1/25分治法 递归地在递归地在S1和和S2上求解最近对问题，分别得到上求解最近对问题，分别得到S1中的最近距离中的最近距

24、离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。472023/1/25分治法x=mddd2d1S1S2pq最近对问题的分治思想最近对问题的分治思想P1P2S1=pS|

25、xpmS2=qS|xqm482023/1/25分治法x=mddp(a)包含点包含点q的的d2d的矩形区域的矩形区域(b)最坏情况下需要检查的最坏情况下需要检查的6个点个点P1P22dx=mddpP1P22d 对于点对于点pP1，需要考察，需要考察P2中的各个点和点中的各个点和点p之间的距之间的距离是否小于离是否小于d，显然，显然，P2中这样点的中这样点的y轴坐标一定位于区间轴坐标一定位于区间y-d,y+d之间，而且，这样的点不会超过之间，而且，这样的点不会超过6个。个。492023/1/25分治法 应应用用分分治治法法求求解解含含有有n个个点点的的最最近近对对问问题题，其时间复杂性可由下面的递

26、推式表示：其时间复杂性可由下面的递推式表示：分分解解合合并并子子问问题题的的解解的的时时间间f(n)O(n)，从而可得从而可得T(n)=O(nlog2n)。50/562023/1/25分治法阅读材料阅读材料递归函数的执行过程递归函数的执行过程递归的定义递归的定义递归函数的运行轨迹递归函数的运行轨迹递归函数的内部执行过程递归函数的内部执行过程51/562023/1/25分治法递归的定义递归的定义 递归（递归（RecursionRecursion）就是子程序（或函数）直）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解

27、决问题的基本方法。是一种描述问题和解决问题的基本方法。递归的两个基本要素：递归的两个基本要素：边界条件边界条件：确定递归到何时终止；：确定递归到何时终止；递归模式递归模式：大问题是如何分解为小问题的。：大问题是如何分解为小问题的。递归通常用来解决结构自相似的问题。递归通常用来解决结构自相似的问题。52/562023/1/25分治法递归函数的运行轨迹递归函数的运行轨迹 在在递递归归函函数数中中，调调用用函函数数和和被被调调用用函函数数是是同同一一个个函函数数，需需要要注注意意的的是是递递归归函函数数的的调调用用层层次次，如如果果把把调调用用递递归归函函数数的的主主函函数数称称为为第第0 0层层，

28、进进入入函函数数后后，首首次次递递归归调调用用自自身身称称为为第第1层层调调用用；从从第第i层层递递归归调调用自身称为第用自身称为第i+1层。层。反反之之，退退出出第第i+1i+1层层调调用用应应该该返返回回第第i i层层。采采用用图图示示方方法法描描述述递递归归函函数数的的运运行行轨轨迹迹，从从中中可可较较直直观观地了解到各调用层次及其执行情况。地了解到各调用层次及其执行情况。53/562023/1/25分治法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)Hani

29、o(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)结束结束 542023/1/25分治法 递归函数的内部执行过程p一个递归函数的调用过程类似于多个函数的一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是嵌套调用，只不过调用函数和被调用函数是同一个函数。同一个函数。p为了保证递归函数的正确执行，系统需设立为了保证递归函

30、数的正确执行，系统需设立一个工作栈。一个工作栈。552023/1/25分治法 u递归算法递归算法结构清晰，可读性强结构清晰，可读性强，而且容易用数，而且容易用数学归纳法来证明算法的正确性，因此，它为设学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。中的一种强有力的工具。u递归算法是一种自身调用自身的算法，随着递递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的归调用时的辅助操作增多，因此，递归算法的运行效率较低运行效率较低。递归算法的特点递归算法的特点56