递归算法的优缺点

1、递归算法的优缺点：优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。边界条件与递归方程是递归函数的二个要素应用分治法的两个前提是问题的可分性和解的可归并性以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。舍伍德算法设计的基本思想:设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模

2、为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在xXn使得 的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有拉斯维加斯( Las Vegas )算法的基本思想:设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有：解此方程可得： 蒙特卡罗(Monte Carlo)算法的基本思想:设p是一个实数，且1/2&l

3、t;p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。单纯形算法的特点是：（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；（2）一般经过不大于m或n次迭代就可求得最优解。单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完

4、全等价的标准线性规划问题。图灵机由以下几部分组成：一条无限长的带（有无穷个格子）、一个读写头、一个有限状态控制器以及一个程序。NPC形式化定义：定义1：语言L是NP完全的当且仅当（1） L【NP；（2）对于所有L【NP有L pL。 如果有一个语言L满足上述性质(2),但不一定满足性质（1），则称该语言是NP难的。所有NP完全语言构成的语言类称为NP完全语言类，就是NPC。定理1 设L是NP完全的，则（1）LÎP当且仅当PNP；（2）若 L µp L1，且 L1Î NP，则L1是NP完全的。团问题: 任给图G和整数k试判定图G中是否存在具有k个顶点的团？ 1)团问题

5、ÎNP。显然，验证G的一个子图是否成团只需多项式时间即可。 2)SATµ团问题。 任给表达式f构造一个相应的图G如下：图G的每个顶点对应于f中的每个文字(多次出现的重复计算)。若G中两个顶点其原对应的文字不相互补且不出现于同一于句中，则将其连线。 设f有n个子句，则f可满足当且仅当f对应的图G中有n个顶点的团。 这是因为：(a) 若f可满足，即有某种赋值使得f取值为真，它等价于使得每个ci中都至少有一个文字为真，这n个文字(每个ci(1i<n)中一个)对应的图G中的n个顶点就构成一个团。(b)若图G中有一n个顶点的团，则取给出使得这n个顶点对应的文字都为真的赋值，则f

6、的取值为真(这由图G的定义易证)。显见，上述构造图G的方法是多项式界的，因此SAT 团问题。由(a)、(b)有，团问题ÎNPC。证毕。单源最短路径问题:void shortestpaths(v) MinHeap H1000; /定义最小堆MinHeapNode<type> E;E.i=v;E.length=0;Distv=0;/搜索问题界空间while(true) for(j=1;j<=n;j+)if(cE.ij<inf)&& (E.length+cE.ij<distj) distj=E.length+cE.ij; prevj=E.i;

7、/加入活结点优先队列 MinHeapNode <type> N;N.i=j; N.length=distj; H.Insert(N); /取下一个扩展结点 try H.DeleteMin(E); /优先队列为空 catch (OutOfBounds) break;(1)数值随机化算法: ß求解数值问题,得到近似解(2)Monte Carlo算法:ß 问题准确性,但却无法确定解正确性(3)Las Vegas算法:ß获得正确解,但存在找不到解的可能性(4)Sherwood算法:ß保证能获得正确解旅行售货员问题:(优先队列式分支限界法) Type

8、Travding (int v) MinHeapNode H(1000)； Type MinoutN+1； /计算 Minouti=顶点 i的最小出边费用 Type Minsurn=0；/最小出边费用和for（i=1;in；i+） Min=NoEdge； for（ j=1；jn；j+） if（aij!=NoEdge(aij<Min | Min=NoEdge) Min=aij； if（Min=NoEdge） return(NoEdge)； /无回路 MinOuti= Min； MinSum+=Min； /初始化 MinHeapNode E； for（i= 0；i n；i+） E.xi= i

9、+ 1； E.s=0； E.cc=0； E.rcost=MinSum； Bestc=NoEdge； while（E.sn-1) /非叶结点if（E.s<n-1） /当前扩展结点是叶结点的父结点 if（aE.xn-2E.xn-1!=NoEdge aE.xn-21!=NoEdge&&（E.cc+aE.xn-2E.xn-1+aE.xn-11<bestc | bestc=NoEdge） /费用更小的回路 bestc=Ecc+aE.xn-2E.xn-1 +aE.xn-11； E.cbestc； E.lcost=bestc； E.s+； Insert（H,E）； else de

10、lete(E.x) ； /舍弃扩展结点 else /产生当前扩展结点的儿子结点 for（ iE.s+1；in；i+ if（aE.xE.sE.xi!=NoEdge） /可行儿子结点 Type ccE.cc+aE.xE.sE.xi； Type rcost=E.rcost-MinOutE.xE.s； Type b=cc+rcost； /下界if（b bestc|bestc= NoEdge ) /子树可能含最优解 for（j= 0； j n； j+) N.xj=E.xj； N.xE.s+1=E.xi； N.xi=E.xE.s+1； N.cc=cc； N.s= E.s+1；N.lcost=b； N.rc

11、ostrcost； Insert（H,N）； delete(H,E.x)；/完成结点扩展DeleteMin(H,E)； /取下一扩展结点 if (堆已空) break； /堆已空 if（bestc=NoEdge）return( NoEdge)； /无回路/将最优解复制到vl：nfor（i=0；in；i+) vi+ 1=E.xi；while (true) /释放最小堆中所有结点 delete(H, E. x)； DeleteMin(H,E)； /取下一扩展结点 if (堆已空) break； /堆已空 return(bestc)；回溯算法解批处理作业调度(解空间：排列树):void Flowsh

12、op:Backtrack(int i) if (i > n) for (int j = 1; j <= n; j+) bestxj = xj; bestf = f; else for (int j = i; j <= n; j+) f1+=Mxj1; f2i=(f2i-1>f1)?f2i-1:f1)+Mxj2; f+=f2i; if (f < bestf) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj); f1- =Mxj1; f- =f2i; 所以在最坏的情况下，整个算法的计算时间复杂性为O(n!)回溯算法解0-1背包问题(

13、解空间：子集树):template<class Typew, class Typep>Typep Knap<Typew, Typep>:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i <= n && wi <= cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i <= n) b += pi/wi * cleft; return b;void backtrack(i)

14、if( i>n ) bestp=cp; return; if(cw+wi<=c)/xi=1 cw+=wi ;cp+=pi; backtrack(i+1); cw-=wi ;cp-=pi; if ( bound(i+1)>bestp ) backtrack(i+1); /xi=0由于上界函数Bound()需要O(n)的时间，在最坏的情况下有O(2n)个右儿子结点需要计算上界函数，所以0-1背包问题的回溯算法Backtrack()所需要的时间是O(n2n)。回溯算法解图的m着色问题:void Color:Backtrack(int t) if (t>n) sum+; for

15、 (int i=1; i<=n; i+) cout << xi << ' ' cout << endl; else for (int i=1;i<=m;i+) xt=i; if (Ok(t) Backtrack(t+1); bool Color:Ok(int k)/ 检查颜色可用性 for (int j=1;j<=n;j+) if (akj=1)&&(xj=xk) return false; return true;回溯法总的时间耗费是O(mn *n)回溯算法解最大团问题（解空间：子集树）：void Cliq

16、ue:Backtrack(int i)/ 计算最大团 if (i > n) / 到达叶结点 for (int j = 1; j <= n; j+) bestxj = xj; bestn = cn; return; / 检查顶点 i 与当前团的连接 int OK = 1; for (int j = 1; j < i; j+) if (xj && aij = 0) / i与j不相连 OK = 0; break; if (OK) / 进入左子树 xi = 1; cn+; Backtrack(i+1); xi = 0; cn-; if (cn + n - i >

17、 bestn) / 进入右子树 xi = 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)。  贪心法解最优装载问题：template<class Type>void Loadin

18、g(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); for (int i = 1; i <= n; i+) xi = 0; for (int i = 1; i <= n && wti <= c; i+) xti = 1; c -= wti;算法所需的计算时间为 O(nlogn)算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入 (2)输出 (3)确定性 (4)有限性：问题的计算时间下界为W(f(n)，则计算时间复杂性为O(f(n)的算法是最优

19、算法。1. 什么是动态规划法：将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。2. 什么是贪心法：从问题某一初始或推测值出发，一步步的攀登给定目标，尽可能快的去逼近更好的解，当达到某一步不能继续时终止。3. 什么是分支定界法：对有约束条件的最优化问题所有可行解定向、适当地进行搜索。将可行解空间不断地划分为越来越小的子集（分支），并为每一个子集的解计算一个上界和下界（定界）。5、什么是NP类问题：NP=L|L是一个能在多项式时间内被一台NDTM图灵机所接受的语言，其中NDTM是非确定性图灵机。或者可说：NP是所有可在多项式时间内用不确定的算法

20、求解的判定问题的集合。对于NP类，相当于要求验证模块在多项式时间内完成对应NDTM，有非确定性算法。1. 算法的分类：1）(数值算法 ) 2） 非数值算法2. 算法的描述：1）自然语言描述 2）(流程图描述) 3）程序语言描述3. 算法的分析标准：1） 时空观念 2 ）(发展观念) 3） 设计观点 4） 交流的观点设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。动态规划法求矩阵连乘问题：void MatrixChain(int *p，int n，int *m，int *s

21、)for (int i = 1; i <= n; i+) mii = 0; for (int r = 2; r <= n; r+) for (int i = 1; i <= n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k < j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t < mij) mij = t; sij = k; 因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。1. 简述算法的五

22、个重要的特征。：有穷性： 一个算法必须保证执行有限步之后结束；确切性： 算法的每一步骤必须有确切的定义； 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件；输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。备注： 算法可以没有输入。因为有些算法中包含了输入，如随机产生输入。2. 简答贪心算法的基本元素：贪心选择性质：所谓贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择达到。最优子结构性质：当一个问题的最优解包含其子问题

23、的最优解时，称此问题具有最优子结构。3.简述动态规划算法的基本思想和基本步骤以及动态规划问题的特征。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。按以下几个步骤进行：分析最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。 根据计算最优值时得到的信息，构造一个最优解。动态规划问题的特征：动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。1、最优子结构：当问题的最优解包含了其子问

24、题的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。4. 简述回溯算法的基本思想及解题步骤。回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩

25、展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。（9分）运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2分）（2）确定易于搜索的解空间结构；（2分） （3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。5.简述分治算法的基本思想及基本步骤。分治法的基本思想：对于一个输入规模为的问题，若该问题容易的解决，则直接解决，否则将其分解为

26、个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归求解这些子问题，然后将各个子问题的解合并，得到原问题的解。（9分）分治法在每一层递归上由以下三个步骤组成：划分：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题；（2分）解决：若子问题规模较小，则直接解决；否则递归求解各个子问题。（2分）合并：将各个子问题的解合并为原问题的解。（2分）6.分支限界法的基本思想：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直