算法导论复习资料

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

2、j3? 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)n<=cT(n)=aT(n/b)+D(n)+C(n)n>c附加习题：请给出一个运行时间为 Q(nlgn) 的算法，使之能在给定的一个由 n 个整数构成的集合 S 和另一个整数 x时，判断出 S中是否存在有两个其和等于 x的元素。Word 资料.Word 资料.4、动态规划（最优子结构性质，自底向上填表计

4、算最优解值（即最长公共子序列），导出最优解）。考点：最优子结构性质，自底向上填表计算最优解值，导出最优解。a）动态规划算法设计的 4个步骤： 1 ）描述最优解的结构；2）递归定义最优解的值； 3）按自底向上的方式计算最优解的值；4）由计算出的结果构造一个最优解。b ）最优子结构遵循的共同模式：1 ）问题的一个解可以是做一个选择，做这种选择可能会得到一个或多个有待解决的子问题；2）假设对一个给定的问题， 已知的是一个可以导致最优解的选择，不必关心如何确定这个选择，尽管假定它是已知的；3）在已知这个选择后，要确定哪些子问题会随之发生， 以及如何最好地描述所得到的子问题的空间；4 ）利用一种 “剪切

5、粘贴法 ”，来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。备注： Aproblemexhibits optimal substructureif an optimal solutionto theproblemcontainswithin itoptimal solutions to subproblems.Word 资料.Whenever a problem exhibits optimal substucture it is a good clue that dynamic programming might apply.c）最长公共子序列的算法：这里以两个序列 X=x1

6、,x2, ,xm和 Y=y1,y2, ,yn为输入，注意课本211页的自底向上填表方法。LCS-LENGTH(X, Y)注：此程序运行时间为O（ mn ），每个表项的计算时间为O（ 1）1 m 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 m8do for j 1 to n9do ifxi = yj10thenci, j ci - 1, j - 1 + 111bi, j “="12else if ci - 1, j ci, j - 113then ci, j ci

7、- 1, j14bi, j ""15elseci, j ci, j - 116bi, j " "17 returnc and bPRINT-LCS(b, X, i, j)注：此程序运行时间为O（ m+n ）1 if i = 0 or j = 02 then return3 if bi, j = "="4 then PRINT-LCS(b, X, i - 1, j - 1)5print xi6elseifbi, j = " "7then PRINT-LCS(b, X, i - 1, j)8else PRINT-LCS

8、(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 ）1 n lengthp - 12 for i 1 to nWord 资料.3do mi, i 04for l 2 ton ? l is the chain length.5do fori 1 ton - l + 16do j i + l - 17mi, j 8for k i to j - 19do

9、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)1ifi = j2then print "Ai "3else print "("4PRINT-OPTIMAL-PARENS(s, i, si, j)5PRINT-OPTIMAL-PARENS(s, si, j + 1, j)6 print ")"e）备忘录算法： 1）程序结构采用自顶向上； 2）保留了递归结

10、构，开销较大； 3）当所有的子问题都需要求解时，自底向上的方法效率较高，否则可以采用备忘录方法。备忘录算法的代码可以参照课本207 页。f）最优二叉查找树：1 ）一棵最优二叉查找树不一定是一棵整体高度最小的树，也不一定总是把有最大概率的关键字放在根部来构造一棵最优二叉查找树。5、贪心法（最优子结构性质+ 贪心选择性质） 。考点：学会证明最优子结构性质和贪心选择性质的问题。a）活动选择问题：0ifSijci , j maxikj ci ,k c k, j 1ifSij注意课本上 224页地贪婪法定理证明，这就是贪婪法的合理性证明。RECURSIVE-ACTIVITY-SELECTOR(s, f,

11、 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 A a1Word 资料.3 i 1 24 for m 2 to n5do if sm fi6then A A am7i m8 returnAb ）贪心算法遵循的步骤：1）决定

12、问题的最优子结构；2 ）设计出一个递归解；3）证明在递归的任一阶段，最优选择之一总是贪心选择，那么，做贪心选择总是安全的；4）证明通过做贪心选择，所有的子问题（出一个以外）都为空；5 ）设计出一个实现贪心策略的递归算法；6）将递归算法转换成迭代算法。c）根据贪心选择来构造最优子结构：1）将优化问题转化成这样一个问题，即先做出选择，再解决剩下的一个子问题；2）证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的安全； 3）说明在做贪心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的最优解和我们所作的贪心选择联合起来，可以得出原问题的一个最优解。d ）贪心选择性质：证明定理 1

13、6.1e）最优子结构性质：课本229页。6、搜索（回溯法、剪枝函数、最小成本优先）。考点：回溯，剪枝函数，最小成本优先的问题；分支界限法，剪枝函数所具备的性质。a）回溯法：1）定义：回溯法(探索与回溯法 )是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点 ”。2）回溯法解题的步骤：a、针对所给的问题，定义问题的解空间；b 、确定易于搜索的解空间结构；c、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。2）回溯法解决的n后问题：在一

14、个n * n 的棋盘上放置n个王后，使得n后彼此不受攻击。3 ）回溯法解决 0-1 背包问题：附：证明部分背包问题具有贪心选择性质。课本练习题 16.2-3 ：Word 资料.c 剪枝函数：约束函数：剪去不满足约束函数的子树；限界函数：剪去由限界函数表明不能得到最优解的子树。P( x1 , x2 ,., xk 1) P( x1 , x2 ,.,xk )0k剪枝函数的必要条件：典型例题： 1）求不等式的整数解5x1+4x 2x32 ）装载问题：c）最小成本优先算法：注：分支限界的基本思想：1回溯法的深度优先比较盲目2广度优先代价太高4 能优先搜索那些最有希望得到解的路径6 深入分析问题，得到有用

15、的启发信息n10, 1xj3, i =1,2,3Word 资料.7 利用启发信息构造成本函数8 最小成本优先的搜索策略9 结合剪枝函数典型题型：重拍九宫问题。7、最大流（概念，最大流- 最小割定理，Edmonds-Karp算法）。考点：最大流的相关概念， 最大流 最小割定理， Edmonds-Karp 算法，要求掌握 Ford-Fulkerson 算法的相关容。1）流网络定义：有向图G = ( V, E)，如果图 G满足：存在源结点 (source) s（ s的入度为 0）存在汇结点 (sink) t（ t的出度为 0）任意结点 v V，有 s v t+容量函数C： E R流的定义：流网络G，

16、若函数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 方法：此方法依赖三中重要思想，a、残留网络； b 、增广路

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

18、6.3 和引理 26.4 。三、流网络的割：注意403页的几个引理。四、最大流最小割定理：几个相互等价的条件。FORD-FULKERSON(G, s, t)1 foreach edge (u, v) EG2do fu, v 03fv, u 04 whilethere exists a path p from s to t in the residual network G5do cf(p) min cf(u, v) : (u, v) is in p6for each edge (u, v) in p7do fu, v fu, v + cf(p)fWord 资料.8fv, u -fu, vFOR

19、D-FULKERSON的复杂性： FORD-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方法的这种实现为Edmond

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

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

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

23、34.33）电路可满足性问题：引理：电路可满足性问题属于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口油井的油田。从每口井中都有一条喷油管道沿最短路径与主管道直接连接（或南或北）。给定各口井的

24、 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 ), 1jm,其中Vj =a1j,a2j,a3jE

25、j =a1j,a2j,a1j,a3j,a2j,a3j覆盖至少包含 Vj 中的两个顶点 ,否则不能覆盖 Ej 中的三角形联络边 :沟通分量之间的关系对于每个子句cj, 设cj = xj,yj,zj,则Ej =a1j,xj,a2j,yj,a3j,zjG = (V,E)V = (V1V2. Vn)(V1V2. Vm )E = E1E2.En)(E1E2. Em)(E1E2.Em )K = n +2m显然构造可在多项式时间完成例如U = u1,u2,u3,u4,C = u1, 3,4,1,u2,4,则G如下， K=4+2 ×2=8Word 资料.设 V 是 V 中不超过 K的顶点覆盖 , 则

26、 V 中必包含 Ti中的一个顶点和每个 Ej 中的两个顶点 , 至少要 n+2m 个顶点 . 而 K=n+2m, 故 V 中一定只包含每个 Ti中的一个顶点和每个 Ej 中的两个顶点.如下得到赋值uiVt(ui)=Ti Vt(ui)=FEj 中的三条边有两条被VjV 中的顶点覆盖, 第三条必被 VVi中的顶点覆盖. 这表示在 Vi中的这个顶点对应的文字取真. 所以子句 cj被满足 . 从而 C被满足 .设 t: UT,F是满足 C的一组赋值 . 若 t(ui)=T,则在 Ti中取顶点 ui, 否则取i. 因为 t满足子句 cj,在 Ej 中的三条联络边中至少有一条被覆盖, 那么取 Ej 中的另

27、两条边的端点作为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 ，定义费用函数为c（ i， j） =0 ，如果（ i， j）属

28、于 E1，如果（ i， j）不属于 ENotice ：因为 G是无向图，它没有自环路，因而对所有的顶点v属于 V，都有 c（v， 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，使得s( a)s(a)显然均分是aA 'a A A'NP 类问题。下面将3DM 变换到均分问题设W,X,Y,MW X Y 是3DM 的实例，其中 |W| = |X| = |Y| = q ，W = w1,w2,wqX = x1,x2, ,xqY = y1,y2,yqM = m1,m2,mkWord 资料.构造 A， |A| = k +2对应于每个 mi = (wf(i),xg(i),yh(i)有 ai.s(ai)为二进制数，分成3q 段，每段有 p =l