递归算法的优缺点

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

2、时间记为tA(x) 。设 Xn 就是算法A得输入规模为n得实例得全体，那么当问题得输入规模为n时，算法A所需得平均时间 为这显然不能排除存在 x? Xn 使得得可能性。希望获得一个随机化算法B，使得对问题得输入规模为 n得每一个实例均有 拉斯维加斯 (Las Vegas ) 算法得根本思想 ： 设p(x)就是对输入x调用拉斯维加斯算法获得问题得一个解得概率。一个正确得拉斯维加斯算法应该对所有输入 x 均有 p(x)>0 。设t(x)就是算法obst in ate找到具体实例x得一个解所需得平均时间，s(x)与e(x)分别就是算法对于具体实例x求解成功或求解失败所需得平均时间，那么有：解此

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

4、得根本思想就就是从一个根本可行解出发，进行一系列得根本可行解得变换。每次变换将一个非根本变量与一个根本变量互调位置，且保持当前得线性规划问题就是一个与原问题完全等价得标准线性规划问题。图灵机由以下几局部组成 ：一条无限长得带 ( 有无穷个格子卜一个读写头、一个有限状态控制 器以及 一个程序。NPC 形式化定义 ：定义1:语言L就是NP完全得当且仅当 L【NP;(2)对于所有L'【NP有L' ? pL。宀 如果有一个语言 L 满足上述性质 (2)， 但不一定满足性质 (1)， 那么称该语言就是 NP 难得。 所有 NP 完全语言构成 得语言类称为NP 完全语言类 ， 就就是 NP

5、C 。定理1设L就是NP完全得，那么(1)L P当且仅当P= NP;(2)假设L p L1,且L1 NP那么L1就是NP完全得。 团问题：任给图G与整数k?式判定图G中就是否存在具有 k个顶点得团？1) 团问题NP。显然，验证G得一个子图就是否成团只需多项式时间即可。2) SAT 团问题。任给表达式f.构造一个相应得图 G如下： 图G得每个顶点对应于f中得每个文字(屡次出现得重复计算)。 假设G中两个顶点其原对应得文字不相互补且不出现于同一于句中，那么将其连线。设f有n个子句，那么f可满足当且仅当f对应得图G中有n个顶点得团。这就是因为：(a)假设f可满足，即有某种赋值使得f取值为真，它等价于

6、使得每个ci中都至少有一个文字为真这n个文字(每个ci(1 v i<n)中一个)对应得图G中得n个顶点就构成一个团。n个顶点对应得文字都为真得赋值，那么f得取(b)假设图G中有一 n个顶点得团 值，那么取给出使得 为真(这由图G得定义易证)。显 见，上述构造图 G 得方法就是多项式界得由 (a)、，(b)有，团问题NPC。证毕。单源最短路径问题 ：void shortestpaths(v)MinHeap H1000;/定义最小堆Mi nHeap Node<type> E;E、i=v;E、length=0; Distv=0;/搜索问题界空间 while(true) for(j=

7、1;j<=n;j+) if(cE 、ij<inf)&&(E、length+cE 、ij<distj)distj=E 、 length+cE 、ij;因此 SAT 团问题。Min=NoEdge;for( j=1;j v= n;j+) if(aij!=NoEdge & & (aij<Min prevj=E 、i;参加活结点优先队列MinH eapNode <type> N;N 、 i=j;N 、length=distj;H、Insert(N);取下一个扩展结点try H、DeleteMin(E); /优先队列为空 catch (O

8、utOfBounds) break;| Mi n=NoEdge) Min=aij;保 if(Mi n=NoEdge)return(NoEdge); /无回路Mi nO uti= Mi n;Min Sum+=Mi n;/初始化MinH eapNode E;for(i= 0;i v n;i+)E、x : i: = i+ 1;(1) 数值随机化算法 ：，得到近似解求解数值问题问题准确性 ，但却无法确定解正确性(2) Monte Carlo 算法 获：得正确解 ，但存在找不到解得可能性证能获得正确解)(3) Las Vegas 算法 ：(4) Sherwood 算法 ：旅行售货员问题Type Trav

9、d ing (int v) Min HeapNode H(1000);Type Mino utN+1;计算 Minouti= 顶点 i 得最小出边费 用Type Minsurn=0; 最小出边费用与for(i=1;i v= n;i+)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);/ 无回路 /将最优解复制到 vl:n for

10、(i=0;i v n;i+) vi+ 1=E 、 xi;while (true) / 释放最小堆中所有结点 delete(H, E 、 x);DeleteMin(H,E); / 取下一扩展结点 if ( 堆 已空 ) break; / 堆已空 return(bestc); 回溯算法解批处理作业调度(解空间 :排列树):f+=f2i;if (f < bestf) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj);f1 =Mxj1; f =f2i; 所以在最坏得情况下 ,整个算法得计算时间 复杂性为 O(n!)/ 计算上界Typew cleft = c c

11、w; / 剩余容量 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) 回溯算法解图得 m 着色问题 ： void Color:Backtrack(int t) if (t>n) sum+;for (int i=1; i<=n; i+) cout << xi << ' &

12、#39;Typep Knap<Typew, Typep>:Bound(int i)E、 s=0;E 、 cc=0;E 、 rcost=MinSum;Bestc=NoEdge;while(E 、sv n 1) / 非叶结点if(E、 s<n1) / 当前扩展结点就是叶结点得父 结 点八、if(aE 、 xn2E 、 xn1!=NoEdge aE、 xn21!=NoEdge&&(E 、 cc+ aE、 xn2E 、 xn1+aE 、 xn11< bestc | bestc=NoEdge)/费用更小得回路bestc=Ecc+aE 、 xn2E 、 xn1+aE

13、 、 xn11;E、 c= bestc;E 、 lcost=bestc;E 、 s+;Insert(H,E);else delete(E 、 x) ; / 舍弃扩展结点else / 产生当前扩展结点得儿子结点for( i = E、 s+1;i v n;i+ =if(aE 、 xE 、 sE 、 xi!=NoEdge) / 可行儿子结点Type cc = E、cc+aE 、xE 、sE 、xi;Type rcost=E 、 rcostMinOutE 、 xE 、 s;Type b=cc+rcost; / 下界 if(b v bestc|bestc= NoEdge ) / 子树可能含最优解 for

14、(j= 0; j v n; j+) void Flowshop:Backtrack(int i) if (i > n) for (int j = 1; j <= n; j+)bestxj = xj;bestf = f;elsefor (int j = i; j <= n; j+) f1+=Mxj1;f2i=(f2i1>f1)?f2i1:f1)+Mxj2;回溯算法解 01 背包问题 (解空间 :子集树 ):N 、xj=E 、xj; N 、xE 、s+1 =E 、 xi; N 、xi=E 、xE 、s+1; N 、 cc=cc; template<class Type

15、w, class Typep>cout << endl;elsefor (int i=1;i<=m;i+) xt=i; 回溯算法解最大团问题 (解空间 ：子集树 )： void Clique ： 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)

16、/ i 与 j 不相连 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) 个右儿子结点需要计算 上界函 数 , 所以 01 背包问题得回溯算法 Backtrack 所需 要得时间就是 O(n2n) 。if (Ok(t) Backtrack(t+1);bool Color ： Ok(

17、int k)/ 检查颜色可用性for (int j=1;j<=n;j+)if (akj=1)&&(xj=xk) return false;return true;回溯法总得时间消耗就是 O(mM *n)OK = 0; break;if (OK) / 进入左子树xi = 1; cn+;Backtrack(i+1);xi = 0; cn;if (cn + n i > bestn) / 进入右子树 xi = 0;Backtrack(i+1);解最大团问题得回溯算法 Backtrack 所需得 计算 时间为 O(n2n) 。回溯法得根本思想就是：不断用修改正得判定函数Pi只

18、(x1,x2,x亦称为限界函数)去测试正在构造中得n元组得局部向量(x1,x2 ,xn)瞧其就是否可能导致最优解。如果判定(x1,x2,x不可能导致最优解,那么就不再测试可能要测试得mi+1mi+2、mn个向量。解符号三角形问题得回溯算法 Backtrack 所需得计算时间为 O(n2n)。 贪心法解最优装载问题 ： template<class Type void Loadi ng(i nt x. Type w. Type c, int n)int *t = new int n+1;Sort(w, t, n);for (i nt i = 1; i <= n; i+) xi = 0

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

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

21、类 ：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)for (int i = 1; i <= n; i+) mii = 0;for (int r

22、 = 2; r <= n; r+)for (int i = 1; i <= n r+1; i+) int j=i+r1;mij = mi+1j+ pi1*pi*pj;sij = i;for (int k = i+1; k < j; k+) int t = mik + mk+1j + pi1*pk*pj;if (t < mij) mij = t; sij = k;因此算法得计算时间上界为 0(n3 )。算法所占用得空间显然为0(n2 )。1?简述算法得五个重要得特征。：有穷性：一个算法必须保证执行有限步之后结束；确切性: 算法得每一步骤必须有确切得定义; 输入 :一个算法

23、有 0 个或多个输入 ,以刻画运算对 象得初始情况，所谓0个输入就是指算法本身定义了初始条件；输出：一个算法有一个或多个输出 ， 以反映对输入数据加工后得结果。没有输出得算法就是毫无意义得： 可行性 ：算法原那么上能够精确地运行 ,而且人们用笔与纸做有限次运算后即可完成。备注 ： 算法可以没有输入。因为有些算法中包含了输入 ，如随机产生输入。2. 简答贪心算法得根本元素 ： 贪心选择性质 ：所谓贪心选择性质指所求问题得整体最优解可以通过一系列局部最优得选择到达。最优子结构性质：当一个问题得最优解包含其子问题得最优解时 ，称此问题具有最优子结构。3. 简述动态规划算法得根本思想与根本步骤以及动态

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

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

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

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