计算机算法设计与分析总复习

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机算法设计与分析,1.1,算法的定义和特征,1),什么是算法？,算法是求解某一,特定问题,的一组,有穷规则,的集合，它,是由若干条指令组成的有穷符号串,。,2,）,算法的五个重要特性,确定性,、,可实现性,、,输入,、,输出,、,有穷性,3,）,算法设计的质量指标,正确性，可读性，健壮性，效率与存储量,算法和程序的区别,程序：一个计算机程序是对一个算法使用某种程序设计语言的具体实现,任何一种程序设计语言都可以实现任何一个算法,算法的有穷性意味着不是所有的计算机程序都是算法,问题求解,(Problem Solving),证明正确性,分析算法,设计程序,理解问题,精确解或近似解,选择数据结构,算法设计策略,设计算法,一般只考虑三种情况下的时间性,:,最坏情况、最好情况和平均情况下的复杂性，分别记为,Tmax(n,),、,Tmin(n,),和,Tavg(n,),算法复杂性,=,算法所需要的计算机资源,=,时间复杂性,+,空间复杂性,算法渐近复杂性,1,）上界函数,定义,1,如果存在两个正常数,c,和,n,0,，,对于所有的,n,n,0,，,有,|f(n)| c|g(n)|,则记作,f(n) =,(g(n),含义：,如果算法用,n,值不变的同一类数据在某台机器上运行时，所用的时间总是小于,|g(n)|,的一个常数倍。所以,g(n),是计算时间,f(n),的一个,上界函数,。,f(n),的数量级就是,g(n),。,f(n,),的增长最多像,g(n,),的增长那样快,试图求出,最小,的,g(n),，,使得,f(n) =,(g(n),。,算法分类（计算时间）,多项式时间算法,：可用多项式（函数）对其计算时间限界的算法。,常见的多项式限界函数,有：,(1) ,(,logn,) ,(n) ,(,nlogn,) ,(n,2,) ,(n,3,),指数时间算法,：计算时间用指数函数限界的算法。,常见的指数时间限界函数,：,(2,n,) ,(n,！,) ,(,n,n,),说明,：,当,n,取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。,典型的计算时间函数曲线,定义,1.2,如果存在两个正常数,c,和,n,0,，,对于所有的,n,n,0,，有,|f(n)| c|g(n)|,则记作,f(n) =,(g(n),含义：,如果算法用,n,值不变的同一类数据在某台机器上运行时，所用的时间总是不小于,|g(n)|,的一个常数倍。所以,g(n),是计算时间,f(n),的一个,下界函数,。,f(n,),的增长至少像,g(n,),的增长那样快,试图求出,“,最大,”,的,g(n),，,使得,f(n) =,(g(n),。,2,）,下界函数,定义,1.3,如果存在正常数,c,1,，,c,2,和,n,0,，,对于所有的,n,n,0,，,有,c,1,|g(n)| |f(n)| c,2,|g(n)|,则记作,含义,：,算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：,既有,f(n) =,(g(n),，又有,f(n) =,(,g(n,),记号表明算法的运行时间有一个较准确的界,3,）,“平均情况,”,限界函数,最优算法,问题的计算时间下界为,(,f,(,n,),，,则计算时间复杂性为,O(,f,(,n,),的算法是最优算法。,例如，排序问题的计算时间下界为,(,n,log,n,),，,计算时间复杂性为,O,(,n,log,n,),的排序算法是最优算法。,第,2,章 递归与分治策略,2.1,递归的概念,直接或间接地调用自身的算法称为,递归算法,。,函数自身给出定义的函数称为,递归函数,。,基于,归纳法,的递归,基于,分治法,的递归,2.1,递归的概念,例,Fibonacci,数列,无穷数列1，1，2，3，5，8，13，21，34，55，,，称为Fibonacci数列。它可以递归地定义为：,边界条件,递归方程,第,n,个,Fibonacci,数可递归地计算如下：,int,fibonacci,(int,n),if,(n = l),int,m = (l+r)/2;,if (x =,am,) return m;,if (x ,am,) r = m-1;,else l = m+1;,return -1;,算法复杂度分析：,每执行一次算法的,while,循环， 待搜索数组的大小减少一半。因此，在最坏情况下，,while,循环被执行了,O(logn,),次。循环体内运算需要,O(1),时间，因此整个算法在最坏情况下的计算时间复杂性为,O(logn,),。,合并排序,基本思想：,将待排序元素分成大小大致相同的,2,个子集合，分别对,2,个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。,public static void,mergeSort,(Comparable,a,int,left,int,right),if,(leftright) /,至少有,2,个元素,int,i=(left+right)/2; /,取中点,mergeSort,(a, left, i);,mergeSort,(a, i+1, right);,merge,(a, b, left, i, right); /,合并到数组,b,copy,(a, b, left, right); /,复制回数组,a,复杂度分析,T(n)=,O(nlogn,),渐进意义下的最优算法,算法,消去递归的合并排序算法,输入：,具有个元素的数组,A,输出：,按递增顺序排序的数组,A,1. template ,2. void,merge_sort(Type,A,int,n),3. ,4.,int,i,s,t,= 1;,5. while (tn) ,6. s = t;t = 2 * s;i = 0;,7. while (,i+t,n) ,8. merge(A,i,i+s-1,i+t-1,t);,9. i = i + t;,10. ,11. if (,i+s,n),12. merge(A,i,i+s-1,n-1,n-i);,13. ,14. ,合并排序,算法,mergeSort,的递归过程可以消去。,初始序列,49 38 65 97 76 13 27,38 49 65 97 13 76 27,第一步,第二步,38 49 65 97 13 27 76,第三步,13 27 38 49 65 76 97,快速排序,private static void,qSort,(int,p,int,r),if,(pr) ,int,q=,partition,(p,r); /,以,ap,为基准元素将,ap:r,划分成,3,段,ap:q-1,aq,和,aq+1:r,，,使得,ap:q-1,中任何元素小于等于,aq,，,aq+1:r,中任何元素大于等于,aq,。,下标,q,在划分过程中确定。,qSort,(p,q-1); /,对左半段排序,qSort,(q+1,r); /,对右半段排序,template,int,Partition,(Type a,int,p,int,r),int,i = p, j = r + 1;,Type x=,ap,;,while (true) ,while (,a+i, x /,将,x); /,将, x,的元素交换到右边区域,if (i = j) break;,Swap(ai,aj,); ;,ap, =,aj,;,aj,= x;,return j;,快速排序,线性时间选择问题,问题描述,：给定线性集中,n,个元素和一个整数,k,要求找出这,n,个元素中第,k,小的元素，即如果将这,n,个元素依其线性序排列时，排在第,k,个位置的元素即为我们要找的元素。,当,k=1,时，即找最小元素；当,k=n,时，即找最大元素；当,k=(n+1)/2,时，称为找中位数。,线性时间选择,template,Type,RandomizedSelect,(Type,a,int,p,int,r,int,k),if (p=r) return,ap,;,int,i=,RandomizedPartition(a,p,r,),j=i-p+1;,if (k=j) return,RandomizedSelect(a,p,i,k,);,else return RandomizedSelect(a,i+1,r,k-j);,线性时间选择问题算法,上述,Partition,算法可用来求选择问题的有效解。如果划分元素,v,测定在,A,（,j,）,的位置上，则有,j-1,个元素小于或等于,A(j),且有,n-j,个,元素大于或等于,A(j),。,因此，若,kj,则第,k,小元素在,A,（,j+1:n),中，再对之进一步划分。,在最坏情况下，算法,randomizedSelect,需要,O(n,2,),计算时间,但可以证明，算法,randomizedSelect,可以在,O(n,),平均时间内找出,n,个输入元素中的第,k,小元素。,将,n,个输入元素划分成,n/5,个组，每组,5,个元素，只可能有一个组不是,5,个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共,n/5,个。,递归调用,select,来找出这,n/5,个元素的中位数。如果,n/5,是偶数，就找它的,2,个中位数中较大的一个。以这个元素作为划分基准。,线性时间选择,Type,Select,(Type,a,int,p,int,r,int,k),if (,r-p,75) ,用某个简单排序算法对数组,ap:r,排序,;,return ap+k-1;,;,for (,int,i = 0; i=(r-p-4)/5; i+ ),将,ap+5*i,至,ap+5*i+4,的第,3,小元素,与,ap+i,交换位置,;,/,找中位数的中位数，,r-p-4,即上面所说的,n-5,Type x =,Select(a, p, p+(r-p-4)/5, (r-p-4)/10);,int,i=,Partition(a,p,r, x),j=i-p+1;,if (k=j) return,Select(a,p,i,k,);,else return Select(a,i+1,r,k-j);,复杂度分析,T(n,)=,O(n,),32,基本思想,：,把求解的问题,分成许多阶段或多个子问题,，然后,按顺序求解各个子问题,。前一个子问题的解为后一个子问题的求解提供了有用的信息。在求解任何一子问题时，列出各种可能的局部解，,通过决策保留那些有可能达到最优的局部解，丢弃其他局部解,，依次解决各子问题，最后一个子问题就是问题的解。,动态规划算法,动态规划算法的两个基本要素,对于一个多阶段过程问题，最优决策是否存在，不仅依赖于该问题是否有最优子结构性质，而能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。,最优子结构性质,：,原问题的最优解包含了其子问题的最优解。,子问题重叠性质,：,每次产生的子问题并不总是新问题，有些子问题被反复计算多次。,34,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。,递归,地定义最优值。,以,自底向上,的方式计算出最优值。,根据计算最优值时得到的信息，构造最优解。,35,矩阵连乘问题,穷举法,动态规划,将矩阵连乘积 简记为,Ai:j,，这里,i,j,考察计算,Ai:j,的最优计算次序。设这个计算次序在矩阵,A,k,和,A,k+1,之间将矩阵链断开，,i,k,j,，则其相应完全加括号方式为,计算量：,Ai:k,的计算量加上,Ak+1:j,的计算量，再加上,Ai:k,和,Ak+1:j,相乘的计算量,建立递归关系,令,mij , 1i, jn,，,为计算,Ai, j,的最少数乘次数，则原问题为,m1n,。,当,i = j,时，,Ai, j,为单一矩阵，,mij = 0,；,当,i,j,时，利用最优子结构性质有：,mij =,minmik + mk+1j + p,i1,p,k,p,j,ikj,其中矩阵,A,i,，,1in,，,的维数为,p,i1,p,i,。,根据此递归式就可以直接用递归程序来实现。,消除重复的矩阵连乘算法,Void,MatrixChain(int,p,int,n,int,*m,int,*s), for (,int,i = 1; i = n; i+) mii = 0;,/,将对角线元素赋值为零，即单个矩阵计算量为,0,for (,int,r = 2; r = n; r+),for (,int,i = 1; i = n r +1; i+) ,int,j = i + r 1;,(5),mij = mi+1j + pi1*pi*pj,;,/,计算,Ai, j = Ai: i Ai+1: j,sij = i;,/,记下断点,i,(7),for (,int,k = i + 1; k j; k+) ,int,t = mik + mk+1j + pi1*pk*pj,;,/,对,ikj,逐个计算,Ai, j = Ai: k Ak+1: j,if (t mij) mij = t; sij = k;,/,记下较小的,mij,及相应的断点,k,算法时间复杂性的上界为,O(n3),39,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用,cij,记录序列和的最长公共子序列的长度。其中，,和,当,i=0,或,j=0,时，空序列是,A,和,B,的最长公共子序列。故此时,Cij,=0,。其它情况下，由最优子结构性质可建立递归关系如下：,40,计算最优值,由于在所考虑的子问题空间中，总共有,(mn,),个不同的子问题，因此，用动态规划算法,自底向上,地计算最优值能提高算法的效率。,void,LCSLength(int,m,，,int,n,，,char *x,，,char *y,，,int,*c,，,int,*b),int,i,，,j;,for (i = 1; i = m; i+) ci0 = 0;,for (i = 1; i = n; i+) c0i = 0;,for (i = 1; i = m; i+),for (j = 1; j =cij-1) ,cij,=ci-1j;,bij,=2;,else ,cij,=cij-1;,bij,=3; ,构造最长公共子序列,void,LCS(int,i,，,int,j,，,char *x,，,int,*b),if (i =0 | j=0) return;,if (,bij,= 1) LCS(i-1,，,j-1,，,x,，,b);,cout,xi,; ,else if (,bij,= 2) LCS(i-1,，,j,，,x,，,b);,else,LCS(i,，,j-1,，,x,，,b);,41,0-1,背包问题,给定,n,种物品和一背包。物品,i,的重量是,w,i,，其价值为,v,i,，背包的容量为,C,。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,0-1,背包问题是一个特殊的整数规划问题。,42,0-1,背包问题,设所给,0-1,背包问题的子问题,的最优值为,m(i,，,j),，即,m(i,，,j),是背包容量为,j,，可选择物品为,i,，,i+1,，,，,n,时,0-1,背包问题的最优值。由,0-1,背包问题的最优子结构性质，可以建立计算,m(i,，,j),的递归式如下。,43,template,void,Knapsack(Type,v,int,w,int,c,int,n, Type * m),int,jMax,=min(wn-1,c);,for(int,j=0; j=,jMax,; j+),mnj,=0;,for(int,j=,wn,; j=c; j+),nnj,=,vn,;,for(int,i=n-1; i1; i-) ,jMax,=min(wi-1,c);,for(int,j=0; j=,jMax,; j+),mij,=mi+1j;,for(int,j=,wi,; j=w1) m1c=max(m1c,m2c-w1+v1);,贪心算法,贪心算法总是作出在,当前看来最好的选择,，即所作的选择只是,局部最优选择,。,希望从,局部的最优选择,得到,整体最优解,。,采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。,贪心方法描述,量度标准,A(1),A(2),A(n),A,(1),A,(2),A,(n),S(1),S(2),这种量度意义下的部分最优解,原问题的,n,个输入,排序后的,n,个输入,A,(j),贪心算法的基本要素,贪心算法的基本要素,可用贪心算法求解的问题的基本要素,最优子结构性质,贪心选择性质,。,贪心算法的基本要素,贪心算法与动态规划算法的差异,相同点：都具有最优子结构性质,区别：动态规划算法每步所作的选择往往依赖于相关子问题的解。只有解出相关子问题才能作出选择。,贪心算法仅在当前状态下作出最好选择，即局部最优选择，但不依赖于子问题的解,贪心：,自顶向下,动态规划：,自底向上,贪心算法的基本要素,活动安排问题,已知,n,个活动,E,= 1, 2, ,n,要求使用同一资源，第,k,个活动要求的开始和结束时间为,s,k,f,k,其中,s,k,f,k,k,= 1, 2, ,n,。活动,k,与活动,j,称为相容的如果,s,k,f,j,或者,s,j,f,k,。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。,问题提出：,基本思路,在安排时应该将,结束时间早的活动,尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。,贪心准则应当是：,在未安排的活动中挑选结束时间最早的活动安排。,活动安排问题,首先将安排的,11,个活动的开始时间和结束时间按结束时间的,非减次序排列,如下：,k,1,2,3,4,5,6,7,8,9,10,11,sk,1,3,0,5,3,5,6,8,8,2,12,fk,4,5,6,7,8,9,10,11,12,13,14,活动安排问题,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,1,i,si,fi,1,1,4,2,3,5,3,0,6,4,5,7,5,3,8,6,5,9,7,6,10,8,8,11,9,8,12,10,2,13,11,12,14,2,1,3,1,4,1,4,1,4,6,1,4,7,1,4,8,1,4,8,9,1,4,8,10,1,4,8,11,1,4,8,11,活动安排问题,5,阴影长条,表示的活动是已选入集合,A,的活动，而,空白长条,表示的活动是当前正在检查相容性的活动。,52,活动安排问题,Public static void,greedySelector,(int, s,int,f ,boolean,a ),int,n=s.length-1;,a0=true;,int,j=0;,int,count=1;,for (,int,i=1;i=,fj,) ,ai,=true; j=i; count+; ,else,ai,=false;,return count;,下面给出解活动安排问题的贪心算法,GreedySelector,:,各活动的起始时间和结束时间存储于数组,s,和,f,中且按结束时间的非减序排列,53,0-1,背包问题：,给定,n,种物品和一个背包。物品,i,的重量是,W,i,，其价值为,V,i,，背包的容量为,C,。应如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,在选择装入背包的物品时，对每种物品,i,只有,2,种选择，即装入背包或不装入背包。不能将物品,i,装入背包多次，也不能只装入部分的物品,i,。,54,背包问题：,与,0-1,背包问题类似，所不同的是在选择物品,i,装入背包时，,可以选择物品,i,的一部分,，而不一定要全部装入背包，,1in,。形式化描述为：,这,2,类问题都具有,最优子结构,性质，极为相似，但背包问题可以用贪心算法求解，而,0-1,背包问题却不能用贪心算法求解。,其中,C0,为背包容量，,w,i,0,v,i,0,，,(x,1,x,2,x,n,),为最优解。,55,首先计算每种物品单位重量的价值,v,i,/,w,i,，然后，依贪心选择策略，将尽可能多的,单位重量价值最高,(,即,v,i,/,w,i,尽可大的,),的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过,C,，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。若最后一个物品不能全部装入时，仅装其一部分使背包装满即可。,具体算法可描述如下页：,用贪心算法解背包问题的基本思想：,贪心解背包问题,首先计算每种物品单位重量的价值,v,i,/,w,i,，然后，将尽可能多的单位重量价值最高的物品装入背包。,void,Knapsack(int,n, float M, float v , float w , float x ),Sort (n, v, w);/,将各种物品按单位重量价值排序,int,i;,for ( i = 1; i = n; i + ),xi, = 0;/,将解向量初始化为零,float c = M; /,是背包剩余容量初始化为,M,for ( i = 1;i = n; i + ) ,if ( ) break;,x i = 1;,c ;,if ( i c,- = w i ,x i = c / w i ,算法复杂度,该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小顺序。因此算法的计算时间上界为,O(nlogn,),。,58,单源最短路径,给定带权有向图,G =(V,E),，其中每条边的权是非负实数。另外，还给定,V,中的一个顶点，称为,源,。现在要计算从源到所有其它各顶点的,最短路径长度,。这里径路的长度是指路径上各边权之和。这个问题通常称为,单源最短路径问题,。,1,、,Dijkstra,算法基本思想,Dijkstra,算法是解单源最短路径问题的贪心算法。其,基本思想,是,:,设置顶点集合,S(,初始仅含,源,),并不断地作,贪心选择,清华大学出版社,59,单源最短路径,来扩充这个集合；一个顶点属于集合,S,当且仅当从源到该顶点的最短路径长度,已知,。,具体而言：初始时，,S,中仅含有源。设,u,是,G,的某一个顶点，把从源到,u,且中间只经过,S,中顶点的路径称为从源到,u,的特殊路径，并用数组,dist,记录,当前每个顶点,所对应的最短特殊路径长度。,Dijkstra,算法每次从,V-S,中取出具有最短特殊路长度的顶点,u,添加到,S,中，同时根据,S,中顶点的最短路径对数组,dist,作必要的修改。一旦,S,包含了,V,中所有顶点，则,dist,就记录了从源到其它所有顶点的最短路径的长度,。,清华大学出版社,v,0,v,2,v,1,v,3,v,4,v,5,20,45,50,10,15,15,20,10,35,30,3,迭代,选取,结点,S,DIST,(1),(2),(3),(4),(5),置初值,-,0,50,10,45,1,2,0,2,50,10,25,45,2,3,0,2,3,45,10,25,45,3,1,0,2,3,1,45,10,25,45,4,4,0,2,3,1,4,45,10,25,45,5,5,0,2,3,1,4,5,45,10,25,45,考虑需要哪些存储结构？,算法如何实现？,循环需要几次？,每次循环做什么工作？,首先为第一行赋初值；,循环,n-1,次；,每次根据新加进来的结点修改可以修改的路径，并选择最短的,61,最小生成树,设,G =(V,E),是无向连通带权图，即一个,网络,。,E,中每条边,(,v,w,),的权为,cvw,。如果,G,的子图,G,是一棵包含,G,的所有顶点的树，则称,G,为,G,的生成树。生成树上各边权的总和称为该生成树的,耗费,。在,G,的所有生成树中，耗费最小的生成树称为,G,的,最小生成树,。,62,最小生成树,1,、最小生成树性质,用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的,Prim,算法,和,Kruskal,算法,都可以看作是应用贪心算法设计策略的例子。尽管这,2,个算法做贪心选择的方式不同，它们都利用了下面的,最小生成树性质,：,设,G=(V,E),是连通带权图，,U,是,V,的非空真子集。如果,(,u,v),E,，且,u,U,，,v,V,-U,，且在所有这样的边中,(,即断集中,),，,(,u,v,),的权,cuv,最小，那么一定存在,G,的一棵最小生成树，它以,(,u,v,),为其中一条边。这个性质有时也称为,MST,性质,。,证明略。,63,最小生成树,Prim,算法,设,G=(V,E),是连通带权图，,V=1,2,n,。,构造,G,的最小生成树的,Prim,算法的,基本思想,是：首先置,S=1,，然后，只要,S,是,V,的真子集，就作如下的,贪心选择,：,选取满足条件,i,S,，,j,V,-S,，且,cij,最小的边，将顶点,j,添加到,S,中。这个过程一直进行到,S=V,时为止。,在这个过程中选取到的所有边恰好构成,G,的一棵,最小生成树,。,清华大学出版社,64,最小生成树,利用最小生成树性质和数学归纳法容易证明，上述算法中的,边集合,T,始终包含,G,的某棵最小生成树中的边,。因此，在算法结束时，,T,中的所有边构成,G,的一棵最小生成树。,例如,，对于右图中的带权图，按,Prim,算法,选取边的过程如下页图所示。,清华大学出版社,65,4.6,最小生成树,清华大学出版社,66,最小生成树,3,、,Kruskal,算法,Kruskal,算法构造,G,的最小生成树的,基本思想,是，首先将,G,的,n,个顶点看成,n,个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，,并按下述方法连接,2,个不同的连通分支：,当查看到第,k,条边,(,v,w,),时，如果端点,v,和,w,分别是当前,2,个不同的连通分支,T1,和,T2,中的顶点时，就用边,(,v,w,),将,T1,和,T2,连接成一个连通分支，然后继续查看第,k+1,条边；如果端点,v,和,w,在当前的同一个连通分支中，就直接再查看第,k+1,条边。这个过程一直进行到只剩下一个连通分支时为止。,清华大学出版社,67,最小生成树,例如，,对前面的连通带权图，按,Kruskal,算法顺序得到的最小生成树上的边如下图所示。,清华大学出版社,问题的解向量,：,一个,n,元式,(x1,x2,xn,),的形式。,显约束：对分量,x,i,的取值限定。,隐约束：为满足问题的解而对不同分量之间施加的约束。,解空间：,问题的解空间一般用,解空间树,（,Solution Space Trees,也称状态空间树）的方式组织,，,其中，树的根结点位于第,1,层,，表示搜索的初始状态，,第,2,层的结点表示对解向量的第一个分量做出选择后到达的状态,，,第,1,层到第,2,层的边上标出对第一个分量选择的结果，,依此类推，,从树的根结点到叶子结点的路径就构成了解空间的一个可能解。,回溯法,回溯法的基本思想,回溯法从,根结点出发,，按照,深度优先,策略,搜索（遍历）解空间树,，搜索满足约束条件的解。,初始时，根结点成为一个,活结点,，同时也称为当前的,扩展结点,。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为一个,死结点,（即不再是一个活节点）。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。,回溯法的求解过程,(1),针对所给问题，定义问题的解空间；,(2),确定易于搜索的解空间结构；,(3),深度优先搜索解空间，并在搜索中用剪枝函数避免无效搜索。,需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构。,在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为,h(n),，,则回溯法所需的计算空间通常为,O(h(n),。,而显式地存储整个解空间则需要,O(2,h(n),),或,O(h(n)!),内存空间。,回溯法的基本思想,在搜索过程中，通常采用两种策略避免无效搜索：,（,1,）用,约束条件,剪去得不到可行解的子树；,（,2,）用,限界函数,剪去得不到最优解的子树。,这两类函数统称为,剪枝函数,（,Pruning Function,）,。,在搜索至树中任一结点时，先判断该结点对应的部分解是否满足,约束条件,，或者是否超出,限界函数,的界，也就是判断该结点是否,包含,问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓,剪枝,（,Pruning,）,；,否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,子集树与排列树,当所给问题是从,n,个元素的集合,S,中找出满足某种性质的,子集,时，解空间为,子集树,。,当所给问题是从,n,个元素的集合,S,中找出满足某种性质的,排列,时，解空间为,排列树,。,遍历子集树需,O(2,n,),计算时间,遍历排列树需要,O(n!),计算时间,void,backtrack,(,int,t),if (tn) output(x);,else,for (,int,i=0;in) output(x);,else,for (,int,i=t;i,当前最优载重量,bestw,1,0,1,1,1,1,0,0,0,不满足,约束函数,1,不满足,上界函数,0,0,1,装载问题算法描述,n,集装箱数；,w,集装箱重量数组；,c,第一艘轮船载重量；,cw,在遍历结点处的当前载重量,bsetw,当前最优载重量,private static void backtrack (,int,i),/,搜索第,i,层结点,if (i n) /,到达叶结点, if (,cw,bestw,),bestw,=,cw;return,;,if (,cw,+ wi n) /,到达叶结点,更新最优解,bestx,bestw;return,;,r -= wi;,if (,cw,+ wi ,bestw,) /,搜索右子树, xi = 0;,backtrack(i + 1); ,r += wi;,复杂度分析,算法,backtrack,在最坏情况下可能需要更新当前最优解,O(2,n,),次，每次更新,bestx,需计算时间,O(n),，,从而整个算法的计算时间复杂性为,O(n2,n,),。,进一步改进算法，可降低时间复杂性为,O(2,n,),。,N-,皇后问题定义,4,皇后问题：,*,*,*,*,*,*,*,*,8,皇后问题：,1,Q,2,Q,3,Q,4,Q,5,Q,6,Q,7,Q,8,Q,1,2,3,4,5,6,7,8,经典的回溯算法，该算法的思路如下,：,依次在棋盘的每一行上摆放一个皇后。,每次摆放都要检查当前摆放是否可行。如果当前的摆放引发冲突，则把当前皇后摆放到当前行的下一列上，并重新检查冲突。,如果当前皇后在当前行的每一列上都不可摆放，则回溯到上一个皇后并且将其摆放到下一列上，并重新检查冲突。,如果所有皇后都被摆放成功，则表明成功找到一个解，记录下该解并且回溯到上一个皇后。,求解,N,后问题中的数据表示,6,5,4,3,2,1,1,2,3,4,5,6,i-j=k-l,6,5,4,3,2,1,1,2,3,4,5,6,i+j=k+l,问题分析,解向量,：,(,x,1,x,2, ,x,n,),，,xi,表示皇后,i,放在棋盘的第,i,行的第,xi,列。,显约束,：,x,i,=1,2, ,n,隐约束,：,1),不同列：,x,i,x,j,(i,j,),2),不处于同一正、反对角线：,|,i,-,j,|,|,x,i,-,x,j,|,解空间,：排列树,约束函数,：,x,i,x,j,(i,j,) and,|,i,-,j,|,|,x,i,-,x,j,|,算法描述,/place,函数测试若将皇后,k,放在,xk,列是否与前面已放置的,k-1,个皇后都不在同一列，而且都不在同一斜线上。,bool,Queen:Place(int,k),for (,int,j=1;jn) sum+;/sum,记录当前已找到的可行方案数。,else,for (,int,i=1;i=n;i+) ,xt=i;,if (Place(t) Backtrack(t+1);,N,后问题的时间复杂性,如果只要找出,N,后问题的一个解，那么这是一个求路径的问题。,求路径：只需要找到一条路径便可以得到解。设每个状态有,k,个后继，其搜索树为,K,叉树，其结点总数为,k,n+1,1,，,遍历的时间为,O(k,n,),，,这里,n,为找到解的路径长度。,N,后问题的路径深度为,n,，,可选择的后继有,n,个，所以时间复杂性为,O(n,n,),。,分支限界法的基本思想,分支限界法与回溯法,（1）求解目标：,回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,（2）搜索方式的不同：,回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,（,3,）,从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到,所需的解,或,活结点表为空,时为止。,（,2,）,每一个活结点只有,一次机会,成为扩展结点。活结点一旦成为扩展结点，就,一次性产生,其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被,舍弃,，其余儿子结点被加入活结点表中。,分支限界法的基本思想,（,1,）,以,广度优先,或以,最小耗费,（最大效益）优先的方式搜索；,常见的两种分支限界法,（1）,队列式,(,FIFO),分支限界法,按照队列,先进先出,（,FIFO）,原则选取下一个节点为扩展节点。,（2）优先队列式分支限界法,按照优先队列中,规定的优先级,选取优先级最高的节点成为当前扩展节点。,