算法导论复习资料.doc

算法导论复习资料一、选择题：第一章的概念、术语。二、考点分析：1、复杂度的渐进表示，复杂度分析。2、正确性证明。考点：1正确性分析冒泡，归并，选择；2复杂度分析渐进表示O，©，替换法证明，先猜测，然后给出递归方程。循环不变性的三个性质：1初始化：它在循环的第一轮迭代开场之前，应该是正确的；2保持：如果在循环的某一次迭代开场之前它是正确的，那么，在下一次迭代开场之前，它也应该保持正确；3当循环完毕时，不变式给了我们一个有用的性质，它有助于说明算法是正确的。插入排序算法：INSERTION-SORT(A)1 for j 2 to lengthA2 do key Aj3 Insert Aj into the sorted sequence A1，j - 1.4 i j - 15 while i > 0 and Ai > key6 do Ai + 1 Ai7 i i - 18 Ai + 1 key插入排序的正确性证明：课本11页。归并排序算法：课本17页及19页。归并排序的正确性分析：课本20页。3、分治法根本步骤，复杂度分析。许多问题都可以递归求解考点：快速排序，归并排序，渐进排序，例如：12球里面有一个坏球，怎样用最少的次数找出来。解：共有24种状态，至少称重3次可以找出不同的球不是考点：线性时间选择，最接近点对，斯特拉算法求解。解：根本步骤：一、分解：将原问题分解成一系列的子问题；二、解决：递归地解各子问题。假设子问题足够小，那么直接求解；三、合并：将子问题的结果合并成原问题的解。复杂度分析：分分治算法中的递归式是基于根本模式中的三个步骤的，T(n)为一个规模为n的运行时间，得到递归式T(n)=Q(1) n<=cT(n)=aT(n/b)+D(n)+C(n) n>c附加习题：请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。4、动态规划最优子构造性质，自底向上填表计算最优解值即最长公共子序列，导出最优解。考点：最优子构造性质，自底向上填表计算最优解值，导出最优解。a动态规划算法设计的4个步骤：1描述最优解的构造；2递归定义最优解的值；3按自底向上的方式计算最优解的值；4由计算出的结果构造一个最优解。b最优子构造遵循的共同模式：1问题的一个解可以是做一个选择，做这种选择可能会得到一个或多个有待解决的子问题；2假设对一个给定的问题，的是一个可以导致最优解的选择，不必关心如何确定这个选择，尽管假定它是的；3在这个选择后，要确定哪些子问题会随之发生，以及如何最好地描述所得到的子问题的空间；4利用一种“剪切粘贴法，来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。备注：A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. Whenever a problem exhibits optimal substucture it is a good clue that dynamic programming might apply. c最长公共子序列的算法：这里以两个序列X=x1,x2,xm和Y=y1,y2,yn为输入，注意课本211页的自底向上填表方法。LCS-LENGTH(X, Y) 注：此程序运行时间为Omn，每个表项的计算时间为O11 m lengthX 2 n lengthY 3 for i 1 to m 4 do ci, 0 0 5 for j 0 to n 6 do c0, j 0 7 for i 1 to m 8 do for j 1 to n 9 do if xi = yj 10 then ci, j ci - 1, j - 1 + 1 11 bi, j “=" 12 else if ci - 1, j ci, j - 1 13then ci, j ci - 1, j 14 bi, j "" 15 else ci, j ci, j - 1 16 bi, j " " 17 return c and b PRINT-LCS(b, X, i, j) 注：此程序运行时间为Om+n1 if i = 0 or j = 0 2 then return 3 if bi, j = "=" 4 then PRINT-LCS(b, X, i - 1, j - 1) 5 print xi 6 elseif bi, j = "" 7 then PRINT-LCS(b, X, i - 1, j) 8 else PRINT-LCS(b, X, i, j - 1) d矩阵链乘法的算法：参照课本上的矩阵链表得出矩阵相乘的最小算法。MATRIX-CHAIN-ORDER(p) 每个表项的复杂度是On，共有On2表项，那么为On31 n lengthp - 1 2 for i 1 to n 3 do mi, i 0 4 for l 2 to n l is the chain length. 5 do for i 1 to n - l + 1 6 do j i + l - 1 7 mi, j 8 for k i to j - 1 9 do q mi, k + mk + 1, j + pi-1 pkpj 10 if q < mi, j 11 then mi, j q 12 si, j k 13 return m and s PRINT-OPTIMAL-PARENS(s, i, j)1 if i = j 2 then print "Ai "3 else print "(" 4 PRINT-OPTIMAL-PARENS(s, i, si, j) 5 PRINT-OPTIMAL-PARENS(s, si, j + 1, j) 6 print ")" e备忘录算法：1程序构造采用自顶向上；2保存了递归构造，开销较大；3当所有的子问题都需要求解时，自底向上的方法效率较高，否那么可以采用备忘录方法。备忘录算法的代码可以参照课本207页。f最优二叉查找树：1一棵最优二叉查找树不一定是一棵整体高度最小的树，也不一定总是把有最大概率的关键字放在根部来构造一棵最优二叉查找树。5、贪心法最优子构造性质+贪心选择性质。考点：学会证明最优子构造性质和贪心选择性质的问题。a活动选择问题：注意课本上224页地贪婪法定理证明，这就是贪婪法的合理性证明。RECURSIVE-ACTIVITY-SELECTOR(s, f, i, j)1 m i + 1 2 while m < j and sm < fi Find the first activity in Sij.3 do m m + 1 4 if m < j 5 then return am RECURSIVE-ACTIVITY-SELECTOR(s, f, m, j) 6 else return GREEDY-ACTIVITY-SELECTOR(s, f)1 n lengths 2 A a1 3 i 1 24 for m 2 to n 5 do if sm fi 6 then A A am 7 i m 8 return A b贪心算法遵循的步骤：1决定问题的最优子构造；2设计出一个递归解；3证明在递归的任一阶段，最优选择之一总是贪心选择，那么，做贪心选择总是平安的；4证明通过做贪心选择，所有的子问题出一个以外都为空；5设计出一个实现贪心策略的递归算法；6将递归算法转换成迭代算法。c根据贪心选择来构造最优子构造：1将优化问题转化成这样一个问题，即先做出选择，再解决剩下的一个子问题；2证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的平安；3说明在做贪心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的最优解和我们所作的贪心选择联合起来，可以得出原问题的一个最优解。d贪心选择性质：证明定理e最优子构造性质：课本229页。6、搜索回溯法、剪枝函数、最小本钱优先。考点：回溯，剪枝函数，最小本钱优先的问题；分支界限法，剪枝函数所具备的性质。a回溯法：1定义：回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以到达目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点。2回溯法解题的步骤：a、针对所给的问题，定义问题的解空间；b、确定易于搜索的解空间构造；c、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数防止无效搜索。2回溯法解决的n后问题：在一个n * n的棋盘上放置n个王后，使得n后彼此不受攻击。3回溯法解决0-1背包问题：附：证明局部背包问题具有贪心选择性质。课本练习题：c 剪枝函数：约束函数：剪去不满足约束函数的子树； 限界函数：剪去由限界函数说明不能得到最优解的子树。剪枝函数的必要条件：典型例题：1求不等式的整数解 5x1+4x2-x3<=10, 1<=xj<=3, i =1,2,3 2装载问题：c最小本钱优先算法：注：分支限界的根本思想：1 回溯法的深度优先比拟盲目2 广度优先代价太高4 能优先搜索那些最有希望得到解的路径6 深入分析问题，得到有用的启发信息7 利用启发信息构造本钱函数8 最小本钱优先的搜索策略9 结合剪枝函数典型题型：重拍九宫问题。7、最大流概念，最大流-最小割定理，Edmonds-Karp算法。考点：最大流的相关概念，最大流最小割定理，Edmonds-Karp算法，要求掌握Ford-Fulkerson算法的相关内容。1流网络定义：有向图G = (V, E)，如果图G满足： 存在源结点(source) ss的入度为0 存在汇结点(sink) tt的出度为0 任意结点vV，有s v t 容量函数C： E R+称G为流网络。流的定义：流网络G，假设函数 p：V XV R+满足下述条件： 容量限制：对任意(u,v) E，有0<=p(u,v)<=c(u,v) 守恒条件：对任意u (V-s,t)，有 那么称p为G上的流。注意课本399页的引理。2对源点顶点来说，离开它的正流要比进入它的正流更多；对汇点顶点来说，进入它的正流要比离开它的正流更多。先证明如下：|f|=fs，V =fV，V-fV-s，V =fV，V-s =fV，t+fV，V-s-t =fV，t3Ford-Fulkerson方法：此方法依赖三中重要思想，a、残留网络；b、增广路径；c、割。这些是最大流最小割定理的精华。Ford-Fulkerson方法沿增广路径反复增加流，知道找出最大流为止；而最大流最小割定理告诉我们：一个流是最大流，当且仅当它的残留网络不包含增广路径。一、残留网络：在不超过容量cu，v的条件下，从u到v之间可以压入的额外网络流量，就是u，v残留容量，定义为cfu，v=cu，v-fu，v。注意课本401页的残留网络的例子。残留网络Gf本身也是一个流网络，其容量由cf给出，且|Ef|<=2|E|。注意课本402页的引理26.2。二、增广路径：注意课本403页引理26.3和引理26.4。三、流网络的割：注意403页的几个引理。四、最大流最小割定理：几个相互等价的条件。FORD-FULKERSON(G, s, t)1 for each edge (u, v) EG 2 do fu, v 0 3 fv, u 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) min cf(u, v) : (u, v) is in p 6 for each edge (u, v) in p 7 do fu, v fu, v + cf(p) 8 fv, u -fu, v FORD-FULKERSON的复杂性：FORD-FULKERSON过程的运行时间取决于如何决定第四行中的增广路径，选择不好，算法可能不会终止。假设容量是整数 13行O(|E|) 48循环执行O(|f*|) 找增广路O(|E|) O(|E|f*|)FORD-FULKERSON算法有其缺点，可以参照课本406页。4Edmonds-Karp算法：如果在第四行中用广度优先搜索来实现对增光路径p的计算。即如果增光路径是残留网络中从s到t的最短路径其中每条边为单位距离，或权，那么能够改良FORD-FULKERSON算法的界；称FORD-FULKERSON方法的这种实现为Edmonds-Karp算法。Edmonds-Karp算法的运行时间为OV*E2注意课本407页关于Edmonds-Karp算法的一些证明。8、NP完全问题多项式时间规约。考点：多项式时间内的规约问题，掌握NP 完全问题的证明方法。P类问题：是在多项式时间内可解的问题，即都是在Onk时间内求解的问题，此处k为某个常数，n是问题的输入规模。NP类问题：是在多项式时间内“可验证的问题即能够在问题输入规模的多项式时间内，验证该问题是正确的。注意：P问题包含于NP问题。但P不一定是NP问题的真子集。NPC问题：NP完全问题，即任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就成为NPC问题。换言之，如果这个问题解决了，那么所有的NP问题也都能解决了。假设问题L满足 L NP, and LP L for every L NP.那么问题L是NPC的，假设L只满足条件2那么称问题是NP-hard的。注意：如果任何NP完全问题可以在多项式时间内解决，那么NP中所有问题都有一个多项式时间的算法。1多项式时间内的规约： 假设问题2可以被多项式时间求解，那么问题1也可被多项式时间求解； 假设问题1不能被多项式时间求解，那么问题2也不能多项式时间求解； problem1 p problem2说明：问题1的求解不“难于问题2。假定一个判定问题A和另外一个不同的判定问题B，在一个过程中，它能将A的任何势力a转换为B的、具有以下特征的势力b：a、转化操作需要多项式时间；b、两个实例的答案是一样的，即a的答案是“是，当且仅当b的答案也是“是，称这样的过程为多项式时间的规约算法。可以参照课本599页的图。a、给定问题A的一个实例a，利用多项式时间规约算法，将它转换为问题B的一个实例b。b、在实例b上，运行B的多项式时间判定算法。c、将b的答案用作a的答案。可以将对问题A的求解“规约为对问题B的求解。注意：第一个NP完全问题就是电路可满足性问题。2NP完全性与可归约性：3电路可满足性问题：引理：电路可满足性问题属于NP类、NP难度及NP完全的。例题解析：1、设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个局部，找出一种分法，使得这K+1个局部的乘积能够为最大。EX：有一个数字串：312，当N=3，K=1时会有以下两种分法：3*12=36、31*2=62，这时，符合题目要求的结果是：31*2=62。2、Olay教授是一家石油公司的参谋，这家公司正在方案建造一条由东向西的大型管道，它穿过一个有n口油井的油田。从每口井中都有一条喷油管道沿最短路径与主管道直接连接或南或北。给定各口井的x坐标和y坐标，应如何选择主管道的最优位置使得各喷管长度总和最小？证明最优位置可在线性时间内确定。3、NPC证明：如集合的等划分问题，TSP问题，最小顶点覆盖问题。一、证明：顶点覆盖问题是NP完全问题。将3SAT变换到VC. 设U=u1,u2,.,un, C=c1,c2,.,cm是3SAT的实例. 如下构造图G, 分量设计法. 真值安排分量: Ti=(Vi,Ei), 1£i£n, 其中Vi=ui,i, Ei=ui,i任意覆盖必至少包含ui或i中的一个,否那么不能覆盖边ui或i. 满足性检验分量: Sj=(Vj,Ej), 1£ j£ m, 其中 Vj=a1j,a2j,a3j Ej=a1j,a2j,a1j,a3j,a2j,a3j覆盖至少包含Vj中的两个顶点,否那么不能覆盖Ej中的三角形 联络边: 沟通分量之间的关系 对于每个子句cj, 设cj = xj,yj,zj, 那么 Ej=a1j,xj,a2j,yj,a3j,zj G = (V,E) V = (V1ÈV2È.ÈVn)È(V1ÈV2È.ÈVm) E = E1ÈE2È.ÈEn)È(E1ÈE2È.ÈEm) È(E1ÈE2È.ÈEm) K = n +2m显然构造可在多项式时间完成例如U = u1,u2,u3,u4, C = u1,3,4,1,u2,4,那么G如下，K = 4 + 2×2 = 8设V是V中不超过K的顶点覆盖, 那么V中必包含Ti中的一个顶点和每个Ej中的两个顶点, 至少要n+2m个顶点. 而K=n+2m, 故V中一定只包含每个Ti中的一个顶点和每个Ej中的两个顶点. 如下得到赋值 uiÎV Û t(ui)=T iÎV Û t(ui)=F Ej中的三条边有两条被VjÇV中的顶点覆盖, 第三条必被VÇVi中的顶点覆盖. 这表示在Vi中的这个顶点对应的文字取真. 所以子句cj被满足. 从而C被满足. 设t: U®T,F是满足C的一组赋值. 假设t(ui)=T, 那么在Ti中取顶点ui, 否那么取i. 因为t满足子句cj, 在Ej中的三条联络边中至少有一条被覆盖, 那么取Ej中的另两条边的端点作为V中的端点即可. 二、证明：TSP旅行商问题问题是NP完全问题。 首先来说明TSP问题属于NP。给定该问题的一个实例，用回路中n个顶点组成的序列作为证书。验证算法检查该序列是否恰好包含每个顶点一次，并且对边的费用求和后，检查和是否至多为k。为了证明TSP是NP难度的，先证明HAM-CYCLE<=PTSP。设G=V，E是HAM-CYCLE额一个实例。构造TSP的实力如下，建立一个完全图G=V，E，其中E=i，j：i，j属于V且i！=j，定义费用函数为ci，j=0，如果i，j属于E 1，如果i，j不属于ENotice：因为G是无向图，它没有自环路，因而对所有的顶点v属于V，都有cv，v=1，于是<G，c，0>就是TSP的一个实例，它很容易在多项式时间内产生。现在说明图G中具有一个汉密尔顿回路，当且仅当图G中有一个费用至多为0的回路。假定图G中有一个汉密尔顿回路h，h中的每条边度属于E，因此在G中的费用为0。因此h在G中的费用为0的回路。反之，假定图G中有一个费用h至多为0的回路。由于E中边的费用只能是0或1，故回路h的费用就是0，且回路上每条边的费用必为0。故h仅包含E中的边。三、证明：集合的等划分问题是NP完全问题。实例：有穷集A，"aÎA, s(a)ÎZ+. 问：是否存在AÍA，使得显然均分是NP类问题。下面将3DM变换到均分问题 设W,X,Y,M Í W´X´Y 是3DM的实例，其中|W| = |X| = |Y| = q， W = w1,w2, ,wq X = x1,x2, ,xq Y = y1,y2, ,yq M = m1,m2, ,mk构造A，|A| = k +2对应于每个mi = (wf(i),xg(i),yh(i) 有ai.s(ai)为二进制数，分成3q段，每段有p = élog(k+1)ù位,共计3pq位，每段对应一个WÈXÈY中的元素. Wf(i),xg(i),yh(i) 所代表的段的最右位为1，其它为0. w1w2wqx1x2xqy1y2yq注：p³log(k+1)，2p ³k+1，k£ 2p-1 , 当 k个1相加时不会产生段之间的进位令B的段数与s(ai)一样，每段的最右位为1，其它为0例如：W=w1,w2,X=x1,x2,Y=y1,y2, M=(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)p=élog(3+1)ù=2元素a1,a2,a3分别对应 (w1,x2,y2),(w1,x2,y1),(w2,x1,y1) s(a1) = 01 00 00 01 00 01 = 210 + 24 + 20 s(a2) = 01 00 00 01 01 00 = 210 + 24 + 22 s(a3) = 00 01 01 00 01 00 = 28 + 26 + 22 B = 01 01 01 01 01 01 子集A = ai:1£i£k 满足 当且仅当 M = mi: aiÎA是M的匹配 A的最后两个元素b1,b2 考虑包含b1的子集A, 必有因此A-b1的元素对应的三元组构成M的匹配反之，假设子集M构成M的匹配，那么 A = b1Èai: miÎM满足证明题的考点：1、正确性证明问题。2、替换法证明问题。3、贪心选择性质证明问题。4、NP完全问题的证明。5、最大流问题的证明。简单题的考点：1、回溯法根本思想和步骤。2、分治算法的根本方法和步骤。3、搜索算法的根本方法和步骤。4、动态规划问题的根本方法和步骤。5、分支界限算法的根本方法和步骤。