递归分治动态规划回溯优秀PPT.ppt
《递归分治动态规划回溯优秀PPT.ppt》由会员分享,可在线阅读,更多相关《递归分治动态规划回溯优秀PPT.ppt(73页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、递归分治动态规划回溯第一页,本课件共有73页 回溯 递归 递推一般实现方式正反方向有时可相互转化较简洁,要求数学规律性较强DFS穷举的优化版启发式搜索路径寻找图论/网络流数学问题:组合数学树、图、排序等问题分治、以大化小动态规划的实现DP=递归贪心回溯、递归、递推是计算机算法中基础内容,范围极其广泛。第二页,本课件共有73页递归与分治基本原理n对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。T(n/2)T(n/2)nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=T(n/2)
2、T(n/2)nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=第三页,本课件共有73页n对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n将求出的小规模的问题的解
3、合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。递归与分治基本原理n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)第四页,本课件共有73页n将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(
4、n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)递归与分治基本原理第五页,本课件共有73页递归的概念n直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。n由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。n分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。第六页,本课件共有73页递推与递归 n递归
5、与递推表面看来是相逆的过程,其实也是相似的,最终的计算都是从小算到大。n递推的使用环境要求高导致了递推的高效性,递推没有重复计算什么数据,保持了高效。n递归大多数会重复计算子问题,导致时间浪费,所以一般不要使用过深的递归,甚至会空间溢出。但是也不能说递推好,递归差,因为递归却能解决很多递推做不到的事情,在某些特定的环境下也能实现高效,并且递归容易使用。我们要就事论事!第七页,本课件共有73页斐波那契数列(Fibonacci),对于f(30),如果使用递归则需要运行1664079次,而递推只需30次就可以了,速度悬殊。递归:long f(long n)if i3 then return 1;el
6、se f(i-1)+f(i-2);递推:long f(long n)a 1:=1;a 2:=1;for i:=1 to n-2 dof i+2:=f i+f i+1;递推与递归 第八页,本课件共有73页1.经典递归例如Hanoi塔问题:经典的递归,原问题包含子问题。有些问题或者数据结构本来就是递归描述的,用递归做很自然。2.递归与递推,数学式关系利用递归的思想建立递推关系,如由兔子生崽而来的fibonacci数列。但递推由于没有返回段,因此更为简单,有时可以直接用循环实现。3.分治等以大化小算法不少分治方法是源于递归思想,或是递归分解+合并处理。递归的应用范围第九页,本课件共有73页递归的应用
7、范围n4.回溯 规模较小的问题用回溯解决比较自然。注意递归前后要保证现场的保存和恢复,即正确的转化问题。n5.动态规划 动态规划的子问题重叠性质与递归有某种相似之处。递归+动态修改查表是一种不错的建立动态规划模型的方法。树、图、排序等符合递归子问题思想的结构 树、图等数据结构本身就是递归结构,因此当然是使用递归来处理。n7.其他 例如排列组合等,很杂的。第十页,本课件共有73页递归举例例例1 1 阶乘函数阶乘函数阶乘函数可递归地定义为:边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。第十一页,本课件共有73页例例
8、2 Fibonacci2 Fibonacci数列数列无穷数列1,1,2,3,5,8,13,21,34,55,被称为Fibonacci数列。它可以递归地定义为:边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算如下:public static int fibonacci(int n)if(n 1时,perm(R)由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)构成。第十七页,本课件共有73页例例5 5 整数划分问题整数划分问题将正整数n表示成一系列正整数之和:n=n1+n2+nk,其中n1n2nk1,k1。正整数n的这种表示称为正整数n的划分。求
9、正整数n的不同划分个数。例如正整数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。递归举例第十八页,本课件共有73页(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此,q(1,m)=1。(1)q(n,1)=1,n1;当最大加数n1不大于1时,任何正整数n只有一种划分形式,即 (4)q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n-1 的划分组成。(3)q(n,n)=1+q(n,n-1)
10、;正整数n的划分由n1=n的划分和n1n-1的划分组成。例例5 5 整数划分问题整数划分问题前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解。在本例中,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。递归举例第十九页,本课件共有73页例例5 5 整数划分问题整数划分问题前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解。在本例中,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不
11、大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。递归举例第二十页,本课件共有73页第二十一页,本课件共有73页例例6 Hanoi6 Hanoi塔问题塔问题设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则:规则1:每次只能移动1个圆盘;规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;规则3:在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。
12、递归举例第二十二页,本课件共有73页在问题规模较大时,较难找到一般的方法,因此我们尝试用递归技术来解决这个问题。当n=1时,问题比较简单。此时,只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n1时,需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c,然后,将剩下的最大圆盘从塔座a移至塔座b,最后,再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见,n个圆盘的移动问题可分为2次n-1个圆盘的移动问题,这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。例例6 Hanoi6 Hanoi塔问题塔问题 public
13、 static 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);思考题:如果塔的个数变为思考题:如果塔的个数变为思考题:如果塔的个数变为思考题:如果塔的个数变为a,b,c,da,b,c,d四四四四个,现要将个,现要将个,现要将个,现要将n n个圆盘从个圆盘从个圆盘从个圆盘从a a全部移动到全部移动到全部移动到全部移动到d d,移动规则不变,求移动步数最小的方移动规则不变,求移动步数最小的方移动规则不变,求移动步数最小的方移动规则不变,求移动步数最小的方案。案。案。案。递归
14、举例第二十三页,本课件共有73页递归小结优点:优点:结构清晰,可读性强,而且容易用数学归纳法来结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带证明算法的正确性,因此它为设计算法、调试程序带来很大方便。来很大方便。缺点:缺点:递归算法的运行效率较低,无论是耗费的计递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。算时间还是占用的存储空间都比非递归算法要多。第二十四页,本课件共有73页分治法的基本步骤divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题 divide P into
15、smaller subinstances P1,P2,.,Pk;/分解问题 for(i=1,i=k,i+)yi=divide-and-conquer(Pi);/递归的解各子问题 return merge(y1,.,yk);/将各子问题的解合并为原问题的解 人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平平衡衡(balancing)子问题子问题的思想,它几乎总是比子问题规模不等的做法要好。第二十五页,本课件共有73页分治法的复杂性分析一个分治法将规模为n的问题分成k个规模
16、为nm的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:通过迭代法求得方程的解:注意注意:递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的,从而当minmi+1时,T(mi)T(n)T(mi+1)。第二十六页,本课件共有73页二分搜索技术分析:如果n=1即只有一个元素,则只要比较
17、这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析:比较x和a的中间元素amid,若x=amid,则x在L中的位置就是mid;如果xai,同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x,其方法都和在a中查找x一样,只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析:很显然此问题分解出的子问题相互独立,即在ai的前面或后面查找x是独立的子问题,因此满足分治法的第四个适用条件。给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1,现要在这,现要在这n个元素中找出一个元素中找出一特定元素特定元素x。分析:分
18、析:n该问题的规模缩小到一定的程度就可以容易地解决;该问题的规模缩小到一定的程度就可以容易地解决;n该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;n分解出的子问题的解可以合并为原问题的解;分解出的子问题的解可以合并为原问题的解;n分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。第二十七页,本课件共有73页二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1,现要在这,现要在这n个元素中找出个元素中找出一特定元素一特定元素x。据此容易设计出二分搜索算法二分搜索算法:public static int binarySea
19、rch(int a,int x,int n)/在 a0=a1=.=an-1 中搜索 x /找到x时返回其在数组中的位置,否则返回-1 int left=0;int right=n-1;while(left amiddle)left=middle+1;else right=middle-1;return-1;/未找到x 算法复杂度分析:算法复杂度分析:每执行一次算法的while循环,待搜索数组的大小减少一半。因此,在最坏情况下,while循环被执行了O(logn)次。循环体内运算需要O(1)时间,因此整个算法在最坏情况下的计算时间复杂性为O(logn)。思考题:给定思考题:给定a,用二分法设计出
20、求,用二分法设计出求an的算法。的算法。第二十八页,本课件共有73页大整数的乘法 请设计一个有效的算法,可以进行两个请设计一个有效的算法,可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法:O(n2)效率太低u分治法:abcd复杂度分析复杂度分析T(n)=O(n2)没有改进没有改进X=Y=X=a 2n/2+b Y=c 2n/2+d XY=ac 2n+(ad+bc)2n/2+bd 第二十九页,本课件共有73页大整数的乘法 请设计一个有效的算法,可以进行两个请设计一个有效的算法,可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法:O(n2)效率太低u分治法:XY=a
21、c 2n+(ad+bc)2n/2+bd 为了降低时间复杂度,必须减少乘法的次数。1.XY=ac 2n+(a-c)(b-d)+ac+bd)2n/2+bd2.XY=ac 2n+(a+c)(b+d)-ac-bd)2n/2+bd复杂度分析复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进较大的改进细节问题细节问题:两个XY的复杂度都是O(nlog3),但考虑到a+c,b+d可能得到m+1位的结果,使问题的规模变大,故不选择第2种方案。第三十页,本课件共有73页大整数的乘法 请设计一个有效的算法,可以进行两个请设计一个有效的算法,可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学
22、的方法:O(n2)效率太低u分治法:O(n1.59)较大的改进u更快的方法?如果将大整数分成更多段,用更复杂的方式把它们组合起来,将有可能得到更优的算法。最终的,这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法,对于大整数乘法,它能在O(nlogn)时间内解决。是否能找到线性时间的算法?目前为止还没有结果。第三十一页,本课件共有73页Strassen矩阵乘法A和B的乘积矩阵C中的元素Ci,j定义为:若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素Cij,需要做n次乘法和n-1次加法。因此,算出矩阵C的
23、 个元素所需的计算时间为O(n3)u传统方法:O(n3)第三十二页,本课件共有73页Strassen矩阵乘法使用与上例类似的技术,将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为:u传统方法:O(n3)u分治法:由此可得:复杂度分析复杂度分析T(n)=O(n3)没有改进没有改进第三十三页,本课件共有73页Strassen矩阵乘法u传统方法:O(n3)u分治法:为了降低时间复杂度,必须减少乘法的次数。复杂度分析复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进较大的改进第三十四页,本课件共有73页Strassen矩阵乘法u传统方法:O(n3)u分治
24、法:O(n2.81)u更快的方法?Hopcroft和Kerr已经证明(1971),计算2个矩阵的乘积,7次乘法是必要的。因此,要想进一步改进矩阵乘法的时间复杂性,就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法?目前为止还没有结果。第三十五页,本课件共有73页快速排序private static int partition(int p,int r)int i=p,j=r+1;Comparable x=ap;/将=x的元素交换到左边
25、区域 /将=x的元素交换到右边区域 while(true)while(a+pareTo(x)0);if(i=j)break;MyMath.swap(a,i,j);ap=aj;aj=x;return j;初始序列6,7,5,2,5,8j-;5,7,5,2,6,8i+;5,6,5,2,7,8j-;5,2,5,6,7,8i+;完成快速排序具有不稳定性不稳定性。6,7,5,2,5,85,2,5 6 7,8第三十六页,本课件共有73页private static int randomizedPartition(int p,int r)int i=random(p,r);MyMath.swap(a,i,p
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 分治 动态 规划 回溯 优秀 PPT
限制150内