《2022年递归算法的优缺点备课讲稿 .pdf》由会员分享，可在线阅读，更多相关《2022年递归算法的优缺点备课讲稿 .pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、递 归 算 法 的 优 缺 点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - - 精品文档收集于网络，如有侵权请联系管理员删除递归算法的优缺点：1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。边界条件与递归方程是递归函数的二个要素应用分治法的两个前提是问题的可分性和解的可归并性以比较
2、为基础的排序算法的最坏倩况时间复杂性下界为0(n log2n)。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。舍伍德算法设计的基本思想: 设 A 是一个确定性算法，当它的输入实例为x 时所需的计算时间记为tA(x) 。设 Xn 是算法 A 的输入规模为 n 的实例的全体，则当问题的输入规模为n时，算法 A 所需的平均时间为这显然不能排除存在xXn 使得的可能性。希望获得一个随机化算法 B，使得对问题的输入规模为n的每一个实例均有拉斯维加斯 ( Las Vegas ) 算法的基本思想 : 设 p(x)是对输入 x 调用拉斯维加斯算法获得问题的
3、一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x 均有 p(x)0。nXxnAAXxtnt| / )()()()(ntxtAA)()()(nsntxtAB名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - - - - - - 精品文档收集于网络，如有侵权请联系管理员删除设 t(x)是算法 obstinate找到具体实例 x 的一个解所需的平均时间 ,s(x)和 e(x)分别是算法对于具体实例x 求解成功或求解失败所需的平均时间，则有：解此方程可
4、得：蒙特卡罗 (Monte Carlo)算法的基本思想 : 设 p 是一个实数，且 1/2p1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称 p-1/2是该算法的优势。如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。单纯形算法的特点是：（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；（2）一般经过不大于m 或 n 次迭代就可求得最优解。单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。每
5、次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题。图灵机由以下几部分组成：一条无限长的带（有无穷个格子）、一个读写头、一个有限状态控制器以及一个程序。)()()(1 ()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 15 页 - - - - - - - - - 精品文档收集于网络，如有侵权请联系管理员删除NPC形式化定义：定义 1：语
6、言 L 是 NP 完全的当且仅当（ 1） L【NP；（2）对于所有 L 【NP 有L pL。如果有一个语言 L 满足上述性质 (2),但不一定满足性质（ 1），则称该语言是NP难的。所有 NP 完全语言构成的语言类称为NP 完全语言类，就是NPC。定理 1 设 L 是 NP 完全的，则（ 1）LP当且仅当 PNP；（2）若 L p L1，且 L1 NP，则 L1 是 NP 完全的。团问题 : 任给图 G和整数 k试判定图 G 中是否存在具有 k 个顶点的团？ 1)团问题NP。显然，验证 G的一个子图是否成团只需多项式时间即可。 2)SAT团问题。任给表达式 f构造一个相应的图G 如下：图 G
7、的每个顶点对应于f 中的每个文字 (多次出现的重复计算 )。若 G 中两个顶点其原对应的文字不相互补且不出现于同一于句中，则将其连线。设 f 有 n 个子句，则 f 可满足当且仅当 f 对应的图 G中有 n个顶点的团。这是因为：(a)若 f 可满足，即有某种赋值使得f 取值为真，它等价于使得每个ci 中都至少有一个文字为真，这n 个文字 (每个 ci(1in)中一个 )对应的图 G中的 n 个顶点就构成一个团。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 15 页 -
8、- - - - - - - - 精品文档收集于网络，如有侵权请联系管理员删除(b)若图 G 中有一 n个顶点的团，则取给出使得这n 个顶点对应的文字都为真的赋值，则 f 的取值为真 (这由图 G 的定义易证 )。显见，上述构造图G 的方法是多项式界的，因此SAT 团问题。由(a)、(b)有，团问题NPC。证毕。单源最短路径问题 : void shortestpaths(v) MinHeap H1000; /定义最小堆MinHeapNode E; E.i=v; E.length=0; Distv=0; /搜索问题界空间while(true) for(j=1;j=n;j+) if(cE.ijinf
9、)& (E.length+cE.ijdistj) distj=E.length+cE.ij; prevj=E.i; /加入活结点优先队列MinHeapNode 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算法:保证能获得正确解
10、旅行售货员问题 :(优先队列式分支限界法 ) Type Travding (int v) MinHeapNode H(1000)； Type MinoutN+1 ； /计算 Minouti= 顶点 i 的最小出边费用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 15 页 - - - - - - - - - 精品文档收集于网络，如有侵权请联系管理员删除 Type Minsurn=0；/最小出边费用和for（i=1;i n；i+） Min=NoEdge； for（ j=1；
11、jn；j+） if（aij!=NoEdge (aijMin | Min=NoEdge) Min=aij ； if（Min=NoEdge）return(NoEdge)； /无回路 MinOuti= Min ； MinSum+=Min ； /初始化 MinHeapNode E； for（i= 0；i n；i+） E.xi= i+ 1； E.s=0； E.cc=0； E.rcost=MinSum； Bestc=NoEdge ； while（E.sn-1) /非叶结点if（E.sn-1） / 当前扩展结点是叶结点的父结点if（aE.xn-2E.xn-1!=NoEdge aE.xn-21!=NoEdge
12、& （E.cc+ aE.xn-2E.xn-1+aE.xn-11 n) for (int j = 1; j = n; j+) bestxj = xj; bestf = f; else for (int j = i; j 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、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 15 页 - - - - - - - - - 精品文档收集于网络，如有侵权请联系管理员删除template Typep Knap:Bound(int i) / 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i n ) bestp=cp; return; if(cw+wib
14、estp ) backtrack(i+1); /xi=0 由于上界函数 Bound()需要 O(n)的时间，在最坏的情况下有O(2n)个右儿子结点需要计算上界函数，所以0-1背包问题的回溯算法Backtrack()所需要的时间是 O(n2n)。回溯算法解图的 m 着色问题 : void Color:Backtrack(int t) if (tn) sum+; for (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
15、 k) / 检查颜色可用性 for (int j=1;j n) / 到达叶结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 15 页 - - - - - - - - - 精品文档收集于网络，如有侵权请联系管理员删除 for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; / 检查顶点 i 与当前团的连接 int OK = 1; for (int j = 1; j bestn) / 进入右子树xi = 0;
16、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 void Loading(int x, Type w, Type c, int n) int *t
17、= 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)有限性：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - -
18、- - - - - - - 精品文档收集于网络，如有侵权请联系管理员删除问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。1. 什么是动态规划法：将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。2. 什么是贪心法：从问题某一初始或推测值出发，一步步的攀登给定目标，尽可能快的去逼近更好的解，当达到某一步不能继续时终止。3. 什么是分支定界法：对有约束条件的最优化问题所有可行解定向、适当地进行搜索。将可行解空间不断地划分为越来越小的子集（分支），并为每一个子集的解计算一个上界和下界（定界）。5、什么是 NP类问题：
19、NP=L|L 是一个能在多项式时间内被一台NDTM 图灵机所接受的语言 ，其中NDTM 是非确定性图灵机。或者可说：NP 是所有可在多项式时间内用不确定的算法求解的判定问题的集合。对于NP 类，相当于要求验证模块在多项式时间内完成对应 NDTM ，有非确定性算法。1. 算法的分类： 1）(数值算法 ) 2） 非数值算法2. 算法的描述： 1）自然语言描述 2）(流程图描述 ) 3）程序语言描述3. 算法的分析标准： 1） 时空观念 2 ）(发展观念 ) 3） 设计观点 4） 交流的观点设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。名师资料总结 - -
20、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 15 页 - - - - - - - - - 精品文档收集于网络，如有侵权请联系管理员删除(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。动态规划法求矩阵连乘问题：void MatrixChain(int *p ，int n，int *m ，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1
21、; 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 1 时, 取 y1=1;yk=0;yi=xi,1 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -