清华大学算法课13课件

算法与数据结构Algorithms and Data Structures 第十三章 算法分析与设计技术Algorithm Analysis and Design Techniques 13.1 递归算法的分析递归算法的分析13.2 递归式求解递归式求解13.3 大递归式的一般解大递归式的一般解13.4 分而治之法分而治之法13.5 动态规划法动态规划法13.6 贪心法贪心法13.7 搜索算法搜索算法13.1 递归算法的分析递归算法的分析考虑一个归并排序算法：考虑一个归并排序算法：考虑一个归并排序算法：考虑一个归并排序算法：List List mergesort(Listmergesort(List L,intL,int n)n)if(n=1)return L;if(n=1)return L;break L into 2 halves,L1 and L2,each of length n/2;break L into 2 halves,L1 and L2,each of length n/2;return merge(mergesort(l1,n/2),mergesort(l2,n/2);return merge(mergesort(l1,n/2),mergesort(l2,n/2);/设设设设 T(n)T(n)是是是是最坏情况下的时间复杂度。最坏情况下的时间复杂度。最坏情况下的时间复杂度。最坏情况下的时间复杂度。显然：显然：显然：显然：T(n)=1 if n=1;T(n)=1 if n=1;T(n)1 T(n)1我们前面已做过很多递归算法的分析，给出了相应的我们前面已做过很多递归算法的分析，给出了相应的递归式；递归式；例如：例如：Hanoi塔：塔：T(0)=0 T(n)=2T(n-1)+1折半查找折半查找：T(0)=0;T(1)=1;T(n)=T(n/2)+1;最复杂的是快速排序。最复杂的是快速排序。13.2 递归式求解递归式求解有有三种方法：三种方法：(1).猜一个解猜一个解f(n)，代入递归式，对代入递归式，对n归纳证明归纳证明T(n)=f(n)，同时确定同时确定F(n)中的不定系数，使对所中的不定系数，使对所有的有的n有有T(n)=f(n)。(2).展开递归式，直到式子的右边的展开递归式，直到式子的右边的T(m)均为初试均为初试递归式（如递归式（如T(0),T(1)）.(3).一般求法。一般求法。1 猜解：猜解：T(n)=1 if n=1;T(n)=1 if n=1;T(n)1 T(n)1 设设设设T(n)=T(n)=a.n.logn+ba.n.logn+b 归纳基础：当归纳基础：当归纳基础：当归纳基础：当 n=1n=1时时时时 b=1 b=1 设对所有的设对所有的设对所有的设对所有的kn k=T(k)=T(k)当当当当k=nk=n时：时：时：时：T(n)=2T(n/2)+cnT(n)d(b)2.若：若：ad(b)(2)d(n)=n2,所以所以d(b)=4,因因a=4=d(b)(3)T(n)=4T(n/4)+n3 d(n)=n3,所以所以d(b)=8,因因a=4d(b)所以特解是：所以特解是：n1.59所以所以 T(n)=O(n1.59)例例3：T(1)=1 T(n)=2T(n/2)+nlogn显然通解是显然通解是 n。a=b=2,d(n)=nlogn 不是不是n的积。的积。特解：特解：13.4 分而治之法分而治之法分而治之就是将大的问题分解小的子问题分别解决，分而治之就是将大的问题分解小的子问题分别解决，最常用的办法是递归算法。在前面我们已设计了许最常用的办法是递归算法。在前面我们已设计了许多递归算法，诸如：多递归算法，诸如：Hanoi塔，快速排序，归并排序，塔，快速排序，归并排序，二叉树遍历，二叉树遍历，dfs，等等。等等。下面在看几个例子，它们比较特殊下面在看几个例子，它们比较特殊例例4：两个两个n位位正整数相乘，这两个数很大，大到计算正整数相乘，这两个数很大，大到计算机内部无法表示。机内部无法表示。为简化问题，设为简化问题，设n是是2的幂。的幂。X=ABY=CD X=A10n/2+BY=C10n/2+DXY=AC10n+(AD+BC)10n/2+BD算法分析：位乘次数算法分析：位乘次数T(1)=1T(n)=4T(n/2)+cn T(n)=O(n2)改进：改进：XY=AC10n+(A-B)(D-C)+AC+BD)10n/2+BDT(1)=1T(n)=3T(n/2)+cn T(n)=O(n1.59)以上公式已说明了递归算法的三要素。以上公式已说明了递归算法的三要素。算法算法Void mult-Big-Num(&c,x,y,n)byte m1,m2,m3;byte An/2,Bn/2,Cn/2,Dn/2;c=new byte2*n;if(n=1)if(x!=0&y!=0)c=multy(x,y,1);else c=0;else A=left n/2 digits of x;B=right n/2 digits of x;C=left n/2 digits of y;D=right n/2 digits of y;mult-big-num(&m1,A,C,n/2);mult-big-num(&m2,A-B,D-C,n/2);mult-big-num(&m3,B,D,n/2);c=m1;c=left-shift(c,n/2);c+=m1+m2+m3;c=left-shift(c,n/2);c+=m3;/m1*10n+(m1+m2+m3)*10n/2+m3 例例5：网球循环赛的安排，每个选手每天只能参赛一场，网球循环赛的安排，每个选手每天只能参赛一场，如有如有n个选手，需要进个选手，需要进n-1天。天。为简单起见，设为简单起见，设n是是2的幂。的幂。（1）最简问题及其解：）最简问题及其解：n=2,（2）问题的划分：将问题的划分：将n个分成两组，每组个分成两组，每组n/2人，进行人，进行循环比赛。循环比赛。（3）解的合成：）解的合成：21121天 21121天2 3 41 4 34 1 23 2 112341 2 32143+21 22 13 44 3加加第第1行：行：1 2第第2行：第行：第1行左循环位移行左循环位移2 3 41 4 34 1 23 2 16 7 85 8 78 5 67 6 55 6 7 86 7 8 57 8 5 68 5 6 71 2 3 42 3 4 13 4 1 24 1 2 3加加第第1行：行：1 2 3 4第第2行：第行：第1行左循环位移行左循环位移第第3行：第行：第2行左循环位移行左循环位移第第4行：第行：第3行左循环位移行左循环位移+413.5 动态规划法动态规划法(Dynamic Programming)(Dynamic Programming)在本节中我们通在本节中我们通在本节中我们通在本节中我们通过一些列子说过一些列子说过一些列子说过一些列子说明什么是动态明什么是动态明什么是动态明什么是动态规划法。规划法。规划法。规划法。例例例例6 6：斐波拿契数斐波拿契数斐波拿契数斐波拿契数列：列：列：列：f(0)=0,f(1)=1f(0)=0,f(1)=1f(n)=f(n-1)+f(n-2);f(n)=f(n-1)+f(n-2);510211010433221问问题题分分解解解解的的合合成成递归子问题图递归子问题图递归求解如图：其中递归求解如图：其中递归求解如图：其中递归求解如图：其中f(3)f(3)重复计重复计重复计重复计2 2次，次，次，次，f(2)f(2)重复计算重复计算重复计算重复计算3 3次次次次当当当当n n增大时，这样的重复计算会按指数级增长。增大时，这样的重复计算会按指数级增长。增大时，这样的重复计算会按指数级增长。增大时，这样的重复计算会按指数级增长。如果我们把子问题的解记录下来，当需要时，直接引如果我们把子问题的解记录下来，当需要时，直接引如果我们把子问题的解记录下来，当需要时，直接引如果我们把子问题的解记录下来，当需要时，直接引用，就可避免重复计算。用，就可避免重复计算。用，就可避免重复计算。用，就可避免重复计算。当求一个子问题当求一个子问题当求一个子问题当求一个子问题P P的解时的解时的解时的解时,它可能用到子问题它可能用到子问题它可能用到子问题它可能用到子问题P P1 1，P2P2，P Pk k的解，在递归算法中的解，在递归算法中的解，在递归算法中的解，在递归算法中P P1 1，P2P2，P Pk k的解的解的解的解是递归调用算法计算出来的，我们现在希望能从表是递归调用算法计算出来的，我们现在希望能从表是递归调用算法计算出来的，我们现在希望能从表是递归调用算法计算出来的，我们现在希望能从表中找到他们的解，而不是再计算。中找到他们的解，而不是再计算。中找到他们的解，而不是再计算。中找到他们的解，而不是再计算。这样就需要搞清楚所有子问题间的依赖关系。我们用这样就需要搞清楚所有子问题间的依赖关系。我们用这样就需要搞清楚所有子问题间的依赖关系。我们用这样就需要搞清楚所有子问题间的依赖关系。我们用一个有向图表示这种关系。称此图为一个有向图表示这种关系。称此图为一个有向图表示这种关系。称此图为一个有向图表示这种关系。称此图为子问题图子问题图子问题图子问题图（SubproblemSubproblem GarphGarph）012345从最简单问题开始，我们由底向上逐层把子问题的解从最简单问题开始，我们由底向上逐层把子问题的解从最简单问题开始，我们由底向上逐层把子问题的解从最简单问题开始，我们由底向上逐层把子问题的解添在一个表中，在合成解时，从表中查找所需要的添在一个表中，在合成解时，从表中查找所需要的添在一个表中，在合成解时，从表中查找所需要的添在一个表中，在合成解时，从表中查找所需要的下层的子问题的解即可。这样的方法是最基本的下层的子问题的解即可。这样的方法是最基本的下层的子问题的解即可。这样的方法是最基本的下层的子问题的解即可。这样的方法是最基本的动动动动态规划法态规划法态规划法态规划法。规划的另一个含义是。规划的另一个含义是。规划的另一个含义是。规划的另一个含义是在多个候选者中选在多个候选者中选在多个候选者中选在多个候选者中选择最好的择最好的择最好的择最好的。Fibonacci Fibonacci 数列问题的子问题图：数列问题的子问题图：数列问题的子问题图：数列问题的子问题图：012345求子问题解的顺序是按逆拓扑序进行的。求子问题解的顺序是按逆拓扑序进行的。求子问题解的顺序是按逆拓扑序进行的。求子问题解的顺序是按逆拓扑序进行的。例例例例7 7：我们已熟悉的一个问题：求组合数：我们已熟悉的一个问题：求组合数：我们已熟悉的一个问题：求组合数：我们已熟悉的一个问题：求组合数：4,23,23,12,22,12,12,01,1 1,0 1,1 1,0递归求解过程递归求解过程递归算法的动态规划版递归算法的动态规划版递归算法递归算法:Int comb(int m,int n)if(m=0|m=n)return 1;return(comb(m-1,n-1)+comb(m,n-1);/ADT Dictionary is/设一个设一个ADT Dictionary Data:Set of subproblems results;Operations:store(sbp,rslt);/存储子问题存储子问题sbp的解的解rslt member(sbp);/检查检查sbp的解是否已在字典中的解是否已在字典中 retrieve(sbp);/取出取出sbp的解的解END ADT Dictionary动态规划算法动态规划算法:dic是是ADT DictionaryInt comb(int m,int n)if(m=0|m=n)rslt=1;else if(!dic.member(m-1,n-1)rslt1=comb(m-1,n-1);else rslt1=dic.retrieve(m-1,n-1);if(!dic.member(m,n-1)rslt2=comb(m,n-1);else rslt2=dic.retrieve(m,n-1);rslt=rslt1+rslt2;dic.store(m,n),rslt);/如果问题图很清楚，可以直接按该图的逆拓扑序遍历如果问题图很清楚，可以直接按该图的逆拓扑序遍历求解各子问题。通常求解各子问题。通常dic是一个数组（一维或二维）是一个数组（一维或二维）1,02,03,04,01,12,13,14,12,23,24,2子子问题图问题图4,2 3,2 3,1 2,1 2,2 1,11,04,0 3,0 2,0拓扑序列之一拓扑序列之一nm1 2 3 4 5 6432101 1 1 1 1 111112345636101541020515For(j=1;j=n;j+)c0j=1;For(i=0;i=m;i+)cij=1;For(i=1;i=m;i+)For(j=i+1;j=n;j+)cij=cij-1+ci-1j-1算法分析：梯形计算算法分析：梯形计算mn0 1 2 3 4 5 543211111111111233464510试一试，只用一维数组如何计算试一试，只用一维数组如何计算105最优二查查找树最优二查查找树二叉查找树二叉查找树ringhasthingcabbagetalkofwalrusandsaidkingtimecomethepigwing平均查找长度：平均查找长度：其中：其中：pi 是查找第是查找第i个个对象的概率，对象的概率，ci 是是比较次数。比较次数。例：例：Keypi 比较比较ci pi ciAnd.1504.600Cabbage .0253.075Come.0504.200Has.0252.050King.0504.200Of.1253.375Pig.0254.100Ring.0751.075Said.0754.300Talk.0503.150Keypi 比较比较ci pi ciThe.1504.600Thing.0752.150Time.0502.100Walrus.0253.075Wing.0504.200平均查找长度：平均查找长度：total=3.250显然这不是一个最优二叉查找树。显然这不是一个最优二叉查找树。关键字集：关键字集：k1,k2,k3,.,kn,ki ki+1:i=1,2,n-1查找概率：查找概率：p1,p2,p3,.,pn 权权子子问题（问题（low,high）:构造构造klow,klow+1,.,khigh的的最最优二叉查找树。优二叉查找树。我们采用以下表示：我们采用以下表示：1 A(low,high,r)是以是以kr为根的子问题为根的子问题（low,high）的最的最小平均查找长度。小平均查找长度。2 A(low,high)是子问题是子问题（low,high）的最小平均查找长的最小平均查找长度。度。3 p(low,high)=plow+plow+1+phigh,被被查找查找key在在klow,klow+1,.,khigh的的概率。概率。A(l,h,r)=A(l,r-1)+A(r+1,h)+p(l,r)r=l,l+1,hA(l,h)=minA(l,h,r)|l=rh,对应对应的子问题是空树。的子问题是空树。只需要计算上三角。只需要计算上三角。Costkk=pkCostkk-1=000p10p20P30P40P50P60P70p80 0 1 2 3 4 5 6 7 80123456789子子问题的求解次序问题的求解次序For(i=n-1;i0;i-)For(j=i+1;j=1;low-)for(high=low-1;highhigh)bestCost=0;bestRoot=-1;/空空 else bestCost=MAX;for(r=low;r=high;r+)rCost=p(low,high)+costlowr-1+costr+1high;if(rCostbestCost)bestCost=rCost;bestRoot=r;costlowhigh=bestCost;rootlowhigh=bestRoot;算法分析：算法分析：bestChoice():T(l,h)=h-lh:空树；空树；2.问题划分：构造子树（问题划分：构造子树（l,h），），rootlh=k,=构造子树构造子树(l,k-1)LT和子树和子树(k+1,h)RT3.解的合成：构造根解的合成：构造根Kk，LT做为左子树，做为左子树，RT作为右作为右子树。子树。13.6 贪心法贪心法(Greedy Algorithms)(Greedy Algorithms)我们已经接触过的贪心算法有我们已经接触过的贪心算法有Dijkstra单源最短路径单源最短路径算法算法和和Kruscal算法算法最小生成树最小生成树。贪心法在当前步骤，只考虑当前的最优解，而不考虑贪心法在当前步骤，只考虑当前的最优解，而不考虑以后的情况。以后的情况。例例8：找币问题：有硬币找币问题：有硬币1角，角，6分，分，1分分3种，种，如何找出如何找出1角角8分？硬币数越少越好。分？硬币数越少越好。贪心法：贪心法：步骤步骤1：1个个1角，差角，差8分分 步骤步骤2：1个个6分，差分，差2分分 步骤步骤3：2个个1分，结束分，结束 ；共用共用4个硬币。个硬币。最优解是：最优解是：3个个6分。分。例例9：用贪心算法解决构造最优二叉查找树问题。用贪心算法解决构造最优二叉查找树问题。对子问题（对子问题（l,h），），选取选取 kl,kl+1,kh,中权最大的中权最大的kr(l=rh,空树；空树；2问题划分：在问题划分：在kl,kl+1,kh,中找出权最大的中找出权最大的kr，分分为子问题（为子问题（l,r-1）和（和（r+1,h）;3解的合成：解的合成：kr做根，做根，T(l,r-1)做左子树，做左子树，T(r+1,h)做做右子树；右子树；数组数组key1n,p1n(key的权的权)算法：算法：BTNode bestBST(int low,int high)if(lowhigh)return NULL;r=low;for(i=low+1;ipr)r=i;root=new BTNode(keyr);/新根新根 root.lchid=bestBST(low,r-1);root.rchild=bestBST(r+1,high);return root;例例10：Key:A B C D EP 2/15 5/15 4/15 1/15 3/15 贪心算法构造的二叉查找树贪心算法构造的二叉查找树 动态规划算法构造的动态规划算法构造的BACEDA(n)=5/15+(2/15+4/15)*2 +3/15*3+1/15*4=5/15+12/15+9/15+4/15=2CBEDAA(n)=4/15+(5/15+3/15)*2 +(2/15+1/15)*3=4/15+16/15+9/15=1.93313.7 搜索算法搜索算法状态（状态（状态（状态（StatusStatus）:问题在某一时刻的状态问题在某一时刻的状态问题在某一时刻的状态问题在某一时刻的状态(属性值集合属性值集合属性值集合属性值集合)。列列列列1111：将将将将A,BA,B放在该网格中，有放在该网格中，有放在该网格中，有放在该网格中，有1212种状态。种状态。种状态。种状态。状态空间（状态空间（状态空间（状态空间（Status SpaceStatus Space）:所有状态的集合。所有状态的集合。所有状态的集合。所有状态的集合。状态变迁（产生式）：状态变迁（产生式）：状态变迁（产生式）：状态变迁（产生式）：有一个状态变为另一个状态的有一个状态变为另一个状态的有一个状态变为另一个状态的有一个状态变为另一个状态的规则。规则。规则。规则。开始状态（开始状态（开始状态（开始状态（Initial StatusInitial Status）：）：）：）：问题的初始状态。问题的初始状态。问题的初始状态。问题的初始状态。终止状态终止状态终止状态终止状态(End Status)(End Status)：问题的目标状态。问题的目标状态。问题的目标状态。问题的目标状态。例例例例1212：4 4皇后问题：皇后问题：皇后问题：皇后问题：A B ABABABABB AB ABABABABAA B4*44*4网格网格网格网格状态状态状态状态：状态空间：状态空间：状态空间：状态空间：16*15*14*1216*15*14*12个状态个状态个状态个状态开始状态开始状态开始状态开始状态：空网格。空网格。空网格。空网格。终止状态终止状态终止状态终止状态：状态变迁：状态变迁：状态变迁：状态变迁：状态可达树：状态可达树：状态可达树：状态可达树：从初始状态开始，按状态变迁产生下层从初始状态开始，按状态变迁产生下层从初始状态开始，按状态变迁产生下层从初始状态开始，按状态变迁产生下层状态，构成的树，叶结点是终止状态或祖先出现过状态，构成的树，叶结点是终止状态或祖先出现过状态，构成的树，叶结点是终止状态或祖先出现过状态，构成的树，叶结点是终止状态或祖先出现过的状态。的状态。的状态。的状态。例例例例1313：4 4皇后问题：皇后问题：皇后问题：皇后问题：问题的求解问题的求解从根开始，在可达树中搜索终止状态。从根开始，在可达树中搜索终止状态。深度优先搜索算法思想：深度优先搜索算法思想：Boolean dfsSearch(S)if(S is in F)return true;/F:终止状态集终止状态集 set S to be Visited;for(each Ss next statue S)S=generateNext(S);if(S is not Visited)rslt=dfsSearch(S);if(rslt)break;/去掉此句就是详尽搜索去掉此句就是详尽搜索 return rslt;算法是一边搜索一边创建后继状态，而不是先创建状态算法是一边搜索一边创建后继状态，而不是先创建状态可达树，然后再搜索。开始时只有一个初始状态。可达树，然后再搜索。开始时只有一个初始状态。广度优先搜索算法思想：广度优先搜索算法思想：Boolean bfsSearch(S0)/S0是初始状态是初始状态 Q=new Q(n);Q.entre(S0);while(!Q.empty()S=Q.out();if(S is in F)return true;/F:终止状态集终止状态集 set S to be Visited;for(each Ss next statue S)S=generateNext(S);if(S is not Visited)Q.entre(S);/while return false;有界深度优先搜索算法思想：有界深度优先搜索算法思想：如果弧上有权（默认为如果弧上有权（默认为1），在搜索中从），在搜索中从S0到当前状态到当前状态S的路径的路径长度长度为为length(S).给定一个给定一个len，搜索到搜索到S，其，其路径长度大于路径长度大于len，就不再向前搜索，就不再向前搜索，退回上一状态。退回上一状态。Boolean dfsSearch(S，len)if(S is in F)return true;/F:终止状态集终止状态集 set S to be Visited;for(each Ss next statue S)S=generateNext(S);if(S is not Visited&length(S)len)return dfsSearch(S);return false;例例14：迷宫问题：迷宫问题：已知从入口到出口至少有已知从入口到出口至少有一条路径的路径长度不超一条路径的路径长度不超过过len。走到走到A时，路径长度超过了时，路径长度超过了len，因此不再往前走，退因此不再往前走，退回到上一位置，换一方向。回到上一位置，换一方向。A详尽搜索：详尽搜索：将状态可达树遍历；将状态可达树遍历；非详尽搜索：非详尽搜索：只要到达终止状态就结束搜索。这种搜索不完只要到达终止状态就结束搜索。这种搜索不完备，得到的解不一定是最优的。备，得到的解不一定是最优的。盲目搜索：盲目搜索：在一个状态下，对下一个状态的选择是盲目的。在一个状态下，对下一个状态的选择是盲目的。以上算法都是盲目搜索。以上算法都是盲目搜索。启发式搜索启发式搜索启发信息与估价函数（启发信息与估价函数（Payoff）下一步去哪？有时会有一些提示信下一步去哪？有时会有一些提示信 息帮助我们尽快到达终止状态。这息帮助我们尽快到达终止状态。这 样的信息就是启发信息。用于估样的信息就是启发信息。用于估价一个结点的重要性的函数是价一个结点的重要性的函数是估价函数估价函数：f(x)=g(x)+h(x)g(x):从初始状态到当前状态从初始状态到当前状态x所所花费的代价。花费的代价。h(x):从从当前状态当前状态x到到终止状态要花费的代价（或概率）。终止状态要花费的代价（或概率）。局部择优搜索法：局部择优搜索法：深度优先搜索的改进：深度优先搜索的改进：ABCDAEDCB当前状态当前状态A,下一步的状态有下一步的状态有B,C,D,E可选，可选，设：设：f(B)=16,f(C)=14,f(D)=13,f(E)=18,选择选择D.全局择优搜索法（全局择优搜索法（A算法）：算法）：A是是当前状态，下一个状态选择当前状态，下一个状态选择绿色状态中绿色状态中f(x)最小的。最小的。它既不是深度优先，也不是广度它既不是深度优先，也不是广度优先。优先。S0utsrzyxAEDCBA算法算法我们应该把绿色的状态和灰色的状态记录下来。我们应该把绿色的状态和灰色的状态记录下来。OPEN表：存放绿色状态，已经产生而未访问的状态。该表：存放绿色状态，已经产生而未访问的状态。该表按表按f(s)排序（不减排序（不减）CLOSE表：存放灰色状态，已经访问过的状态。表：存放灰色状态，已经访问过的状态。算法思想：算法思想：1产生初始状态产生初始状态S0，入，入OPEN表，计算表，计算f(S0)；2若若OPEN表空，搜索失败，结束；表空，搜索失败，结束；3取出取出OPEN表的第表的第1个状态个状态S，放入放入CLOSE表；表；4若若S是终止状态，得到解，结束；是终止状态，得到解，结束；5若若S不可扩展，转不可扩展，转2；6产生产生S的所有后继状态，计算他们的的所有后继状态，计算他们的f(x),并入并入OPEN表，转表，转2。例例15：迷宫问题，找一条最短的路径。迷宫问题，找一条最短的路径。初始状态初始状态：（1，1）终止状态：终止状态：（n,n）g(i,j):(1,1)到到(i,j)的路径长度；的路径长度；h(i,j):(i,j)到到(n,n)的路径长度的估计值；的路径长度的估计值；h(i,j)=2n-i-j;n-jn-ig(i,j)h(i,j)A*算法算法是是A算法的改进算法的改进h(x):是是从当前状态从当前状态x到终止状态要花费的代价的估计值；到终止状态要花费的代价的估计值；h*(x):是是从当前状态从当前状态x到终止状态要花费的代价的实际值；到终止状态要花费的代价的实际值；要求：要求：h(x)=h*(x)例例16：上一例中对所有的上一例中对所有的i,j有有 h(i,j)=2n-i-j=h*(i,j)