递归算法的优缺点

递归算法的优缺点：○1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。边界条件与递归方程是递归函数的二个要素应用分治法的两个前提是问题的可分性和解的可归并性以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。舍伍德算法设计的基本思想:设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有拉斯维加斯(LasVegas)算法的基本思想:设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有：解此方程可得：蒙特卡罗(MonteCarlo)算法的基本思想:设p是一个实数，且1/2p1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。单纯形算法的特点是：（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；（2）一般经过不大于m或n次迭代就可求得最优解。单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问nXxnAAXxtnt||/)()()()(ntxtAA)()()(nsntxtAB))()())((1()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt题完全等价的标准线性规划问题。图灵机由以下几部分组成：一条无限长的带（有无穷个格子）、一个读写头、一个有限状态控制器以及一个程序。NPC形式化定义：定义1：语言L是NP完全的当且仅当（1）L【NP；（2）对于所有L’【NP有L’～pL。如果有一个语言L满足上述性质(2),但不一定满足性质（1），则称该语言是NP难的。所有NP完全语言构成的语言类称为NP完全语言类，就是NPC。定理1设L是NP完全的，则（1）当且仅当P＝NP；（2）若，且，则L1是NP完全的。团问题:任给图G和整数k．试判定图G中是否存在具有k个顶点的团？1)团问题。显然，验证G的一个子图是否成团只需多项式时间即可。团问题。任给表达式f．构造一个相应的图G如下：①图G的每个顶点对应于f中的每个文字(多次出现的重复计算)。②若G中两个顶点其原对应的文字不相互补且不出现于同一于句中，则将其连线。设f有n个子句，则f可满足当且仅当f对应的图G中有n个顶点的团。这是因为：(a)若f可满足，即有某种赋值使得f取值为真，它等价于使得每个ci中都至少有一个文字为真，这n个文字(每个ci(1＜in)中一个)对应的图G中的n个顶点就构成一个团。(b)若图G中有一n个顶点的团，则取给出使得这n个顶点对应的文字都为真的赋值，则f的取值为真(这由图G的定义易证)。显见，上述构造图G的方法是多项式界的，因此SAT团问题。由(a)、(b)有，团问题。证毕。单源最短路径问题:voidshortestpaths(v){MinHeapH[1000];//定义最小堆MinHeapNodetypeE;E.i=v;E.length=0;Dist[v]=0;//搜索问题界空间while(true){for(j=1;j=n;j++)if((c[E.i][j]inf)&&(E.length+c[E.i][j]dist[j])){dist[j]=E.length+c[E.i][j];prev[j]=E.i;//加入活结点优先队列MinHeapNodetypeN;N.i=j;N.length=dist[j];H.Insert(N);}//取下一个扩展结点try{H.DeleteMin(E);}//优先队列为空catch(OutOfBounds){break;}}}(1)数值随机化算法:求解数值问题,得到近似解(2)MonteCarlo算法:问题准确性,但却无法确定解正确性(3)LasVegas算法:获得正确解,但存在找不到解的可能性(4)Sherwood算法:保证能获得正确解旅行售货员问题:(优先队列式分支限界法)TypeTravding(intv[]){MinHeapNodeH(1000)；TypeMinout[N+1]；//计算Minout[i]=顶点i的最小出边费用TypeMinsurn=0；//最小出边费用和for（i=1;i＜＝n；i++）{Min=NoEdge；for（j=1；j＜＝n；j++）if（a[i][j]!=NoEdge＆＆(a[i][j]Min||Min==NoEdge)Min=a[i][j]；if（Min==NoEdge）return(NoEdge)；//无回路MinOut[i]=Min；MinSum+=Min；}//初始化MinHeapNodeE；for（i=0；i＜n；i++）E.x［i］=i+1；E.s=0；E.cc=0；E.rcost=MinSum；Bestc=NoEdge；while（E.s＜n-1)//非叶结点if（E.sn-1）{//当前扩展结点是叶结点的父结点if（a[E.x[n-2][E.x[n-1]]!=NoEdge＆＆a[E.x[n-2][1]!=NoEdge&&（E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]bestc||bestc==NoEdge）{//费用更小的回路bestc=Ecc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]；E.c＝bestc；E.lcost=bestc；E.s++；Insert（H,E）；}elsedelete(E.x)；}//舍弃扩展结点else{//产生当前扩展结点的儿子结点for（i＝E.s+1；i＜n；i++＝if（a[E.x[E.s]][E.x[i]]!=NoEdge）{//可行儿子结点Typecc＝E.cc+a[E.x[E.s]][E.x[i]]；Typercost=E.rcost-MinOut[E.x[E.s]]；Typeb=cc+rcost；//下界if（b＜bestc||bestc==NoEdge){//子树可能含最优解for（j=0；j＜n；j++)N.x[j]=E.x[j]；N.x[E.s+1]=E.x[i]；N.x[i]=E.x[E.s+1]；N.cc=cc；N.s=E.s+1；N.lcost=b；N.rcost＝rcost；Insert（H,N）；}}delete(H,E.x)；}//完成结点扩展DeleteMin(H,E)；}//取下一扩展结点if(堆已空)break；//堆已空}if（bestc==NoEdge）return(NoEdge)；//无回路//将最优解复制到v[l：n]for（i=0；i＜n；i++)v[i+1]=E.x[i]；while(true){//释放最小堆中所有结点delete(H,E.x)；DeleteMin(H,E)；}//取下一扩展结点if(堆已空)break；//堆已空}return(bestc)；}回溯算法解批处理作业调度(解空间：排列树):voidFlowshop::Backtrack(inti){if(in){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(fbestf){Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);}f1-=M[x[j]][1];f-=f2[i];}}所以在最坏的情况下，整个算法的计算时间复杂性为O(n!)回溯算法解0-1背包问题(解空间：子集树):templateclassTypew,classTypepTypepKnapTypew,Typep::Bound(inti){//计算上界Typewcleft=c-cw;//剩余容量Typepb=cp;//以物品单位重量价值递减序装入物品while(i=n&&w[i]=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i=n)b+=p[i]/w[i]*cleft;returnb;}voidbacktrack(i){if(in){bestp=cp;return;}if(cw+w[i]=c)//x[i]=1{cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}if(bound(i+1)bestp)backtrack(i+1);//x[i]=0}由于上界函数Bound()需要O(n)的时间，在最坏的情况下有O(2n)个右儿子结点需要计算上界函数，所以0-1背包问题的回溯算法Backtrack()所需要的时间是O(n2n)。回溯算法解图的m着色问题:voidColor::Backtrack(intt){if(tn){sum++;for(inti=1;i=n;i++)coutx[i]'';coutendl;}elsefor(inti=1;i=m;i++){x[t]=i;if(Ok(t))Backtrack(t+1);}}boolColor::Ok(intk){//检查颜色可用性for(intj=1;j=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}回溯法总的时间耗费是O(m^n*n)回溯算法解最大团问题（解空间：子集树）：voidClique::Backtrack(inti){//计算最大团if(in){//到达叶结点for(intj=1;j=n;j++)bestx[j]=x[j];bestn=cn;return;}//检查顶点i与当前团的连接intOK=1;for(intj=1;ji;j++)if(x[j]&&a[i][j]==0){//i与j不相连OK=0;break;}if(OK){//进入左子树x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-ibestn){//进入右子树x[i]=0;Backtrack(i+1);}}解最大团问题的回溯算法Backtrack所需的计算时间为O(n2n)。回溯法的基本思想是：不断用修改过的判定函数Pi只(x1,x2,…,xi)(亦称为限界函数)去测试正在构造中的n元组的部分向量(x1,x2,…,xn)．看其是否可能导致最优解。如果判定(x1，x2，…，xn)不可能导致最优解，那么就不再测试可能要测试的mi+1mi+2...mn个向量。解符号三角形问题的回溯算法Backtrack所需的计算时间为O(n2n)。贪心法解最优装载问题：templateclassTypevoidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(in