算法设计复习资料

递归：直接或间接的调用自身算法称为递归算法；用函数自身给出定义的函数称为递归函数。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法（divide-and-conquer）的基本思想：A分割成k个更小规模的子问题。B对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。C将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。设计动态规划算法的步骤（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。最优子结构性质：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质贪心算法：贪心算法总是作出在当前看来最好的选择，它并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。贪心算法：贪心算法求解的这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质贪心算法与动态规划算法的差异：贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？单源最短路径基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。回溯法的基本思想：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常见的两种分支限界法：（1）队列式（FIFO）分支限界法。按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法。按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。布线问题算法思想：解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2,并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。随机存储机RAM它描述的形式计算机是一台带累加器计算机，他不允许程序修改其自身，RAM由只读输入带、只写输入带、程序存储部件、内存储器和指令计数器5个部分组成。P类和NP类语言的定义P={L|L是一个能在多项式时间内被一台DTM所接受的一眼}NP+{L|L是一个能在多项式时间内被一台NDTM所接受的语言}由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被非确定性图灵机接受。故P属于NPP类问题:是确定性计算模型下的易解问题类。NP类问题：是非确定性计算模型下的易验证问题类。NP完全类问题：即多项式复杂度的非确定性问题类；简单的写法是NP=P?问题就在这个问号上，到底是NP等于P,还是NP不等于P。算法的渐进时间复杂性的含义？答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。最坏情况下的时间复杂性和平均时间复杂性有什么不同？答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n)=max{T(n，I)},lUDnA(n)=EP(l)T(n，I)lUDn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：釆用回溯法求解的问题，其解如何表示？有什么规定？问题的解可以表示为n元组：(x,x, x)，xeS,S为有穷集合，xeS, (x,x, x)具备1 2 n i ii i i 1 2 n完备性，即(x,x, X)是合理的，贝I」(x,x, x)(i〈n)—定合理。12 n 12 i简述渐进时间复杂性上界的定义。T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n)〈f(n)，这种关系记作T(n)=0(f(n))。快速排序的基本思想是什么。快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。什么是直接递归和间接递归？消除递归一般要用到什么数据结构？在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P,这个称为间接递归。消除递归一般要用到栈这种数据结构。哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%〜90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。二、递归与分治：二分搜索算法：publicstaticintbinarySearch(inta[],intx,intn){left二0; right二n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left二middle+1;elseright二middle-1;}return-1; }棋盘覆盖publicvoidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt二tile++.s=size/2;if(dr<tr+s&&de<tc+s)chessBoard(tr,tc,dr,de,s);else{board]tr+s-l][tc+s-1]=t;chessBoard(tr,tc,tr+sT,tc+sT,s);}if(dr<tr+s&&dc>=tc+s)chessBoard(tr,tc+s,dr,dc,s);else{ board[tr+s-l][tc+s]=t;chessBoard(tr,tc+s,tr+sT,tc+s,s);}if(dr>=tr+s&&dc<tc+s)chessBoard(tr+s,tc,dr,dc,s);else{ board[tr+s][tc+s-1]=t;chessBoard(tr+s,tc,tr+s,tc+sT,s);}if(dr>=tr+s&&dc>=tc+s)chessBoard(tr+s,tc+s,dr,dc,s);else{ board[tr+s][tc+s]=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}三、动态规划最长公共子序列voidLCSLength(intm,intn,char[]x,char[]y,int[][]c,int[][]b){inti,j;TOC\o"1-5"\h\zfor(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-l][j-l]+l;b[i][j]=1;}elseif(c[iT][j]〉=c[i][j—l]){ c[i][j]=c[iT][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(iT,j,x,b);elseLCS(i,j—1,x,b); }最优装载voidLoading(intx[],Typew[],Typec,intn){int*t二newint[n+1];Sort(w,t,n);for(inti二1;i〈二n;i++)x[i]=0;for(inti二1;i〈二n&&w[t[i]]〈二c;i++){x[t[i]]=1;c—二w[t[i]];}}五、回溯法装载问题voidbacktrack(inti){if(i>n)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); }r+=w[i];}批处理问题：voidFlowshop::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestf二f;}elsefor(intj二i;j〈二n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]〉f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(f<bestf){Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);} f1-=M[x[j]][1];f-=f2[i];}}六、分支限界法单源最短路径问题while(true){for(intj=1;j<=n;j++)if((c[E.i][j]〈inf)&&(E.length+c[E.i][j]〈dist[j])){//顶点i到顶点j可达，且满足控制约束dist[j]=E.length+c[E.i][j];prev[j]=E.i;MinHeapNode〈Type〉N;N.i=j;N.length二dist[j];H.Insert(N);}try{H.DeleteMin(E);}catch(OutOfBounds){break;} }}求证：O(f(n))+O(g(n))=O(max{f(n),g(n)})。证明：对于任意f1(n)eO(f(n))，存在正常数cl和自然数nl,使得对所有n>n1，有f1(n)<clf(n)。类似地，对于任意gl(n)eO(g(n))，存在正常数c2和自然数n2，使得对所有n>n2，有gl(n)<c2g(n)。令c3=max{cl,c2}，n3=max{nl,n2}，h(n)=max{f(n),g(n)}。则对所有的n>n3，有fl(n)+gl(n)<clf(n)+c2g(n)<c3f(n)+c3g(n)=c3(f(n)+g(n))

<c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).装载问题贪心算法的证明比如所你是按每次装入重量最小的作为贪心的选择，那么设重量从小到大(x1,x2,...,xn)是最优装载问题的一个最优解。设k=min{i|xi=1}.当k=1的时候(x1,x2,...,xn)是一个满足贪心性质的最优解。当k>1，令y=1，yk=O,yi=xi,i不等于k,那么yi与对应重量wi的乘积的和=w1-wk+wixi乘积的和，这个是小于等于本身wi*xi乘积的和的，小于容量c因此，(y1,y2,...,yn)也是最优装载问题的可行解。然而，xi的和与yi的和是相等的，也就是说，(y1,y2,...,yn)也是满组贪心性质的最优解。矛盾。7.最长公共子序列问题：给定2个序列X二{xl,x2,…,xm}和Y二{yl,y2,…,yn}，找出X和Y的最长公共子序列。由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用

]记录序列Xi和YJ的最长公共子序列的长度。其中，Xi={xl,x2,…,xi}；Yj二{yl,y2,…,yj}。当i=0或j=0时，空序列是Xi和YJ的最长公共子序列。故此时C[i][j]=0o其它情况下，由最优子结构性质可建立递归关系如下：' 0 i=0,j=0c[i][j]=< c[i-l][j—1]+1 i,j>0；x=yijmax{c[i][j-1],c[i-1][j]}i,j>0;x丰yJ ij在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。请填写程序中的空格，以使函数LCSLength完成计算最优值的功能。voidLCSLength(intm,voidLCSLength(intm,intn,char*x,char*y,int**c,int**b)inti,j;for(i=1;i<=m;i++)c[i][0]for(i=1;i<=n;i++)c[0][i]for(i=1;i<=m;i++)for(j=1::j<=n;j++){=0;=0;if(x[i]==y[j]){c[i][j]=c[i-l][j-l]+l;b[i][j]=l;}elseif(c[i-l][j]>=c[i][j-l]){c[i][j]=c[i-l][j];b[i][j]=2;}else{c[i][j]=c[i][j-l];b[i][j]=3;}}(1)函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填写程序中的空格，以使函数LCS完成构造最长公共子序列的功能(请将b[i][j]的取值与(1)中您填写的取值对应，否则视为错误)。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(iT,j，x，b);elseLCS(i，j-1，x，b);}1、⑴原理：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优I贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。(2)特性：贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质。贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质刃最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。⑶贪心算法与动态规划算法的差异动态规划和贪心算法都是一种递推算法，均有最优子结构性质，通过局部最优解来推导全局最优解。两者之间的区别在于：贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。动态规划算法中全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。阎基本思路：1） 建立数学模型来描述问题。2） 把求解的问题分成若干个子问题。3） 对每一子问题求解，得到子问题的局部最优解。4） 把子问题的解局部最优解合成原来解问题的一个解。2、活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。问题描述T设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fio如果选择了活动i,则它在半开时间区间［si,fi）内占用资源。若区间［si,fi）与区间［sj,fj）不相交，则称活动i与活动j是相容的。也就是说，当si^fj或sj^fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。求解思路：将活动按照结束时间进行从小到大排序。然后用i代表第i个活动，s［i］代表第i个活动开始时间，f［i］代表第i个活动的结束时间。按照从小到大排序,挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。事实上系统一次检查活动i是否与当前已选择的所有活动相容。若相容活动i加入已选择活动的集合中，否则，不选择活动i,而继续下一活动与集合A中活动的相容性。若活动i与之相容，则i成为最近加入集合A的活动，并取代活动j的位置。下面给出求解活动安排问题的贪心算法，各活动的起始时间和结束时间存储于数组s和f中，且按结束时间的非减序排列。如果所给的活动未按此序排列，可以用O（nlogn）的时间重排。具体代码如下：〃4dl活动安排问题贪心算法#include"stdafx.h"#includeviostream>usingnamespacestd;templatevclassType〉voidGreedySelector(intn,Types[],Typef[],boolA[]);constintN=11;intmain(){〃下标从1开始，存储活动开始时间ints[]={0,1,3,0,5,3,5,6,8,8,2,12};〃下标从1开始，存储活动结束时间intf[]={0,4,5,6,7,8,9,10,11,12,13,14};boolA[N+1];coutvv"各活动的开始时间，结束时间分别为："vvendl;for(inti=1;iv=N;i++){coutv<"["<<ivv"]:"vv"("vvs[i]vv","vvf[i]vv")"vvendl;}GreedySelector(N,s,f,A);coutvv"最大相容活动子集为："vvendl;for(inti=1;iv=N;i++){if(A[i]){coutvv"["vvivv"]:"vv"("vvs[i]vv","vvf[i]vv")"vvendl;}}return0;}templatevclassType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;〃记录最近一次加入A中的活动for(inti=2;iv=n;i++)〃依次检查活动i是否与当前已选择的活动相容{if(s[i]>=f[j]){A[i]=true;j=i；}else{A[i]=false;}}}回溯法分配工作#includevstdio.h>#includevmath.h>/*名称：swap功能：交换两个整数输入：输出：作者：刘荣时间：2013/5/17备注：*/voidswap(int&x,int&y){inttemp=x;x=y;y=temp;}/*名称：next功能：递归求解最优方案输入：输出：作者：刘荣时间：2013/5/17备注:*/voidnext(inti,intn,intc[][3],int*x,int&bestv,int*bestx){intj,v;if(i>n)〃到达叶子节点{v=0;for(intk=l;k<=n;k++){v+=c[k-1][x[k-1]];}if(v<bestv){bestv=v;for(intk=1;k<=n;k++){bestx[k-1]=x[k-1];〃记录下最有方案}}return;}〃组合排列for(j=i;j<=n;j++){swap(x[i-1],x[j-1]);next(i+1,n,c,x,bestv,bestx);swap(x[i-1],x[j-1]);}}/*名称：solve功能：开始求解，包括初始化输入：输出：作者：刘荣时间：2013/5/17备注:*/voidsolve(intn,intc[][3],int*bestx,int&bestv){inti;int*x=newint[n];for(i=1;i<=n;i++){x[i-1]=i-1;}bestv=0;for(i=1;i<=n;i++){bestv+=c[i-l][i-l];}next(1,n,c,x,bestv,bestx);}intmain(){intn=3;intc[][3]={{10,2,3},{2,3,4},{3,4,5}};int*bestx=newint[n];intbestv=0;solve(n,c,bestx,bestv);printf("最优工作安排的时间:％d\n\r",bestv);printf(”最优工作安排：\n\r");for(inti=1;i<=n;i++){printf("工作％小:第％小个人，”,i,bestx[i-1]+1);}return0;亘溯法对艇空间作深度优先搜索，因此，在一般情况下用递归方法实现叵溯法[cpp]口面01.voidbackt-ack(intt)02・03.if(t>n)04.CUtpLlt(K)；"已到叶子结点，输出结果阪else06.for(inti=f(n^t);i<=g(njt);i++){尊厂x[t]=h(i);if(ccn5t-aint(t)&.aboLind(t))backt-ack(t+l);10.>11.}f(n,t),g(n;t):表示刍前扩展结点处未搜索过的子树的起始编亏和终止编号h(i)：表袞在刍前扩展结点处刈t］的第i个可选值；迭找回濛:采用树的非递归深度忧先遍历算法，可将回溯法表看为一个非递归迭代过程:[cpp]B③02.03.64.05.06.&7.施.02.03.64.05.06.&7.施.09.10.intt=l;while(t>0)-[if(f(nJt)<=g(nJt))for(inti=f(n±t};i<=gtn±t};i++}■[x[t]=h(i);if(constraint(t>fi&baund(t}}{if(solution(t>)output(x);elset++;4.15.子集松刍所给的问题是城门个元素的集合S丰找Hi®己某种性质的子集时，相应的解空间称为子集如例如，那个物品的CM背包问题所相应的解空间树就是一颗子集树：迄类子集问题通常有2饷个叶节点，其节点总个数为2A(n+1)-1.遍历子集树的任何算法均需要0(才n)的计算时间：01.02.01.02.03.@4.05.06.07.08.09.用回溯法遍历子集树的一般算法可描述如下:[cpp]口©voidbacktrack,(intt){if(t>n)output(x);elsefor(inti=0;i<=l;i++){if(legal(t))backtrack(t+]L);}排列孙当所绐问题是确定n个元素满足杲种性质的排列时，相应的解空间树称为切松排列树适常有n!个叶子节点.因此遍历排列树需要0(n!)的计算时间.01.01.02.03.04.05.06.07.08.09.何用回溯法遍历排列树的一般算法可描述如下:[cpp]口③voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t]±x[i]);if(legal(t))backtra匚k(1:+]L);swap(x[t]±x[i]);迭代回溯算法设计:用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。用可科VWiXi<Cl行性约束函数可剪去不满足约束条件二 的子树。在子集树的第j+1乞yvxi层的结点z处，用CW记当前的装载重量，即cw==，则当cw>c1时，以结点z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。(该约束函数去除不可行解，得到所有可行)。可以引入一个上界函数，用于剪去不含最优解的子树从而改进算法在平均情况下的运行效率。设z是解空间树第i层上的当前扩展结点。cw是当前载重量；bestw是当前最优载重量；r是剩余集装箱的重量，即r=「」 。定义上界函数为cw+r。在以z为根的子树中任一叶结点所相应的载重量均不超过cw+r。因此，当cw+r<=bestw时，可将z的右子树剪去。#include"stdafx.h"#includeviostream>usingnamespacestd;templatevclassType〉TypeMaxLoading(Typew[],Typec,intn,intbestx[]);intmain(){intn=3,m;intc=50,c2=50;intw[4]={0,10,40,40};intbestx[4];m=MaxLoading(w,c,n,bestx);coutvv"轮船的载重量分别为："vvendl;coutvv"c(l)="vvcvv",c(2)="vvc2vvendl;coutvv"待装集装箱重量分别为："vvendl;coutvv"w(i)=";for(inti=1;iv=n;i++){coutvvw[i]vv"";}coutvvendl;coutvv"回溯选择结果