算法导论复习资料

《算法导论复习资料》由会员分享，可在线阅读，更多相关《算法导论复习资料（17页珍藏版）》请在装配图网上搜索。

1、算法导论复习资料一、选择题：第一章的概念、术语。二、考点分析：1、复杂度的渐进表示，复杂度分析。2、正确性证明。考点： 1）正确性分析（冒泡，归并，选择）； 2）复杂度分析（渐进表示O， ? ，替换法证明，先猜想，然后给出递归方程）。循环不变性的三个性质：1）初始化：它在循环的第一轮迭代开始之前，应该是正确的；2）保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确；3）当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。插入排序算法：INSERTION-SORT(A)1 for j 2 to lengthA2 do key Aj3?

2、Insert Aj into the sorted sequence A1 ， j - 1.4i j - 15while i 0 and Ai key6do Ai + 1 Ai7i i - 18Ai + 1 key插入排序的正确性证明：课本11页。归并排序算法：课本17页及 19页。归并排序的正确性分析：课本20页。3、分治法（基本步骤，复杂度分析）。许多问题都可以递归求解考点：快速排序，归并排序，渐进排序，例如：12 球里面有一个坏球，怎样用最少的次数找出来。（解：共有 24种状态，至少称重3次可以找出不同的球）不是考点：线性时间选择，最接近点对，斯特拉算法求解。解：基本步骤：一、分解：将原

3、问题分解成一系列的子问题；二、解决：递归地解各子问题。若子问题足够小，则直接求解；三、合并：将子问题的结果合并成原问题的解。复杂度分析：分分治算法中的递归式是基于基本模式中的三个步骤的，T(n)为一个规模为 n的运行时间，得到递归式T(n)=Q(1)nc附加习题：请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S和另一个整数 x时，判断出 S中是否存在有两个其和等于x的元素。4、动态规划（最优子结构性质，自底向上填表计算最优解值（即最长公共子序列），导出最优解）。考点：最优子结构性质，自底向上填表计算最优解值，导出最优解。a）动态规划算法设计的4个步骤： 1）描

4、述最优解的结构；2）递归定义最优解的值；3）按自底向上的方式计算最优解的值；4 ）由计算出的结果构造一个最优解。b）最优子结构遵循的共同模式：1）问题的一个解可以是做一个选择，做这种选择可能会得到一个或多个有待解决的子问题；2）假设对一个给定的问题，已知的是一个可以导致最优解的选择，不必关心如何确定这个选择，尽管假定它是已知的；3）在已知这个选择后，要确定哪些子问题会随之发生， 以及如何最好地描述所得到的子问题的空间；4）利用一种 “剪切粘贴法 ”，来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。备注： A problemexhibits optimal substructur

5、e if an optimal solution to the problemcontains within it optimalsolutions to subproblems.Whenevera problemexhibitsoptimalsubstuctureitis a goodcluethatdynamicprogramming might apply.c）最长公共子序列的算法：这里以两个序列X=x1,x2,xm和 Y=y1,y2,yn为输入，注意课本211页的自底向上填表方法。LCS-LENGTH(X, Y)注：此程序运行时间为O（ mn ），每个表项的计算时间为O（ 1）1 m

6、lengthX2 n lengthY3 for i 1 to m4 do ci, 0 05 for j 0 to n6 do c0, j 07 for i 1 to m8 do for j 1 to n9do if xi = yj10then ci, j ci - 1, j - 1 + 111bi, j “=12else if ci - 1, j ci, j - 113thenci, j ci - 1, j14bi, j 15else ci, j ci, j - 116bi, j 17 returnc and bPRINT-LCS(b, X, i, j)注：此程序运行时间为1 if i = 0

7、 or j = 0O（m+n ）2 then return3 if bi, j = =4 then PRINT-LCS(b, X, i - 1, j - 1)5print xi6 elseifbi, j = 7then PRINT-LCS(b, X, i - 1, j)8else PRINT-LCS(b, X, i, j - 1)d）矩阵链乘法的算法：参照课本上的矩阵链表得出矩阵相乘的最小算法。m i , j m in mi , k m k1, j ikjpi 1 pk p j MATRIX-CHAIN-ORDER(p) 每个表项的复杂度是O（n ），共有 O（ n2 ）表项，则为O（ n3

8、）1n lengthp - 12fori 1 to n3do mi, i 04forl 2 to n ?l is the chain length.5do for i 1 to n - l + 16do j i + l - 17mi, j 8for k i to j - 19do q mi, k + mk + 1, j + pi-1 pkpj10if q mi, j11then mi, j q12si, j k13return m and sPRINT-OPTIMAL-PARENS(s, i, j)1 if i = j2then print Ai 3else print (4PRINT-OPT

9、IMAL-PARENS(s, i, si, j)5PRINT-OPTIMAL-PARENS(s, si, j + 1, j)6 print )e）备忘录算法： 1）程序结构采用自顶向上；2）保留了递归结构，开销较大；3）当所有的子问题都需要求解时，自底向上的方法效率较高，否则可以采用备忘录方法。备忘录算法的代码可以参照课本207页。f ）最优二叉查找树：1 ）一棵最优二叉查找树不一定是一棵整体高度最小的树，也不一定总是把有最大概率的关键字放在根部来构造一棵最优二叉查找树。5、贪心法（最优子结构性质+贪心选择性质） 。考点：学会证明最优子结构性质和贪心选择性质的问题。a）活动选择问题：0ifSi

10、jci , j max ci ,k c k, j 1ifSiji k j注意课本上 224页地贪婪法定理证明，这就是贪婪法的合理性证明。RECURSIVE-ACTIVITY-SELECTOR(s, f, i, j)1 m i + 12 while m j and sm fi ? Find the first activity in Sij.3 do m m + 14 if m j5then returnam RECURSIVE-ACTIVITY-SELECTOR(s, f, m, j)6 else returnGREEDY-ACTIVITY-SELECTOR(s, f)1 n lengths2

11、 A a13 i 1 24 for m 2 to n5do if sm fi6then A A am7i m8 returnAb）贪心算法遵循的步骤：1）决定问题的最优子结构；2）设计出一个递归解；3）证明在递归的任一阶段，最优选择之一总是贪心选择，那么，做贪心选择总是安全的；4）证明通过做贪心选择，所有的子问题（出一个以外）都为空；5）设计出一个实现贪心策略的递归算法；6）将递归算法转换成迭代算法。c）根据贪心选择来构造最优子结构：1）将优化问题转化成这样一个问题，即先做出选择，再解决剩下的一个子问题；2）证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的安全； 3）说明在做贪

12、心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的最优解和我们所作的贪心选择联合起来，可以得出原问题的一个最优解。d）贪心选择性质：证明定理e）最优子结构性质：课本229页。6、搜索（回溯法、剪枝函数、最小成本优先）。考点：回溯，剪枝函数，最小成本优先的问题；分支界限法，剪枝函数所具备的性质。a）回溯法：1）定义：回溯法(探索与回溯法 )是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点 ”。2）回溯法解题的步骤：a、针对所给的问题，定义问

13、题的解空间；b、确定易于搜索的解空间结构；c、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。2）回溯法解决的n 后问题：在一个n * n 的棋盘上放置n个王后，使得n后彼此不受攻击。3）回溯法解决0-1背包问题：附：证明部分背包问题具有贪心选择性质。课本练习题：c 剪枝函数：约束函数：剪去不满足约束函数的子树；限界函数：剪去由限界函数表明不能得到最优解的子树。P( x1 , x2 ,., xk 1) P( x1 , x2 ,.,xk )0kn剪枝函数的必要条件：典型例题： 1）求不等式的整数解5x1 +4x2x310, 1xj3, i =1,2,32）装载问题：c）最小成本优

14、先算法：注：分支限界的基本思想：1回溯法的深度优先比较盲目2广度优先代价太高4 能优先搜索那些最有希望得到解的路径6 深入分析问题，得到有用的启发信息7 利用启发信息构造成本函数8 最小成本优先的搜索策略9 结合剪枝函数典型题型：重拍九宫问题。7、最大流（概念，最大流-最小割定理，Edmonds-Karp 算法）。考点：最大流的相关概念，最大流 最小割定理， Edmonds-Karp算法，要求掌握 Ford-Fulkerson算法的相关内容。1）流网络定义：有向图G = (V, E)，如果图 G满足：存在源结点 (source) s（ s的入度为 0）存在汇结点 (sink) t（ t 的出度

15、为 0）任意结点 vV，有 s v t+容量函数C： E R流的定义：流网络G，若函数p： V XV R+满足下述条件：容量限制：对任意(u,v) E，有 0=p(u,v)=c(u,v)守恒条件：对任意u (V-s,t)，有则称 p为 G上的流。注意课本 399页的引理。2）对源点顶点来说，离开它的正流要比进入它的正流更多；对汇点顶点来说，进入它的正流要比离开它的正流更多。先证明如下： |f|=f （ s， V）=f（ V， V）-f （ V-s，V）=f（ V， V-s）=f（ V， t ） +f（ V， V-s-t）=f（ V， t ）3）Ford-Fulkerson方法：此方法依赖三中重

16、要思想，a、残留网络；b、增广路径；c、割。这些是最大流最小割定理的精髓。 （ Ford-Fulkerson方法沿增广路径反复增加流，知道找出最大流为止；而最大流最小割定理告诉我们：一个流是最大流，当且仅当它的残留网络不包含增广路径。）一、残留网络：在不超过容量c（u ， v）的条件下，从u到 v之间可以压入的额外网络流量，就是（ u， v）残留容量，定义为cf（ u， v） =c（ u， v） -f （u ，v）。注意课本 401页的残留网络的例子。残留网络 Gf本身也是一个流网络，其容量由cf给出，且 |E f|=2|E| 。注意课本 402页的引理。二、增广路径：注意课本403页引理和引

17、理。三、流网络的割：注意403页的几个引理。四、最大流最小割定理：几个相互等价的条件。FORD-FULKERSON(G, s, t)1 for each edge (u, v) EG2do fu, v 03fv, u 04 whilethere exists a path p from s to t in the residual network G f5do cf(p) min cf(u, v) : (u, v) is in p6for each edge (u, v) in p7do fu, v fu, v + cf(p)8fv, u -fu, vFORD-FULKERSON的复杂性： F

18、ORD-FULKERSON过程的运行时间取决于如何决定第四行中的增广路径，选择不好，算法可能不会终止。假设容量是整数? 13行 O(|E|)? 48循环执行 O(|f*|)? 找增广路 O(|E|)? O(|E|f*|)FORD-FULKERSON算法有其缺点，可以参照课本406页。4）Edmonds-Karp算法：如果在第四行中用广度优先搜索来实现对增光路径p的计算。即如果增光路径是残留网络中从s到 t 的最短路径（其中每条边为单位距离，或权），则能够改进FORD-FULKERSON算 法 的 界 ； 称 FORD-FULKERSON方 法 的 这 种 实 现 为 Edmonds-Karp

19、算 法 。Edmonds-Karp算法的运行时间为O（ V*E2）注意课本 407页关于 Edmonds-Karp算法的一些证明。8、 NP完全问题（多项式时间规约）。考点：多项式时间内的规约问题，掌握NP 完全问题的证明方法。P类问题：是在多项式时间内可解的问题，即都是在O（nk）时间内求解的问题，此处k为某个常数， n是问题的输入规模。NP类问题：是在多项式时间内“可验证”的问题即能够在问题输入规模的多项式时间内，验证该问题是正确的。注意：P问题包含于NP问题。但P不一定是NP问题的真子集。NPC问题：NP完全问题，即任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个

20、NP问题就成为NPC问题。换言之，如果这个问题解决了，那么所有的NP问题也都能解决了。 若问题 L满足L NP, andL P L for every L NP.则问题 L是 NPC的，若 L只满足条件 2则称问题是 NP-hard 的。注意：如果任何 NP完全问题可以在多项式时间内解决，则 NP中所有问题都有一个多项式时间的算法。1）多项式时间内的规约：若问题 2可以被多项式时间求解，则问题1也可被多项式时间求解；若问题 1不能被多项式时间求解，则问题2也不能多项式时间求解； problem1 p problem2 表明：问题 1的求解不 “难 ”于问题 2。假定一个判定问题A和另外一个不同

21、的判定问题B，在一个过程中，它能将A的任何势力 a转换为B的、具有以下特征的势力b：a、转化操作需要多项式时间；b、两个实例的答案是相同的，即a的答案是“是” ，当且仅当 b的答案也是“是” ，称这样的过程为多项式时间的规约算法。可以参照课本599页的图。a、给定问题 A的一个实例 a，利用多项式时间规约算法，将它转换为问题B的一个实例 b 。b、在实例 b上，运行 B的多项式时间判定算法。c、将 b的答案用作 a的答案。可以将对问题 A的求解“规约”为对问题B的求解。注意：第一个 NP完全问题就是电路可满足性问题。2）NP完全性与可归约性：课本 609页引理3）电路可满足性问题：引理：电路可

22、满足性问题属于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坐标，应如何选择主管道的最优位置（使得各喷管长度总和最小

23、）证明最优位置可在线性时间内确定。3、 NPC证明：如集合的等划分问题，TSP问题，最小顶点覆盖问题。一、证明：顶点覆盖问题是NP完全问题。将 3SAT变换到 VC. 设 U=u1,u2,.,un, C=c1,c2,.,cm 是 3SAT的实例 . 如下构造图 G, 分量设计法.真值安排分量:Ti=(Vi,Ei), 1in, 其中 Vi=ui, i, Ei=ui,i任意覆盖必至少包含ui或i中的一个 ,否则不能覆盖边ui 或i.满足性检验分量:Sj=(Vj,Ej), 1jm,其中Vj=a1j,a2j,a3jEj=a1j,a2j,a1j,a3j,a2j,a3j覆盖至少包含 Vj 中的两个顶点,否

24、则不能覆盖 Ej中的三角形联络边 :沟通分量之间的关系对于每个子句cj, 设 cj = xj,yj,zj, 则Ej=a1j,xj,a2j,yj,a3j,zjG = (V,E)V=(V1V2 .Vn)(V1 V2 .Vm)E=E1E2 .En)(E1 E2 .Em)(E1E2.Em)K = n +2m显然构造可在多项式时间完成例如U = u1,u2,u3,u4,C = u1,3,4,1,u2, 4,则G如下， K=4+22=8设 V是 V中不超过 K的顶点覆盖, 则 V中必包含 Ti中的一个顶点和每个n+2m个顶点 . 而K=n+2m, 故 V中一定只包含每个Ti中的一个顶点和每个Ej中的两个顶

25、点Ej中的两个顶点, 至少要.如下得到赋值uiVt(ui)=TiVt(ui)=FEj中的三条边有两条被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个顶

26、点组成的序列作为证书。验证算法检查该序列是否恰好包含每个顶点一次，并且对边的费用求和后，检查和是否至多为 k。为了证明 TSP是 NP难度的，先证明 HAM-CYCLE=PTSP。设 G=（ V， E）是 HAM-CYCLE额一个实例。构造 TSP的实力如下，建立一个完全图 G=（V， E），其中 E=（ i， j）： i，j 属于 V且i！=j，定义费用函数为c（ i，j ） =0，如果（ i， j ）属于 E1，如果（ i， j ）不属于 ENotice：因为 G是无向图， 它没有自环路， 因而对所有的顶点v属于 V，都有 c（v，v）=1，于是 就是 TSP的一个实例，它很容易在多项式时

27、间内产生。现在说明图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，aA, s(a)Z+.s( a)s(a)问：是否存在 A A，使得 a A a AA显然均分是 NP类问题。下面将 3DM 变换到均分问题设W,X,Y,MW XY 是 3D

28、M的实例，其中 |W| = |X| = |Y| = q，W = w1,w2, ,wqX = x1,x2, ,xqY = y1,y2, ,yqM = m1,m2,mk构造 A， |A| = k +2对应于每个 mi = (wf(i),xg(i),yh(i)有 ai.s(ai)为二进制数，分成3q段，每段有 p =log(k+1)位 ,共计 3pq位，每段对应一个 WX Y中的元素 . Wf(i),xg(i),yh(i)所代表的段的最右位为1，其它为 0.s( a ) 2 p(3q f ( i )2 p( 2q g (i )2 p (q h (i )iw1w2wqx1x2xq y1y2yq注： p

29、 log(k+1)， 2pk+1， k2p1 ,当 k个1相加时不会产生段之间的进位令3q12 p( 3q 1)2 p( 3q 2 )22 p2p20B2 pj.j0B的段数与 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 + 20s(a2) = 01 00 00 01 01 00 =

30、210 + 24 + 22s(a3) = 00 01 01 00 01 00 = 28 + 26 + 22B=010101010101s( a)B子集 A= ai:1 ik满足aA 当且仅当 M= mi: aiA是 M 的匹配A的最后两个元素 b1,b2ks( b1 ) 2s(ai) Bi1ks( b2 )s( ai )Bi 1kk考虑包含 b1的子集 A,必有s( a)2 s(ai )(2 s( ai ) B) Ba A b1 i 1i 1因此 A-b1的元素对应的三元组构成M的匹配反之，若子集 M 构成 M 的匹配，则A= b1 ai: miM满足ks(a)(2s(ai )B )Ba A i1k2s( ai)s( a)i1aA A证明题的考点：1、正确性证明问题。2、替换法证明问题。3、贪心选择性质证明问题。4、NP完全问题的证明。5、最大流问题的证明。简单题的考点：1、回溯法基本思想和步骤。2、分治算法的基本方法和步骤。3、搜索算法的基本方法和步骤。4、动态规划问题的基本方法和步骤。5、分支界限算法的基本方法和步骤。