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