算法设计与分析总结

简答：算法定义：算法是一个满足下列条件的计算：有穷性/终止性：有限步内必须停止。/*好算法/坏算法*/确定性：每一步都是严格定义和确定的动作。/*要严格算法语言*/能行性：每一个动作都能够被精确地机械执行。输入：有一个满足给定约束条件的输入。输出：满足给定约束条件的结果。常用算法及其特点：递归分治法，贪心算法，动态规划，回溯法等。递归分治法：基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。动态规划法：1）适用条件：当一个优化问题可分为多个子问题，子问题的解被重复使用。具有最优子结构和重叠子问题2）基本思想：求解每个子问题仅一次，并保存其结果，以后用到时直接存取，不重复计算，节省计算时间。3）解题步骤：①分析优化解的结构②递归地定义最优解的代价③自底向上地计算优化解的代价保存之，并获取构造最优解的信息④根据构造最优解的信息构造优化解4）与递归分治法的区别：动态规划法自底向上，递归分治法自顶向下贪心算法：1）基本思想·求解最优化问题的算法包含一些列步骤·每一步都有一组选择·作出在当前看来最好的选择·希望通过作出局部优化选择达到全局优化选择2）产生优化解的条件①贪心选择性②优化子结构3）与动态规划法的比较：·动态规划方法可用的条件优化子结构子问题相交性子问题空间小·贪心算法可用的条件优化子结构贪心选择性*可用Greedy方法时，动态规划方法可能不适用。*可用动态规划方法时，Greedy方法可能不适用。6.平摊分析：1）基本思想：·在平摊分析中，执行一系列数据结构操作所需要时间是通过对执行的所有操作求平均而得出的。·平摊分析可用来证明在一系列操作中，即使单一的操作具有较大的代价，通过对所有操作求平均后，平均代价还是很小的。·平摊分析与平均情况分析不同,不牵涉到概率。2)常用方法:聚集方法、会计方法、势能方法。3）区别与联系：（1）聚集方法为每个操作都赋予相同的平摊代价，即使序列中存在不同类型操作时也一样。会计方法和势能方法对不同类型操作赋予不同的平摊代价。（2）势能方法不是将已预付的费用作为存储在数据结构特定对象中的存款来表示，而是表示成一种“势能”，或“势”，它在需要时可释放出来以支付后面操作的代价。势是与整个数据结构而不是其中的个别对象发生联系的。即会计存储在个体上，势能存储在整体上。7.拟阵：1）定义：Matroid是一个序对M=(S,I)，满足：S是一个有限非空集合;I是非空的S子集的集族，I中的子集合称为S的独立子集合;遗传性:如果BI，AB，则AI；交换性：如果AI，BI，A<B，则xB-A使得A{x}I。2）图拟阵(GraphicMatroid)的定义：设G=(V，E)是一个无向图，由G确定的图拟阵MG=（SG，IG）定义如下：SG是G的边集合E，IG={A|A=E’E,(V,A)是一个森林}。显然，SG=E是一个有限集合.因为eE，(v,{e})是一个森林，{e}IG。于是，IG是SG的非空集族。③证MG满足遗传性。如果BIG，AB，则(V，A)是一个森林。于是，AIG，MG满足遗传性。④证MG满足交换性。设AIG，BIG，A>B，由图论定理可知，具有k条边的森林包括V-k棵树，于是，A包括V-A棵树，B包括V-B棵树。由于B具有较少的树，B一定包含一个树T，T的结点在A的不相同树中。T是连通的，必包括一条边(u,v)，使得u和v在A的不相同树中。(u,v)A-B连接A的两棵不同的树，(u,v)可以加到A，(V,A{(u,v)})是森林，A{(u,v)}IG，于是MG满足交换性。Matroid的性质定义2.设M=(S，I)是一个Matroid，AI。xA称为A的一个extension如果A{x}I。定义3.设M=(S，I)是一个Matroid，AI（A称为M的独立子集合）。如果A没有extension，则称A为最大独立子集合。定理2.一个Matroid的所有最大独立子集合都具有相同大小。证.A是MatroidM的最大独立子集合，而且存在M的另一个独立子集合B,A<B。根据M的交换性，xB-A使得A{x}I，与A最大矛盾。定义4（加权Matroid）设M=(S，I)是一个Matroid。如果存在一个权函数W，使得xS,W(x)是一个正数，则称M是加权Matroid。*权函数W可以扩展到S的任意子集合A：w(A)=.加权Matroid上的Greedy算法Greedy(M,W)A=;按权w值大小排序S；FORxS（按w(x)非增序）DOIfA{x}I/*每次选择具有最大w(x)的x—贪心*/ThenA{x}；ReturnA.时间复杂性step2:O(slogs)step4:O(f(s))T(s)=O(slgs+sf(s)8.P：时间复杂度在O(n的k次方)多项式之内可求解NP：不能在多项式时间内求解，但可验证NPC：NP问题的子集回溯法：基本思想：以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。解题步骤：(1)针对所给问题，定义问题的解空间(2)确定易于搜索的解空间；(3)以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索.3）子集树与排列树子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。O(2^n)排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。O(n!)10.Master定理定理2.4.1设是常数，是一个函数,是定义在非负整数集上的函数.可以如下求解：⑴.若,是常数，则.⑵.若，则.⑶.若,是常数,且对于所有充分大的n。,c>1是常数,则.*直观地：我们用与比较⑴.若大，则⑵.若大，则⑶.若与同阶，则.*更进一步：在第一种情况,不仅小于，必须多项式地小于,即对于一个常数，在第三种情况,不仅大于，必须多项式地大于，即对一个常数，.*注意：这三种情况并没有cover所有可能的⑴情况1与情况2之间有空隙,即小于,但不是多项式也小于.⑵情况2与情况3也同样有间断空隙.对于这两种情况，Master定理也无能为力.近似算法1.RatioBound(RatioBound)设A是一个优化问题的近似算法，A具有ratioboundp(n)，如果,其中n是输入大小，c是近似算法所产生的解的代价，c*是优化解的代价。*若问题是最大化问题，则，*若问题是最小化问题，则，*由于c/c*<1当且仅当c*/c>1,近似算法的RatioBound不会小于1，即*求解准确优化解的优化算法的RatioBound一定是1*具有较大RatioBound的近似算法给出的近似解一定比优化解坏的多—RatioBound表示了近似算法的性能2．相对误差对于任意输入,近似算法的相对误差定义为,其中c是近似算法所产生的解的代价，c*是优化解的代价。*相对误差总是非负的。一个近似算法的相对误差界为如果。P={L|LisalanguagethatcanbeacceptedbyaDTMinpolynomialtime.}NP={L|LisalanguagethatcanbeacceptedbyaNDTMinpolynomialtime.}证明：1、证明,其中证:由于，且，所以2、对于任意f(n)和g(n),iff而且f(n)=(g(n)).证.如果,则当时,.显然. 如果且,则由可知，存在使得，当，。由f(n)=(g(n))可知，使得当，。令,则当，。所以3、4、例2证明。证：令c=1,n0=1,则当时，。5.证明证.设，令c1=a/4,c2=7a/4,则，令。当时成立。6.证明证.由于f(n)=o(g(n)),对任意>0,存在，当时,0f(n)<g(n),即.于是,计算题:求界限和Master定理1、设对于所有,，求的上界.解：,,……于是,.2、求的上界解：……3、4、.5、求的界（例1）解..于是6、用分裂和的方法求的下界.解:7、用Master定理求解.解：,,8、用Master定理求解.解：,,9.求解解：令，则,.令则.于是,.显然,,即由于2m=n,m=lgn,.10.用Master定理求解解：⑴,⑵对所有n,,.于是,11..解：.大于，但不是多项式也大于,Master定理不使用于该.综合题：在实际生活中，当遇到一个新的未知问题，综合运用《算法设计与分析》课程所学的知识给出你的最佳解决策略。1）先判定问题是否可判定，若问题不可判定，则该问题无法求解；2）若问题可判定，再进一步判定该问题是P问题还是NP问题；3）若问题是P问题，进行精确求解；4）若问题是NP问题，判断问题的规模n的大小，若n很小，设计算法精确求解；5）若问题的规模n很大，设计近似算法，求近似最优解。算法设计：1、活动安排问题：1）算法：复杂性分析：If结束时间已排序T(n)=(n)If结束时间未排序T(n)=(n)+(nlog2n)=(nlog2n)2、王教授加油问题：s[0]表示出发地s[m+1]终点站n表示加满油的行程refuel(s,m,n){ for(i=m+1;i>=2;i--) { s[i]=s[i]-s[i-1]; if(s[i]>n) { return("NOSolution"); } } t=s[1]; k=0; for(i=1;i<=m;i++) { t=t+s[i+1]; if(t>n) { k=k+1; x[k]=i; t=s[i+1]; } }}3、哈夫曼树：初始：f:5e:9c:12b:13d:16a:454、最小生成树：5、点覆盖问题：输入：无向图G=（V，E）输出：，满足(1).，、或{u,v}V’(2).是满足条件(1)的最小集合。*理论上已经证明优化结点覆盖问题是NP-完全问题。时间复杂性T(G)=O(|E|).性能定理1Approx-Vertex-Cover具有RatioBound2证:令A=是算法第4步选中的边}。若(u,v)A，则所以与（u,v）邻接的边皆从中删除。于是,A中无相邻接边