递归算法的优缺点

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

2、为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时的可能性。希望获得一个随机化算法5 0) = 5) + S(n)E,使得对问题的输入规模为n的每二个实例均有这显然不能排除存在XGX11使後tA (x) » t A (n)拉斯维加斯(Las Vegas)算法的基本思想：设p(x)是对输入X调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算 法应该对所有输入x均有p(x)>0。设t(x)是算法obstmate找到具体实例x的一个解所需的平均时间，s(x)和e(x)分别是算法对于 具体实例X求解成功或求解失败所需的平均时间，则有f(x)二p(.r)5( V

3、)4-(1- P(x)(£(x) + r( v) 解此方程可得：1 蒙特卡罗(Monte Carlo)算法的基本思想：设p是一个实数，且l/2<p<lo如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概 率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一 致的。线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。单纯形算法的特点是：(1) 只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；(2) 一般经过不大于m或11次迭代就可求得最优解

4、。单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。每次 变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题。图灵机由以下几部分组成：一条无限长的带(有无穷个格子)、一个读写头、一个有限状态 控制器以及一个程序。NPC形式化定义：定义1：语言L是NP完全的当且仅当(1) L NP； (2)对于所有1/匸NP有LpLo 如果有一个语言L满足上述性质(2),但不一定满足性质(1),则称该语言是NP难的。 所有NP完全语言构成的语言类称为NP完全语言类，就是NPCo定理1设L是NP完全的，则(1) L P当且仅当P=

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

6、)中一个)对应的图G中的n个顶点就构成一个团。(b) 若图G中有一 n个顶点的团，则取给出使得这n个顶点对应的文字都为真的赋值，则f 的取值为真(这由图G的定义易证)。显见，上述构造图G的方法是多项式界的，因此SAT(X团问题。由(a)、(b)有，团问题 NPC。证毕。单源最短路径问题：void shoitestpaths(v)MinHeap H1000;定义最小堆MinHeapNode<tvpe> E;E.i=v;E.length=0;Distv=0:搜索问题界空间wliile(tnie) fof(j=lJ<=n；j-H-)if(c E.ij(Eength+cE.ij<

7、;distj)d ist j =E. length+c E.ij;prevj=E.i;加入活结点优先队列NIiiiHeapNode <tvpe> N;N.i=j；N.length=distj;H.Iiisert(N);取下一个扩展结点try H.DeleteMin(E); 优先队列为空catch (OutOfBounds) break;(1) 数值随机化算法：求解数值问题，得到近似解 Monte Carlo算法：问题准确性，但却无法确定解正确性 Las Vegas算法：获得正确解，但存在找不到解的可能性 (4)Shenvood算法：保证能获得正确解旅行售货员问题:(优先队列式分支限

8、界法)Type Travdmg (int v) MniHeapNode H(1000)：Type MiiioutN+1 ；计算Mmouti=顶点i的最小出边费 用Type Mmsurn=0 ； 最小出边费用和for (i=l;i<=n； i+) Miii=NoEdge；for ( j=l； j<=n： j+)if (aij!=NoEdge& &(aij<Min| Min=NoEdge) Min=aij；if (Mm=NoEdge) retuin(NoEdge): 无回路MiiiOuti= Min：MmSum+=Min；初始化MinHeapNode E；for

9、(i= 0： i< n； i+)E.x i = i+ 1；E.s=0；E.cc=0：E.rcost=MinSum；Bestc=NoEdge；wliile (E.s<n-1) /非叶结点if (E.svn-l) /当前扩展结点是叶结点的父 结点if ( aE.xn-2E.xn-l!=NoEdge & & aE.xn-2 1 !=NoEdge&& (E.cc+ aE.xn-2E.xn-l+aE.xn.ll< bestc | bestc=NoEdge) 费用更小的回路bestc=Ecc+aE.xn-2 E.xn-1+aE.xn-ll；E.c = be

10、stc：E.lcost=bestc：E.s+；Insert (H,E)； else delete(E.x) : 舍弃扩展结点 else 产生当前扩展结点的儿子结点 for ( i=E.s+l； i<n； i+=if ( aE.xE.sE.xi !=NoEdge) 可行儿子结点Type cc=E.cc+aE.xE.sE.xi:Type rcost=E.icost-NIinOutE.xE.s； Type b=cc+rcost； 下界 if (b< bestc|bestc= NoEdge )子树可能含最优解for (j= 0； j< n； j+)N.xj=E.xj；N.xEs+l=

11、E.xi；N.xi=E.xE.s+l；N.cc=cc；N.s= E.s+1；N.lcost=b：N.rcost=icost：Insert (H,N)：delete(H,E.x)；/完成结点扩展DeleteMm(H,E): 取下一扩展结点if (堆已空)break： 堆已空1)if (bestc=NoEdge) retuin( NoEdge)； 无回路将最优解复制到vl: 11for (i=0； i<n： i+)vi+ l=E.xi；while (tme) 释放最小堆中所有结点delete(H, E. x)：DeleteMin(H,E): 取下一扩展结点 if (堆己空)break； 堆己

12、空leturn(bestc)：void Flowshop:Backtrack(iiit i)for (mt j = l;j <=n;j+)bestxfj = xj;bestf = f;elsefor (mt j = i; j <=n;j+) fl+=Mx|jl;f2i=(f2i-l>fl)?f2i-l:fl)+Mxj2;回溯算法解0-1背包问题(解空间：子集树): template<class Tvpew, class Tvpep>Typep Kiiap<Tvpew, Typep>:Bound(int i) /计算上界Tvpew cleft = c -

13、 cw; / 剩余容量Tvpep b = cp;以物品单位重量价值递减序装入物品 wliile (i <= n && wi <= cleft) cleft =wi;b += pM；/装满背包if (i <= n) b += pi/wi * cleft; return b;void backtrack(i)回溯算法解图的m着色问题：void Color:Backtrack(mt t)if (E) SU111+；for (int i=l; i<=n; i+)cout « xi «f :cout« endl;elsefor (in

14、t i=l;i<=m;i+) 回溯算法解批处理作业调度(解空间：排列 树)：fT2】；if (f < bestf) Swap(xi, xj);Backtrack(i+1);Swap(xi, xj);fl-=Mx|jl;f-=£2i;所以在最坏的情况卞，整个算法的计算时间复杂性为O(d!)逬向) bestp=cp;return; if(cw+wi<=c)/xi=1 cw+=wi ；cp+=pi;backtrack(i+l);cw-=wi ;cp-=pi;if (bound(i+l)>bestp)backtrack(i+l); /xi=0由于上界函数Bound()

15、需要O(n)的时间，在 最坏的情况卞有O(2n)个右儿子结点需要计 算上界函数，所以0-1背包问题的回溯算法 BackUackQ所需要的时间是O(ii2n)oxt=i；if (Ok(t) Backtrack(t+1);bool Color: :Ok(iiit k)/检查颜色可用性for (mt尸I;j<=n;j+)if (akj=l)&&(xj=xk) return false;return tme;回溯法总的时间耗费是O(m"i *n)回溯算法解最大团问题(解空间：子集树): void Clique: Backtiack(int i)/计算最大团if(i>

16、;n)/到达叶结点for (int j = 1; j <= n; j+) bestxj=Xj；bestn = cn; return;/检查顶点1与当前团的连接mt OK= 1;for (mt j = l；j<i；j+)if(xj && aij = 0)i与J不相连OK = 0; break;if (OK) /进入左子树xi = 1;cn+;Backtiack(i+1);xi = 0; cn-;if (cn + n - i > bestn) / 进入右子树 X1 = o；Backtiack(i+1);解最人团问题的回溯算法Backuack所需的 计算时间为O(1

17、1211)0回溯法的基本思想是：不断用修改过的判定函数Pi只(xl,x2_xi)(亦称为限界函数)去测试 正在构造中的n元组的部分向量(xl,x2,.xii).看其是否可能导致最优解。如果判定(xl, x2,，xn)不可能导致最优解，那么就不再测试可能要测试的个向量。解符号三角形问题的回溯算法Backtrack所需的计算时间为0(11211)。贪心法解最优装载问题：template<class Tvpe>void Loadmg(int x, Type w, Type c, iiit n)int *t = new int n+1;Sort(w, t5 n);for (mt i= l;

18、i<= n; i+) xi = 0;for (mt i= l;i<=n && wti <= c; i+) xti = 1; c -= wti;算法所需的计算时间为O(nlogn)算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输 入(2)输出(3)确定性(4)有限性：问题的计算时间下界为Q(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。1. 什么是动态规划法：将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子 问题的解为后一个子问题的求解提供有用的信息。2. 什么是贪心法：从问题某一初始或推测值出发，一步步的

19、攀登给定目标，尽可能快的去 逼近更好的解，当达到某一步不能继续时终止。3. 什么是分支定界法：对有约束条件的最优化问题所有可行解定向、适当地进行搜索。将可 行解空间不断地划分为越来越小的子集(分支)，并为每一个子集的解计算一个上界和下界 (定界)。5、什么是NP类问题：NP=L|L是一个能在多项式时间内被一台NDTM图灵机所接受的语言,其中NDTM是非 确定性图灵机。或者可说：NP是所有可在多项式时间内用不确定的算法求解的判定问题的 集合。对于NP类，相当于要求验证模块在多项式时间内完成对应NDTM,有非确定性算法。1. 算法的分类：1)(数值算法)2)非数值算法2. 算法的描述：1)自然语言

20、描述2)(流程图描述)3)程序语言描述3. 算法的分析标准：1)时空观念2 )(发展观念)3)设计观点4)交流的观点设计动态规划算法的步骤。(1) 找出最优解的性质，并刻划其结构特征。递归地定义最优值。(2) 以自底向上的方式计算出最优值。(3) 根据计算最优值时得到的信息，构造最优解。动态规划法求矩阵连乘问题：void MatrixChaiii(mt *p, iiit n, int mt *s)for (mt i= l;i<=n; i+) mii = 0;for (int r = 2; r <= n; r+)for (int i= 1; i<=n- r+1; i+) iii

21、t j=i+r-l;=mi+lj+ pi-l*pi*pj;= i；for (intk = i+l; k<j; k+) int t = mik + mk+lj + pi-l*pk*pj;if (t <mij) mij = t; sij = k;因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)°1简述算法的五个重要的特征。：有穷性：一个算法必须保证执行有限步之后结束；确 切性：算法的每一步骤必须有确切的定义；输入：一个算法有0个或多个输入，以刻画 运算对彖的初始情况，所谓0个输入是指算法本身定义了初始条件；输出：一个算法有一 个或多个输出，以反映对输入数据

22、加工后的结果。没有输出的算法是亳无意义的；可行性: 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。备注：算法可 以没有输入。因为有些算法中包含了输入，如随机产生输入。2. 简答贪心算法的基本元素：贪心选择性质：所谓贪心选择性质指所求问题的整体最优解 可以通过一系列局部最优的选择达到。最优子结构性质：当一个问题的最优解包含其子问 题的最优解时，称此问题具有最优子结构。3. 简述动态规划算法的基本思想和基本步骤以及动态规划问题的特征。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、 相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优

23、化问题的算法策略。 按以下几个步骤进行： 分析最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式或自顶向卞的记忆化方法（备忘录法）计算出最优值。 根据计算最优值时得到的信息，构造一个最优解。动态规划问题的特征：动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结 构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题, 有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子 问题只解一次，而后将其解保存在一个

24、表格中，在以后尽可能多地利用这些子问题的解。4. 简述回溯算法的基本思想及解题步骤。回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以 深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展 结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的 活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩 展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯） 至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递 归地在解空间中搜索，直至

25、找到所要求的解或解空间中已没有活结点时为止。（9分）运用回溯法解题通常包含以卜三个步骤：（1）针对所给问题，定义问题的解空间：（2分）（2）确定易于搜索的解空间结构：（2分）（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。5. 简述分治算法的基本思想及基本步骤。分治法的基本思想：对于一个输入规模为的问题，若该问题容易的解决，则直接解决，否 则将其分解为R个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归求解 这些子问题，然后将各个子问题的解合并，得到原问题的解。（9分）分治法在每一层递归上由以下三个步骤组成： 划分：将原问题分解为若干规模较小、相互独立、与

26、原问题形式相同的子问题：（2分） 解决：若子问题规模较小，则直接解决；否则递归求解各个子问题。（2分）合并：将各个子问题的解合并为原问题的解。（2分）6. 分支限界法的基本思想：分支限界法常以广度优先或以最小耗费(最人效益)优先的方式搜索问题的解空间树。问题 的解空间树是表示问题解空间的一棵有序树，常见的有排列树。在搜索问题的解空间树时, 分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结 点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。 在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被 子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩 展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。7. 贪心算法的基本思想如下：从问题的某一个初始解出发逐步逼近给定的