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

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

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

3、数（new）= 5+3=8 7月个数6月个数（old）5月个数（new）= 8+5=13 Fib(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）求值的过程从初值开始，通过表达式不断的计算得出新值，新值是不断的通过旧值计算出来的。 我们称以上过程即为迭代过程。其思想就是由一个初值开始使用一个迭代表达式进行反复迭代，从而不断求出新值，直到求得需要的值。,迭代法,迭代过程的实现比较简单，常常使用循环结构生成

4、效率极高的过程。 int fun(int n) int i, fib, fib1, fib2; fib1=fib2=1; /初值 for (i=3; i=n; i+) /迭代条件：3 = i = n fib = fib2 + fib1; fib2 = fib1; fib1 = fib; return fib; ,穷举法,顾名思义就是将所有的情况全部列举出来的意思。 对于我们来说，穷举法似乎是一种“较笨”的算法，而且如果情况比较复杂，可能根本无法办到。 为什么还要提这种方法呢？ 思路简单 很多情况下规律的寻找并不容易，有时可能无法找到。 穷举虽然对于人很麻烦易错，但是对于高速运算的计算机而言，实

5、在是不在话下，而且重复机械计算正是计算机的特长。,穷举法,因此作为一种算法思想，加上计算机这种强大的计算工具，穷举也成为一种被人们经常使用的解决问题的方法。 举例 下棋程序中很多时候就是运用了穷举法则，每一步可能的走法及对应招数都被存储在海量存储器中，每下一步棋，电脑便依靠强大的计算速度查询海量存储器寻找对应的解决办法，然后猜测可能的结果，最终选定一步最好的走法。 求排列、组合问题,递归与分治,递归 定义：直接或间接地调用自身的过程称为递归过程。,递归与分治,递归的工作原理,1,2,6,24,递归与分治,递归三要素 1）问题形式：需要哪些输入参数？返回结果是什么？ 2）递归规则：问题如何进行分

6、解？ 3）终结条件：什么情况下可以无须分解而直接求解？,递归与分治,分治 思想：将一个难以直接解决的大问题，分割成一些与原问题同类型的、规模小于原问题的子问题，然后各个击破，分而治之，最后再合并子问题的解从而得到原问题的解。,凡治众如治寡，分数是也。 孙子兵法,递归与分治,图例：,递归与分治,分治和递归的关系 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多

7、高效算法。,递归与分治,分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,递归与分治,分治法举例 Hanoi塔问题 问题描述：设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：,1、每次只

8、能移动1个圆盘； 2、任何时刻都将较大的圆盘放在较小的圆盘之下； 3、在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。,递归与分治,问题的分解,n个盘从A移动到B,n-1个盘从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

9、, c, b, a); ,递归与分治,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,递归与分治,递归算法优点 结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点 运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 解决方法 在递归算法中消除递归调用，使其转化为非递归算法：采用一个用户定义的栈来模拟系统的递归调用工作

10、栈。通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情。,回溯法,也称为试探法。可以将回溯法看作是带优化的穷举法。 基本思想 在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。 在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。,回溯法,回溯法,在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续

11、试探的过程称为向前试探。,回溯法,举例：迷宫问题 问题描述：求从入口出口的路径,迷宫的图形表示 (b) 迷宫的二维数组表示,回溯法,求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索。若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索。直到所有可能的通路都探索到为止。 为避免走回到已经进入的点（包括已在当前路径上的点和曾经在当前路径上的点），凡是走过的点都应做上记号。 为了记录当前位置以及在该位置上所选的方向，算法中设置了一个栈，栈中每个元素包括三项，分别记录当前位置的行坐标、列坐标以及在该位置上所选的方向（即direction数组的下标值）。,0,1,2,3,回溯法,迷宫的二维

12、数组表示,过程： 1）将入口为止进栈(1,1,-1) 2）从栈中读出栈顶元素，判断是否为出口；若是则路径找到；否则，寻找下一个可走方位，若存在一个可走方向，则首先改写栈顶元素方位值（1,1,2），然后将这个方向的可走的相邻块进栈(2,1,-1);否则退栈。 3）重复以上过程，直到栈为空；或者栈顶元素为出口 此外为了防止重复的走到已经经过的路，当一个块进栈时，需要修改迷宫数组的值（将该块的值改为1）,而当退栈时则要将其值恢复为0,分枝限界法,分支限界法基本思想 在分支限界法中，每一次搜索过程将会对下一步所有可能的结点进行优劣判断，那些导致不可行解或导致非最优解的结点被舍弃，只有相对较优的结点才会

13、被选中进行下一步扩展。这一过程一直重复直到找到所需的解或找不到合适的解为止。 分支限界法与回溯法的不同 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。采用广度优先搜索策略的目的是:尽早发现剪枝点。以便减少无效搜索次数。因此相对于回溯法而言，分枝限界法提高了问题的求解效率。,分枝限界法,分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择

14、一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 分支限界法可应用于大量组合优化问题。其关键技术在于各节点权值如何估计，可以说，一个分支限界求解方法的效率基本上由定界方法所决定，若界估计不好，在极端情况下将与穷举搜索没有区别。,动态规划法,基本思想: 将待求解问题分解成若干个子问题,先求解子问题,然后从这些问题的解得到原问题的解. 与分治法不同的是,经分解得到的子问题往往不是互相独立的.用一个表来记录所有已解决的子问题的答案. 设计动态规划算法的步骤 1.找出最优解的性质,并刻画其结构特性 2.递归地定义最优值 3.以自底向上的方式计算出最优值

15、4.根据计算最优值时得到的信息,构造一个最优解,动态规划与分治法的区别,在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。 动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。 由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。,动态规划举例,矩阵连乘问题 给定n个矩阵A1,A2,.,An,其中Ai与Ai+1是可乘的，i=1,2,.n-1。现在要计算这n个矩

16、阵的连乘积。 由于矩阵的乘法满足结合律，所以通过加括号可以使得计算矩阵的连乘积有许多不同的计算次序。采用不同的加扩号方式，所需要的总计算量是不一样的。 若A是一个p*q矩阵，B是一个q*r矩阵，则其乘积C=AB是一个p*r矩阵。如果用标准算法计算C，总共需要pqr次数乘。,矩阵连乘问题,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倍。

17、 在计算矩阵连乘积时，不同的加括号方式所导致的不同的计算对计算量有很大的影响。 如何确定计算矩阵连乘积A1A2，.,An的一个计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少便成为一个问题。,矩阵连乘问题,穷举法，指数级时间复杂度 分析最优解结构 将矩阵连乘积AiAi+1.Aj简记为Ai:j。 对于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:

18、k和Ak+1:n相乘的计算量。 通过反证法可以证明，问题的关键特征在于，计算A1:n的一个最优次序所包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种最优子结构性质是该问题可以用动态规划解决的重要特征。,矩阵连乘问题,建立递归关系定义最优值。 设计算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)。 递归关系

19、 当i=j时，mij=0。 当ij时，mij=minmik+mk+1j+pi-1*pk*pj (i=kj)。 将对应于mij的断开位置记为sij，在计算出最优值mij后，可以递归地由sij构造出相应的最优解。,矩阵连乘问题,计算最优值。 如果直接套用mij的计算公式，进行简单的递归计算需要耗费指数计算时间。 然而，实际上不同的子问题的个数只是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=