




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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.分支限界法的基本思想:分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树,常见的有排列树。在搜索问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 基于“计数单位”的小学数学数概念与运算的整体化教学研究-以苏教版教材为例
- 107.危重症患者团队决策能力协作考核
- 2024年环境监测全流程质量控制体系考核试卷
- 10.《短视频叙事节奏与情绪引导职业技能考核》
- 承包水果合同(标准版)
- 砖混施工合同(标准版)
- 2024年绥化市北林区劳动就业服务中心招聘公益性岗位真题
- 杭州市萧山区委统战部下属事业单位选调工作人员考试真题2024
- 全市场科技产业策略报告第112期:数字医疗细分领域之医疗社交平台当前现状和未来发展怎么看
- 考点攻克人教版八年级物理上册第6章质量与密度-质量定向训练试题(解析卷)
- 木质纤维素的生物分解及其转化技术
- 海康威视磁盘阵列使用说明精.选
- GB/T 7387-1999船用参比电极技术条件
- GB/T 39473-2020北斗卫星导航系统公开服务性能规范
- GB 16808-2008可燃气体报警控制器
- 公司有限空间作业安全专项排查表
- 高考英语衡水体字帖电子书
- 强度调制机理光纤传感器基本原理课件
- 《当代中国经济》第一章中国经济体制改革
- 《自强不息的人格修养》-课件1
- DB4403-T 54-2020 停车库(场)交通设施建设与管理规范-(高清现行)
评论
0/150
提交评论