第4章分治法4.1概述4.2递归4.3排序问题中的分治法4.4组合问题中的分治法4.5几何问题中的分治法4.1概述4.1.1分治法的
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
思想
教师资格思想品德鉴定表下载浅论红楼梦的主题思想员工思想动态调查问卷论语教育思想学生思想教育讲话稿
4.1.2分治法的求解过程将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。4.1.1分治法的设计思想更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。2.独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。1.平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。启发式规则：子问题1的规模是n/2子问题1的解子问题2的解子问题2的规模是n/2原问题的解原问题的规模是n分治法的典型情况4.1.2分治法的求解过程一般来说，分治法的求解过程由以下三个阶段组成：（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。例：计算an，应用分治技术得到如下计算方法：3432328131319313193333分解问题求解每个子问题合并子问题的解不是所有的分治法都比简单的蛮力法更有效。分析时间性能ëûéùîíì>´==1122naanaannn如果如果4.2递归4.2.1递归的定义4.2.2递归函数的运行轨迹4.2.3递归函数的内部执行过程4.2.1递归的定义递归（Recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。递归的两个基本要素：⑴边界条件：确定递归到何时终止；⑵递归模式：大问题是如何分解为小问题的。递归通常用来解决结构自相似的问题。在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。递归函数的经典问题——汉诺塔问题三个步骤实现（1）将塔A上的n-1个碟子借助塔C先移到塔B上。（2）把塔A上剩下的一个碟子移到塔C上。（3）将n-1个碟子从塔B借助塔A移到塔C上。显然，这是一个递归求解的过程算法4.2——汉诺塔算法1voidHanoi(intn,charA,charB,charC)//第一列为语句行号2{3if(n==1)Move(A,C);//Move是一个抽象操作，表示将碟子从A移到C上4else{5Hanoi(n-1,A,C,B);6Move(A,C);7Hanoi(n-1,B,A,C);8}9}4.2.2递归函数的运行轨迹在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。采用图示方法描述递归函数的运行轨迹，从中可较直观地了解到各调用层次及其执行情况。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)结束4.2.3递归函数的内部执行过程一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：（1）运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；（3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。汉诺塔算法在执行过程中，工作栈的变化下图所示，其中栈元素的结构为（返回地址，n值，A值，B值，C值），返回地址对应算法中语句的行号。⑾⑿⒀⒁⑹⑺⑻⑼⑽⑴⑵⑶⑷⑸5,3,A,B,C5,2,A,C,B5,3,A,B,C5,1,A,B,C5,2,A,C,B5,3,A,B,C5,2,A,C,B5,3,A,B,C7,1,C,A,B5,2,A,C,B5,3,A,B,C5,2,A,C,B5,3,A,B,C5,3,A,B,C7,2,B,A,C5,3,A,B,C5,1,B,C,A7,2,B,A,C5,3,A,B,C7,2,B,A,C5,3,A,B,C7,1,A,B,C7,2,B,A,C5,3,A,B,C7,2,B,A,C5,3,A,B,C5,3,A,B,C递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。递归算法的特点4.3排序问题中的分治法4.3.1归并排序4.3.2快速排序4.3.1归并排序二路归并排序的分治策略是：（1）划分：将待排序序列r1,r2,…,rn划分为两个长度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；（3）合并：将这两个有序子序列合并成一个有序序列。r1……rn/2rn/2＋1……rn划分r‘1<……
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
序列同样数量的存储空间，因此其空间复杂性为O(n)。îíì>+==1)2(211)(nnnTnnT算法4.4——合并有序子序列voidMerge(intr[],intr1[],ints,intm,intt){i=s;j=m+1;k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中较小者放入r1[k]elser1[k++]=r[j++];}if(i<=m)while(i<=m)//若第一个子序列没处理完，则进行收尾处理r1[k++]=r[i++];elsewhile(j<=t)//若第二个子序列没处理完，则进行收尾处理r1[k++]=r[j++];}4.3.2快速排序（2）求解子问题：分别对划分后的每一个子序列递归处理；（3）合并：由于对子序列r1…ri-1和ri+1…rn的排序是就地进行的，所以合并不需要执行任何操作。快速排序的分治策略是：（1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1…ri-1和ri+1…rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；[r1……ri-1]ri[ri+1……rn]均≤ri轴值均≥ri位于最终位置归并排序按照记录在序列中的位置对序列进行划分，快速排序按照记录的值对序列进行划分。以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；（2）右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若i＜j，则将基准记录与j指向的记录进行交换；（3）左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若i＜j，则将基准记录与i指向的记录交换；（4）重复（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。13652750384955jijj13652750384955jiii13652750384955ijjj一次划分示例算法4.5——一次划分intPartition(intr[],intfirst,intend){i=first;j=end;//初始化while(i0)sum=a[left];elsesum=0;}else{center=(left+right)/2;//划分leftsum=MaxSum(a,left,center);//对应情况①，递归求解rightsum=MaxSum(a,center+1,right);//对应情况②，递归求解s1=0;lefts=0; //以下对应情况③，先求解s1for(i=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}s2=0;rights=0;//再求解s2for(j=center+1;j<=right;j++){rights+=a[j];if(rights>s2)s2=rights;}sum=s1+s2;//计算情况③的最大子段和if(sum0时，可将2k×2k的棋盘划分为4个2k-1×2k-1的子棋盘，这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。2k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1(a)棋盘分割(b)构造相同子问题下面讨论棋盘覆盖问题中数据结构的设计。（1）棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；（2）子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示；（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标;（4）L型骨牌：一个2k×2k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。dcdrtrtcsize棋盘覆盖问题中的数据结构算法4.8——棋盘覆盖voidChessBoard(inttr,inttc,intdr,intdc,intsize)//tr和tc是棋盘左上角的下标，dr和dc是特殊方格的下标，//size是棋盘的大小，t已初始化为0{if(size==1)return;//棋盘只有一个方格且是特殊方格t++;//L型骨牌号s=size/2;//划分棋盘//覆盖左上角子棋盘if(dr=tc+s)//特殊方格在右上角子棋盘中ChessBoard(tr,tc+s,dr,dc,s);//递归处理子棋盘else{//用t号L型骨牌覆盖左下角，再递归处理子棋盘board[tr+s-1][tc+s]=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘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);}}设T(k)是覆盖一个2k×2k棋盘所需时间，从算法的划分策略可知，T(k)满足如下递推式：解此递推式可得T(k)=O(4k)。由于覆盖一个2k×2k棋盘所需的骨牌个数为(4k-1)/3，所以，算法4.8是一个在渐进意义下的最优算法。4.4.3循环赛日程安排问题设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能赛一次。按此要求，可将比赛日程表设计成一个n行n-1列的二维表，其中，第i行第j列表示和第i个选手在第j天比赛的选手。按照分治的策略，可将所有参赛的选手分为两部分，n＝2k个选手的比赛日程表就可以通过为n/2＝2k-1个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单：只要让这2个选手进行比赛就可以了。显然，这个求解过程是自底向上的迭代过程。具有多个选手的情况可以依此类推。(b)2k(k=2)个选手比赛(c)2k(k=3)个选手比赛加4加2(a)2k(k=1)个选手比赛122112213443344312211234214334124321567865877856876556786587785687651234214334124321这种解法是把求解2k个选手比赛日程问题划分成依次求解21、22、…、2k个选手的比赛日程问题，换言之，2k个选手的比赛日程是在2k-1个选手的比赛日程的基础上通过迭代的方法求得的。在每次迭代中，将问题划分为4部分：（1）左上角：左上角为2k-1个选手在前半程的比赛日程；（2）左下角：左下角为另2k-1个选手在前半程的比赛日程，由左上角加2k-1得到，例如22个选手比赛，左下角由左上角直接加2得到，23个选手比赛，左下角由左上角直接加4得到；（3）右上角：将左下角直接抄到右上角得到另2k-1个选手在后半程的比赛日程；（4）右下角：将左上角直接抄到右下角得到2k-1个选手在后半程的比赛日程；算法设计的关键在于寻找这4部分元素之间的对应关系。算法4.9——循环赛日程表voidGameTable(intk,inta[][]){//n=2k(k≥1)个选手参加比赛，//二维数组a表示日程安排，数组下标从1开始n=2;//k=0，2个选手比赛日程可直接求得//求解2个选手比赛日程，得到左上角元素a[1][1]=1;a[1][2]=2;a[2][1]=2;a[2][2]=1;for(t=1;t
本文档为【天津科技大学算法设计与分析 第4章 分治法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483