《算法设计技术》PPT课件.ppt

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

1、第13章 算法设计技术 引言,1984年的图灵奖得主Niklaus Wirth“Programs=Algorithm+Data Structures”算法是对特定问题求解步骤的一种描述。其基本特性为：有穷性确定性可行性输入输出一个好的算法应当具备以下特点：正确性可读性健壮性效率与低存储量需求,引言,当我们遇到一个问题时，首先需要设计算法，但是算法的设计并非一件容易的事情，它需要具备各方面的知识，同时还需要一些灵感。好在现实生活中并非每件事情的解决都要我们去传造出新的方法，很多事情前人们已经遇到，而且已经给出了很好的解决，因此首先掌握一些经典的算法思想不仅可以帮助我们解决现有的问题，而且也有助于

2、我们在此基础上进行创造性的劳动。在学习的过程中我们应当仔细体会这些思想的奥妙。,引言,经常采用的算法设计技术主要有：迭代法穷举法递归法回溯法分枝限界法分治法动态规划法贪心法,迭代法,意大利数学家Fibonacci曾提出过一个有趣的问题：“设有一对新生兔子，从第三个月开始它们每月都生一对兔子。按照这个规律，并假设兔子没有死亡的，求一年后有多少对兔子。”思路：首先我们根据已知条件来找规律,迭代法,4月个数3月个数（old）2月个数（new）=2+1=35月个数4月个数（old）3月个数（new）=3+2=56月个数5月个数（old）4月个数（new）=5+3=87月个数6月个数（old）5月个数（

3、new）=8+5=13Fib(n)=Fib(n-1)+Fib(n-2)Fib(1)=Fib(2)=1,迭代法,对于以上问题我们可以描述为Fib(n)=Fib(n-1)+Fib(n-2)Fib(1)=Fib(2)=1特点：1）存在初值。2）存在一个表达式。3）求值的过程从初值开始，通过表达式不断的计算得出新值，新值是不断的通过旧值计算出来的。我们称以上过程即为迭代过程。其思想就是由一个初值开始使用一个迭代表达式进行反复迭代，从而不断求出新值，直到求得需要的值。,迭代法,迭代过程的实现比较简单，常常使用循环结构生成效率极高的过程。int fun(int n)int i,fib,fib1,fib2;

4、fib1=fib2=1;/初值for(i=3;i=n;i+)/迭代条件：3=i=nfib=fib2+fib1;fib2=fib1;fib1=fib;return fib;,穷举法,顾名思义就是将所有的情况全部列举出来的意思。对于我们来说，穷举法似乎是一种“较笨”的算法，而且如果情况比较复杂，可能根本无法办到。为什么还要提这种方法呢？思路简单很多情况下规律的寻找并不容易，有时可能无法找到。穷举虽然对于人很麻烦易错，但是对于高速运算的计算机而言，实在是不在话下，而且重复机械计算正是计算机的特长。,穷举法,因此作为一种算法思想，加上计算机这种强大的计算工具，穷举也成为一种被人们经常使用的解决问题的方

5、法。举例下棋程序中很多时候就是运用了穷举法则，每一步可能的走法及对应招数都被存储在海量存储器中，每下一步棋，电脑便依靠强大的计算速度查询海量存储器寻找对应的解决办法，然后猜测可能的结果，最终选定一步最好的走法。求排列、组合问题,递归与分治,递归定义：直接或间接地调用自身的过程称为递归过程。,递归与分治,递归的工作原理,1,2,6,24,递归与分治,递归三要素1）问题形式：需要哪些输入参数？返回结果是什么？2）递归规则：问题如何进行分解？3）终结条件：什么情况下可以无须分解而直接求解？,递归与分治,分治思想：将一个难以直接解决的大问题，分割成一些与原问题同类型的、规模小于原问题的子问题，然后各个

6、击破，分而治之，最后再合并子问题的解从而得到原问题的解。,凡治众如治寡，分数是也。孙子兵法,递归与分治,图例：,递归与分治,分治和递归的关系由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,递归与分治,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结

7、构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,递归与分治,分治法举例Hanoi塔问题问题描述：设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：,1、每次只能移动1个圆盘；2、任何时刻都将较大的圆盘放在较小的圆盘之下；3、在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。,递归与分治,问题的分解,n个盘从A移动到B,n-1个

8、盘从A移到C,移动剩余的盘到B,n-1个盘从C移到B,n-2个盘从A移到B,移动剩余的盘到C,n-2个盘从B移到C,n-2个盘从C移到A,移动剩余的盘到B,n-2个盘从A移到B,递归与分治,程序,void hanoi(int n,int a,int b,int c)if(n=1)move(a,b);else hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);,递归与分治,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balan

9、cing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,递归与分治,递归算法优点结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。解决方法在递归算法中消除递归调用，使其转化为非递归算法：采用一个用户定义的栈来模拟系统的递归调用工作栈。通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情。,回溯法,也称为试探法。可以将回溯法看作是带优化的穷举法。基本思想在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则

10、判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。,回溯法,回溯法,在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。,回溯法,举例：迷宫问题问题描述：求从入口出口的路径,迷宫的图形表示(b)迷宫的二维数组表示,回溯法,求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索。若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索

11、。直到所有可能的通路都探索到为止。为避免走回到已经进入的点（包括已在当前路径上的点和曾经在当前路径上的点），凡是走过的点都应做上记号。为了记录当前位置以及在该位置上所选的方向，算法中设置了一个栈，栈中每个元素包括三项，分别记录当前位置的行坐标、列坐标以及在该位置上所选的方向（即direction数组的下标值）。,0,1,2,3,回溯法,迷宫的二维数组表示,过程：1）将入口为止进栈(1,1,-1)2）从栈中读出栈顶元素，判断是否为出口；若是则路径找到；否则，寻找下一个可走方位，若存在一个可走方向，则首先改写栈顶元素方位值（1,1,2），然后将这个方向的可走的相邻块进栈(2,1,-1);否则退栈。

12、3）重复以上过程，直到栈为空；或者栈顶元素为出口此外为了防止重复的走到已经经过的路，当一个块进栈时，需要修改迷宫数组的值（将该块的值改为1）,而当退栈时则要将其值恢复为0,分枝限界法,分支限界法基本思想在分支限界法中，每一次搜索过程将会对下一步所有可能的结点进行优劣判断，那些导致不可行解或导致非最优解的结点被舍弃，只有相对较优的结点才会被选中进行下一步扩展。这一过程一直重复直到找到所需的解或找不到合适的解为止。分支限界法与回溯法的不同搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。采用广度优先搜索策略的目的是:尽早发现剪枝点。以便

13、减少无效搜索次数。因此相对于回溯法而言，分枝限界法提高了问题的求解效率。,分枝限界法,分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法可应用于大量组合优化问题。其关键技术在于各节点权值如何估计，可以说，一个分支限界求解方法的效率基本上由定界方法所决定，若界估计不好，在极端情况下将与穷举搜索没有

14、区别。,动态规划法,基本思想:将待求解问题分解成若干个子问题,先求解子问题,然后从这些问题的解得到原问题的解.与分治法不同的是,经分解得到的子问题往往不是互相独立的.用一个表来记录所有已解决的子问题的答案.设计动态规划算法的步骤 1.找出最优解的性质,并刻画其结构特性2.递归地定义最优值3.以自底向上的方式计算出最优值4.根据计算最优值时得到的信息,构造一个最优解,动态规划与分治法的区别,在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而

15、在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。,动态规划举例,矩阵连乘问题 给定n个矩阵A1,A2,.,An,其中Ai与Ai+1是可乘的，i=1,2,.n-1。现在要计算这n个矩阵的连乘积。由于矩阵的乘法满足结合律，所以通过加括号可以使得计算矩阵的连乘积有许多不同的计算次序。采用不同的加扩号方式，所需要的总计算量是不一样的。若A是一个p*q矩阵，B是一个q*r矩阵，则其乘积C=AB是一个p*r矩阵。如果用标准算法计算C，总共需要pqr次数乘。,矩阵连乘问题,

16、A1，A2，A3分别是10*100,100*5和5*50的矩阵。求A1*A2*A3。如果按照(A1A2)A3)来计算，则计算所需的总数乘次数是10*100*5+10*5*50=7500 如果按照(A1(A2A3)来计算，则需要的数乘次数是100*5*50+10*100*50=75000,整整是前者的10倍。在计算矩阵连乘积时，不同的加括号方式所导致的不同的计算对计算量有很大的影响。如何确定计算矩阵连乘积A1A2，.,An的一个计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少便成为一个问题。,矩阵连乘问题,穷举法，指数级时间复杂度分析最优解结构将矩阵连乘积AiAi+1.Aj简记为Ai:j。

17、对于A1:n的一个最优次序，设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开(1=kn)，那么完全加括号的方式为(A1.Ak)(Ak+1.An)。依此次序，我们应该先分别计算A1:k和Ak+1:n，然后将计算结果相乘得到A1:n，总计算量为A1:k的计算量加上Ak+1:n的计算量，再加上A1:k和Ak+1:n相乘的计算量。通过反证法可以证明，问题的关键特征在于，计算A1:n的一个最优次序所包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种最优子结构性质是该问题可以用动态规划解决的重要特征。,矩阵连乘问题,建立递归关系定义

18、最优值。设计算Ai:j(1=i=j=n)所需的最少数乘次数为mij，则原问题的最优值为m1n。易见，当i=j时，mij=0。当ij时，若计算Ai:j的最优次序在Ak和Ak+1之间断开，可以定义mij=mik+mk+1j+pi-1*pk*pj(其中，Ai的维数为pi-1*pi)。递归关系当i=j时，mij=0。当ij时，mij=minmik+mk+1j+pi-1*pk*pj(i=kj)。将对应于mij的断开位置记为sij，在计算出最优值mij后，可以递归地由sij构造出相应的最优解。,矩阵连乘问题,计算最优值。如果直接套用mij的计算公式，进行简单的递归计算需要耗费指数计算时间。然而，实际上不同

19、的子问题的个数只是n的平方项级 用动态规划解决此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。,矩阵连乘问题,void matrixChain(int*p,int n,int*m,int*s)for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+)/链长度控制 for(int i=1;i=n-r+1;i+)/链起始位置控制 int j=i+r-1;/链终止位置 mij=mi+1j+pi-1*pi*pj;sij=i;for(i

20、nt k=i+1;kj;k+)int t=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k;,贪心算法,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,贪心选择性质,所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。,最优子结构性质,当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,贪心算法的例子,哈夫曼树和哈夫曼编码问题单源最短路径问题，Dijkstra算法最小生成树，Prim算法和Kruskal算法,