计算机算法设计和分析总复习市公开课金奖市赛课一等奖课件

计算机算法设计与分析第1页1.1算法定义和特征1)什么是算法？

算法是求解某一特定问题一组有穷规则集合，它是由若干条指令组成有穷符号串。2）

算法五个主要特征

确定性、可实现性、输入、输出、有穷性3）

算法设计质量指标

正确性，可读性，健壮性，效率与存放量第2页算法和程序区分程序：一个计算机程序是对一个算法使用某种程序设计语言详细实现任何一个程序设计语言都能够实现任何一个算法算法有穷性意味着不是全部计算机程序都是算法第3页问题求解(ProblemSolving)证实正确性分析算法设计程序了解问题准确解或近似解选择数据结构算法设计策略设计算法第4页

普通只考虑三种情况下时间性:最坏情况、最好情况和平均情况下复杂性，分别记为Tmax(n)、Tmin(n)和Tavg(n)算法复杂性=算法所需要计算机资源=时间复杂性+空间复杂性第5页算法渐近复杂性第6页1）上界函数定义1假如存在两个正常数c和n0，对于全部n≥n0，有|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))。第7页第8页算法分类（计算时间）多项式时间算法：可用多项式（函数）对其计算时间限界算法。

常见多项式限界函数有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指数时间算法：计算时间用指数函数限界算法。

常见指数时间限界函数：

Ο(2n)<Ο(n！)<Ο(nn)说明：当n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。第9页经典计算时间函数曲线第10页定义1.2假如存在两个正常数c和n0，对于全部n≥n0，有|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）下界函数第11页定义1.3假如存在正常数c1，c2和n0，对于全部n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|则记作含义：算法在最好和最坏情况下计算时间就一个常数因子范围内而言是相同。可看作：现有f(n)=Ω(g(n))，又有f(n)=Ο(g(n))记号表明算法运行时间有一个较准确界3）“平均情况”限界函数第12页最优算法问题计算时间下界为(f(n))，则计算时间复杂性为O(f(n))算法是最优算法。比如，排序问题计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)排序算法是最优算法。第13页第2章递归与分治策略第14页2.1递归概念直接或间接地调用本身算法称为递归算法。函数本身给出定义函数称为递归函数。

基于归纳法递归基于分治法递归第15页2.1递归概念例Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它能够递归地定义为：边界条件递归方程第n个Fibonacci数可递归地计算以下：intfibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}第16页分治算法总体思想分治法设计思想是，将一个难以直接处理大问题，分割成一些规模较小相同问题，方便各个击破，分而治之。

第17页分治法适用条件分治法所能处理问题普通含有以下几个特征：该问题规模缩小到一定程度就能够轻易地处理；该问题能够分解为若干个规模较小相同问题，即该问题含有最优子结构性质利用该问题分解出子问题解能够合并为该问题解；该问题所分解出各个子问题是相互独立，即子问题之间不包含公共子问题。第18页分治法基本步骤

（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同子问题；

（2）处理：若子问题规模较小而轻易被处理则直接解，不然递归地解各个子问题；

（3）合并：将各个子问题解合并为原问题解。第19页分治法复杂性分析一个分治法将规模为n问题分成k个规模为n／k子问题去解。设分解阀值n0=1，且adhoc解规模为1问题花费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题解合并为原问题解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n问题所需计算时间，则有：经过迭代法求得方程解：第20页二分搜索技术给定已按升序排好序n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。据此轻易设计出二分搜索算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法复杂度分析：每执行一次算法while循环，待搜索数组大小降低二分之一。所以，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，所以整个算法在最坏情况下计算时间复杂性为O(logn)。第21页合并排序基本思想：将待排序元素分成大小大致相同2个子集合，分别对2个子集合进行排序，最终将排好序子集合合并成为所要求排好序集合。publicstaticvoidmergeSort(Comparablea[],intleft,intright){

if(left<right){//最少有2个元素inti=(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)渐进意义下最优算法第22页算法消去递归合并排序算法输入：含有个元素数组A[]输出：按递增次序排序数组A[]1.template<classType>2.voidmerge_sort(TypeA[],intn)3.{4.inti,s,t=1;5.while(t<n){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.}第23页合并排序算法mergeSort递归过程能够消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]第24页快速排序privatestaticvoidqSort(intp,intr){

if(p<r){intq=partition(p,r);//以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使得a[p:q-1]中任何元素小于等于a[q]，a[q+1:r]中任何元素大于等于a[q]。下标q在划分过程中确定。

qSort(p,q-1);//对左半段排序

qSort(q+1,r);//对右半段排序}}第25页template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];while(true){while(a[++i]<x&&i<r);//将<x元素交换到左边区域while(a[--j>x);//将>x元素交换到右边区域if(i>=j)break;Swap(a[i],a[j]);;}a[p]=a[j];a[j]=x;returnj;}快速排序第26页线性时间选择问题问题描述：给定线性集中n个元素和一个整数k,要求找出这n个元素中第k小元素，即假如将这n个元素依其线性序排列时，排在第k个位置元素即为我们要找元素。当k=1时，即找最小元素；当k=n时，即找最大元素；当k=(n+1)/2时，称为找中位数。第27页线性时间选择template<classType>TypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r)returna[p];inti=RandomizedPartition(a,p,r),j=i-p+1;if(k<=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}第28页线性时间选择问题算法上述Partition算法可用来求选择问题有效解。假如划分元素v测定在A（j）位置上，则有j-1个元素小于或等于A(j),且有n-j个元素大于或等于A(j)。所以，若k<j,则第k小元素在A（1：j-1)中，再对之深入划分。若k=j,则A(j)就是第k小元素若k>j,则第k小元素在A（j+1:n)中，再对之深入划分。在最坏情况下，算法randomizedSelect需要O(n2)计算时间但能够证实，算法randomizedSelect能够在O(n)平均时间内找出n个输入元素中第k小元素。第29页将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一个排序算法，将每组中元素排好序，并取出每组中位数，共n/5个。递归调用select来找出这n/5个元素中位数。假如n/5是偶数，就找它2个中位数中较大一个。以这个元素作为划分基准。线性时间选择第30页TypeSelect(Typea[],intp,intr,intk){if(r-p<75){用某个简单排序算法对数组a[p:r]排序;returna[p+k-1];};for(inti=0;i<=(r-p-4)/5;i++)将a[p+5*i]至a[p+5*i+4]第3小元素与a[p+i]交换位置;//找中位数中位数，r-p-4即上面所说n-5Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}复杂度分析T(n)=O(n)第31页32基本思想：

把求解问题分成许多阶段或多个子问题，然后按次序求解各个子问题。前一个子问题解为后一个子问题求解提供了有用信息。在求解任何一子问题时，列出各种可能局部解，经过决议保留那些有可能到达最优局部解，丢弃其它局部解，依次处理各子问题，最终一个子问题就是问题解。动态规划算法第32页动态规划算法两个基本要素对于一个多阶段过程问题，最优决议是否存在，不但依赖于该问题是否有最优子结构性质，而能否采取动态规划方法，还要看该问题子问题是否含有重合性质。最优子结构性质：原问题最优解包含了其子问题最优解。子问题重合性质：每次产生子问题并不总是新问题，有些子问题被重复计算屡次。

第33页34动态规划基本步骤找出最优解性质，并刻划其结构特征。递归地定义最优值。以自底向上方式计算出最优值。依据计算最优值时得到信息，结构最优解。第34页35矩阵连乘问题穷举法动态规划将矩阵连乘积简记为A[i:j]，这里i≤j

考查计算A[i:j]最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其对应完全加括号方式为计算量：A[i:k]计算量加上A[k+1:j]计算量，再加上A[i:k]和A[k+1:j]相乘计算量第35页建立递归关系令m[i][j],1≤i,j≤n，为计算A[i,j]最少数乘次数，则原问题为m[1][n]。当i=j时，A[i,j]为单一矩阵，m[i][j]=0；当i＜j时，利用最优子结构性质有：m[i][j]=min{m[i][k]+m[k+1][j]+pi–1pkpj}i≤k＜j其中矩阵Ai，1≤i≤n，维数为pi–1×pi。依据此递归式就能够直接用递归程序来实现。第36页消除重复矩阵连乘算法VoidMatrixChain(intp,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=0;//将对角线元素赋值为零，即单个矩阵计算量为0for(intr=2;r<=n;r++)for(inti=1;i<=n–r+1;i++){intj=i+r–1;(5)m[i][j]=m[i+1][j]+p[i–1]*p[i]*p[j];

//计算A[i,j]=A[i:i]A[i+1:j]s[i][j]=i;//记下断点i(7)for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i–1]*p[k]*p[j];

//对i<k<j,逐一计算A[i,j]=A[i:k]A[k+1:j]if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}

//记下较小m[i][j]及对应断点k

}}}算法时间复杂性上界为O(n3)第37页第38页39子问题递归结构由最长公共子序列问题最优子结构性质建立子问题最优值递归关系。用c[i][j]统计序列和最长公共子序列长度。其中，和当i=0或j=0时，空序列是A和B最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系以下：第39页40计算最优值因为在所考虑子问题空间中，总共有θ(mn)个不一样子问题，所以，用动态规划算法自底向上地计算最优值能提升算法效率。voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}结构最长公共子序列voidLCS(inti，intj，char*x，int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1，j-1，x，b);cout<<x[i];}elseif(b[i][j]==2)LCS(i-1，j，x，b);elseLCS(i，j-1，x，b);}第40页410-1背包问题给定n种物品和一背包。物品i重量是wi，其价值为vi，背包容量为C。问应怎样选择装入背包物品，使得装入背包中物品总价值最大?0-1背包问题是一个特殊整数规划问题。第41页420-1背包问题设所给0-1背包问题子问题最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题最优值。由0-1背包问题最优子结构性质，能够建立计算m(i，j)递归式以下。第42页43template<classType>voidKnapsack(Typev,intw,intc,intn,Type**m){intjMax=min(w[n]-1,c);for(intj=0;j<=jMax;j++)m[n][j]=0;for(intj=w[n];j<=c;j++)n[n][j]=v[n];for(inti=n-1;i<1;i--){jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}第43页贪心算法贪心算法总是作出在当前看来最好选择，即所作选择只是局部最优选择。希望从局部最优选择得到整体最优解。采取逐步结构最优解方法。在每个阶段，都作出一个看上去最优决议（在一定标准下）。决议一旦作出，就不可再更改。第44页贪心方法描述量度标准A(1)A(2)…A(n)A'(1)A'(2)…A'(n)S(1)S(2)…这种量度意义下部分最优解原问题n个输入排序后n个输入A'(j)贪心算法基本要素第45页贪心算法基本要素可用贪心算法求解问题基本要素

最优子结构性质贪心选择性质。

贪心算法基本要素第46页贪心算法与动态规划算法差异相同点：都含有最优子结构性质区分：动态规划算法每步所作选择往往依赖于相关子问题解。只有解出相关子问题才能作出选择。贪心算法仅在当前状态下作出最好选择，即局部最优选择，但不依赖于子问题解贪心：自顶向下动态规划：自底向上贪心算法基本要素第47页活动安排问题已知n个活动E={1,2,…,n}要求使用同一资源，第k个活动要求开始和结束时间为sk,fk,其中sk<fk,k=1,2,…,n。活动k与活动j称为相容假如sk≥

fj或者sj≥

fk。活动安排问题就是要在所给活动集合中选出最大相容活动子集。问题提出：第48页基本思绪在安排时应该将结束时间早活动尽可能往前安排，好给后面活动安排留出更多空间，从而到达安排最多活动目标。贪心准则应该是：在未安排活动中挑选结束时间最早活动安排。活动安排问题第49页首先将安排11个活动开始时间和结束时间按结束时间非减次序排列以下：k1234567891011s[k]130535688212f[k]4567891011121314活动安排问题第50页012345678910111213141isifi11423530645753865976108811981210213111214√21314141461471481489148101481114811√√√活动安排问题5

阴影长条表示活动是已选入集合A活动，而空白长条表示活动是当前正在检验相容性活动。第51页52活动安排问题PublicstaticvoidgreedySelector(int[]s,intf[],booleana[]){intn=s.length-1;a[0]=true;intj=0;intcount=1;for(inti=1;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}下面给出解活动安排问题贪心算法GreedySelector:各活动起始时间和结束时间存放于数组s和f中且按结束时间非减序排列

第52页530-1背包问题：

给定n种物品和一个背包。物品i重量是Wi，其价值为Vi，背包容量为C。应怎样选择装入背包物品，使得装入背包中物品总价值最大?

在选择装入背包物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包屡次，也不能只装入部分物品i。第53页54背包问题：

与0-1背包问题类似，所不一样是在选择物品i装入背包时，能够选择物品i一部分，而不一定要全部装入背包，1≤i≤n。形式化描述为：

这2类问题都含有最优子结构性质，极为相同，但背包问题能够用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

其中C>0为背包容量，wi>0,vi>0，(x1,x2,…,xn)为最优解。第54页55

首先计算每种物品单位重量价值vi/wi，然后，依贪心选择策略，将尽可能多单位重量价值最高(即vi/wi尽可大)物品装入背包。若将这种物品全部装入背包后，背包内物品总重量未超出C，则选择单位重量价值次高物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。若最终一个物品不能全部装入时，仅装其一部分使背包装满即可。 详细算法可描述以下页：

用贪心算法解背包问题基本思想：第55页贪心解背包问题首先计算每种物品单位重量价值vi/wi，然后，将尽可能多单位重量价值最高物品装入背包。

voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//将各种物品按单位重量价值排序inti;for(i=1;i<=n;i++)x[i]=0;//将解向量初始化为零floatc=M;//是背包剩下容量初始化为Mfor(i=1;i<=n;i++){if()break;x[i]=1;c;}if(i<=n);

}w[i]>c-=w[i]x[i]=c/w[i]第56页算法复杂度该算法主要计算时间在于将各种物品依其单位重量价值从大到小次序。所以算法计算时间上界为O(nlogn)。第57页58单源最短路径

给定带权有向图G=(V,E)，其中每条边权是非负实数。另外，还给定V中一个顶点，称为源。现在要计算从源到全部其它各顶点最短路径长度。这里径路长度是指路径上各边权之和。这个问题通常称为单源最短路径问题。

1、Dijkstra算法基本思想

Dijkstra算法是解单源最短路径问题贪心算法。其基本思想是:设置顶点集合S(初始仅含源)并不停地作贪心选择清华大学出版社第58页59单源最短路径 来扩充这个集合；一个顶点属于集合S当且仅当从源到该顶点最短路径长度已知。

详细而言：初始时，S中仅含有源。设u是G某一个顶点，把从源到u且中间只经过S中顶点路径称为从源到u特殊路径，并用数组dist统计当前每个顶点所对应最短特殊路径长度。Dijkstra算法每次从V-S中取出含有最短特殊路长度顶点u添加到S中，同时依据S中顶点最短路径对数组dist作必要修改。一旦S包含了V中全部顶点，则dist就统计了从源到其它全部顶点最短路径长度。清华大学出版社第59页v0v2v1v3v4v5204550101515201035303迭代选取结点SDIST(1)(2)(3)(4)(5)置初值--05010∞45∞120,250102545∞230,2,345102545∞310,2,3,145102545∞440,2,3,1,445102545∞550,2,3,1,4,545102545∞考虑需要哪些存放结构？算法怎样实现？循环需要几次？每次循环做什么工作？首先为第一行赋初值；循环n-1次；每次依据新加进来结点修改能够修改路径，并选择最短第60页61最小生成树

设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)权为c[v][w]。假如G子图G’是一棵包含G全部顶点树，则称G’为G生成树。生成树上各边权总和称为该生成树花费。在G全部生成树中，花费最小生成树称为G最小生成树。

第61页62最小生成树1、最小生成树性质 用贪心算法设计策略能够设计出结构最小生成树有效算法。本节介绍结构最小生成树Prim算法和Kruskal算法都能够看作是应用贪心算法设计策略例子。尽管这2个算法做贪心选择方式不一样，它们都利用了下面最小生成树性质： 设G=(V,E)是连通带权图，U是V非空真子集。假如(u,v)E，且uU，vV-U，且在全部这么边中(即断集中)，(u,v)权c[u][v]最小，那么一定存在G一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。

证实略。第62页63最小生成树Prim算法

设G=(V,E)是连通带权图，V={1,2,…,n}。 结构G最小生成树Prim算法基本思想是：首先置S={1}，然后，只要S是V真子集，就作以下贪心选择：选取满足条件iS，jV-S，且c[i][j]最小边，将顶点j添加到S中。这个过程一直进行到S=V时为止。 在这个过程中选取到全部边恰好组成G一棵最小生成树。清华大学出版社第63页64最小生成树 利用最小生成树性质和数学归纳法轻易证实，上述算法中边集合T一直包含G某棵最小生成树中边。所以，在算法结束时，T中全部边组成G一棵最小生成树。

比如，对于右图中带权图，按Prim算法选取边过程以下页图所表示。清华大学出版社第64页654.6最小生成树清华大学出版社第65页66最小生成树3、Kruskal算法

Kruskal算法结构G最小生成树基本思想是，首先将Gn个顶点看成n个孤立连通分支。将全部边按权从小到大排序。然后从第一条边开始，依边权递增次序查看每一条边，并按下述方法连接2个不一样连通分支：当查看到第k条边(v,w)时，假如端点v和w分别是当前2个不一样连通分支T1和T2中顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；假如端点v和w在当前同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。

清华大学出版社第66页67最小生成树

比如，对前面连通带权图，按Kruskal算法次序得到最小生成树上边以下列图所表示。清华大学出版社第67页问题解向量：一个n元式(x1,x2,…,xn)形式。显约束：对分量xi取值限定。隐约束：为满足问题解而对不一样分量之间施加约束。解空间：问题解空间普通用解空间树（SolutionSpaceTrees,也称状态空间树）方式组织，其中，树根结点位于第1层，表示搜索初始状态，第2层结点表示对解向量第一个分量做出选择后抵达状态，第1层到第2层边上标出对第一个分量选择结果，依这类推，从树根结点到叶子结点路径就组成了解空间一个可能解。回溯法第68页回溯法基本思想

回溯法从根结点出发，按照深度优先策略搜索（遍历）解空间树，搜索满足约束条件解。初始时，根结点成为一个活结点，同时也称为当前扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为一个新活结点，并成为当前扩展结点。假如在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为一个死结点（即不再是一个活节点）。此时，应往回移动（回溯）至最近一个活结点处，并使这个活结点成为当前扩展结点。第69页回溯法求解过程(1)针对所给问题，定义问题解空间；(2)确定易于搜索解空间结构；(3)深度优先搜索解空间，并在搜索中用剪枝函数防止无效搜索。需要注意是，问题解空间树是虚拟，并不需要在算法运行时结构一棵真正树结构。在任何时刻，算法只保留从根结点到当前扩展结点路径。假如解空间树中从根结点到叶结点最长路径长度为h(n)，则回溯法所需计算空间通常为O(h(n))。而显式地存放整个解空间则需要O(2h(n))或O(h(n)!)内存空间。第70页回溯法基本思想在搜索过程中，通常采取两种策略防止无效搜索：（1）用约束条件剪去得不到可行解子树；（2）用限界函数剪去得不到最优解子树。这两类函数统称为剪枝函数（PruningFunction）。在搜索至树中任一结点时，先判断该结点对应部分解是否满足约束条件，或者是否超出限界函数界，也就是判断该结点是否包含问题（最优）解，假如必定不包含，则跳过对以该结点为根子树搜索，即所谓剪枝（Pruning）；不然，进入以该结点为根子树，继续按照深度优先策略搜索。第71页子集树与排列树当所给问题是从n个元素集合S中找出满足某种性质子集时，解空间为子集树。

当所给问题是从n个元素集合S中找出满足某种性质排列时，解空间为排列树。第72页遍历子集树需O(2n)计算时间遍历排列树需要O(n!)计算时间voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(constraint(t)&&bound(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(constraint(t)&&bound(t))

backtrack(t+1);swap(x[t],x[i]);}}5.1.5子集树与排列树//更换排列次序

当前第一个元素和下面交换

//搜索完成后恢复

第73页装载问题问题定义有一批共n个集装箱要装上2艘载重量分别为c1和c2轮船，其中集装箱i重量为wi，且∑wi≤c1+c2装载问题要求确定是否有一个合理装载方案可将这n个集装箱装上这2艘轮船。假如有，找出一个装载方案。第74页问题分析假如一个给定装载问题有解，则采取下面策略可得到最优装载方案：(1)首先将第一艘轮船尽可能装满；(2)将剩下集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱一个子集，使该子集中集装箱重量之和最靠近c1。由此可知，装载问题等价于以下特殊0-1背包问题。第75页算法设计解空间：子集树可行性约束函数(选择当前元素)：上界函数(不选择当前元素)：当前载重量cw+剩下集装箱重量r>当前最优载重量bestw101111000不满足约束函数1不满足上界函数001第76页装载问题算法描述n集装箱数；w[]集装箱重量数组；c第一艘轮船载重量；cw在遍历结点处当前载重量bsetw当前最优载重量privatestaticvoidbacktrack(inti){//搜索第i层结点if(i>n)//抵达叶结点{if(cw>bestw)bestw=cw;return;}if(cw+w[i]<=c){//搜索左子树x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}x[i]=0;//搜索右子树backtrack(i+1);}}解空间：子集树可行性约束函数(选择当前元素)：第77页引入上界函数算法描述

当前载重量cw+剩下集装箱重量r当前最优载重量bestwvoidbacktrack(inti){//搜索第i层结点if(i>n)//抵达叶结点更新最优解bestx,bestw;return;r-=w[i];if(cw+w[i]<=c)//搜索左子树{x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+r>bestw)//搜索右子树{x[i]=0;backtrack(i+1);