算法设计考点整理

1、一、证明题最近点对证明 ：假设需要比较的点不止 7 个，则由图可知，比较的点 >=8 个，则至少有一个 抽屉里有两个点，一个抽屉是长为d/2、宽为 d/2 的小正方形，两点之间的最大距离为根号2d/2<d，这与 d 是最小距离矛盾，所以需要比较的点的个数只有7 个。汉密尔顿路径证明 (作业题) ：给出引理： 最优路径上各点在插入路径时其路径变化量最小。 证明：对结点从小到大排序 k(1) 、 k(2)k(n) ， k( n)表示第 n 个结点的值 ,则路径长度为：(k(2)-k(1)+(k(3)-k(2)+(k(n)-k(n-1)=k(n)-k(1) ；所以从 i 点到 j 点的路

2、 径长 度为 ：k(i)-k(1)+k(n)-k(1)+k(n)-k(j)<=|k(a)-k(i)|+k(a)-k(1)+k(n)-k(1)+k(n)-k(b)+|k(j)-k(b)| 。可证引理正 确，所以从值最小结点到较大的结点路径最短。流值小于割容量证明 ：设是对应的相对流。因为 ( u，v)=f( u,v)-f(v,u) ，所以 ( u,v) <=f(u,v) 。因此，我们有 ( S,T) =求和 ( u,v) <=求和 f( u,v) <=求和 c(u,v)=c(S,T) 。所 以|f|= (S,T)<=c(S,T) 。最大流最小割定理证明 ：假定 Gf

3、=(V ,Ef,Cf)是对应于最大流 f的剩余网络。 那么 Gf 中必不存 在一条增广路径，否则， f 可以增广为值更大的流。我们定义一个割(S,T)。显然在 Gf 中没有从 S中点到 T中点的边。这说明在原网络 G中，任何一条从 S到 T的边( u,v),uS,v T，都有 cf(u,v)=c(u,v)-(u,v)=0，即 c(u,v)= (u,v) 。因为 |f|= ( S,T )=求和 ( u,v ) = 求和 c(u,v)=c(S,T) 。也就是说，这个最大流的值等于割(S,T)的容量。又因为最大流 f 的值小于等于任何一个割的容量，因此c(S,T) 也小于等于任何一个割的容量。所以，

4、割(S,T)的容量是所有割中最小的。FORD-FULKERSON(G , s, t)1: for each edge (u, v) E do2: fu, v 03: fv, u 04: end for5: while there exists a path P from s to t in the residual network Gfdo6: cf(P) mine P cf(e)7: for each edge (u, v) P do8: fu, v fu, v + cf(P)9: fv, u - fu, v10: end for11: end while二、算法题插入乘号算法cj,k 表示

5、长度为 j 的数字串中插入 k 个乘号的最大值d1,j 表示长度为 j 的数字串代表一个数字递归表达式为 cj,k=d1,j,k=0 或 maxcm,k-1*dm+1,j,k>0算法： for( d=0,j=1;j<=n;j+ )d=d*10+bj-1;cj0=d;for(s=1;s<=k;s+)for(i=s+1;i<=n;i+)for(j=s;j<i;j+)for(d=0;u=j+1;u<=i;u+)word 文档 可自由复制编辑 d=d*10+bu-1if(cik<cjk-1*d) cik=cjk-1*d;MST-KRUSKAL(G , w)1:

6、 A ?2: for each vertex v V do3: MAKE-SET(v)4: end for5: sort the edges of E into nondecreasing order by weight w6: for each edge (u, v) E, taken in nondecreasing order by weight do7: if FIND-SET(u) 6= FIND-SET(v) then8: AA (u, v)9: UNION(u, v)10: end if11: end for12: return A MST-PRIM(G , w, r) 1: f

7、or each u V do 2: keyu 3: u nil 4: end for 5: keyr 0 6: Q V 7: while Q 6= ? do 8: u EXTRACT-MIN(Q) 9: for each v Adju do 10: if v Q and w(u, v) <keyv then 11: v u 12: keyv w(u, v) 13: end if 14: end for 15: end while三、名词解释 什么是算法 ：一个由计算步骤构成的序列， 可以将一组输入值转换成相应的输出值， 或者是 用来解决一个明确定义的问题。算法特点 ：确定性，可行性，输入

8、和输出及有穷性。最优子结构性质 ：考察任意最优解；定义子问题；采用剪切粘贴法证明贪心选择性质 ：任取一个最优解； 若该最优解包含了贪心选择出的结果，贪心选择性质显然成立； 若不包含，调整该最优解，得到另一最优解包含贪心选择出的结果； 注意必须证明调 整后的解为最优解。简述循环不变性法证明算法正确性的过程Initialization ：在第一次循环开始前不变性是满足的 Maintenance：如果在某次迭代前不变性满足，在这次迭代后也满足不变性 Termination ：循环结束后，不变性可以提供程序正确性的有用信息 简述分治策略通常采用的步骤word 文档 可自由复制编辑 Divide ：将问

9、题分成多个子问题 Conquer：递归的解决每个子问题 Combine：将子问题的解合并成原问题的解 Master 定理 ： T(n) = aT(n/b) + f(n) 规则 1:若 f(n)=O( nlogb a-e)e为一常数， e>0则 T ( n)= (nlogb a)规则 2：若 f(n)= (nlogb alogk n )k 为一常数， k>0则 T( n)= (nlogb alogk+1 n)规则 3：若 f( n) =?(nlogb a+e) e 为一常数， e>0则 T( n)=(f(n)流网络定义 ：有向图 G(V ，E)，如果图 G 满足存在源结点 s，

10、存在汇结点 t，任意结点 v V，有 s v t，容量函数 c：V × V R 0(若(u, v) / E，则c(u, v) = 0)称 G为 流网络。网络流定义 ：流网络 G( V ， E，c)，映射： V × V R。若 f 满足下列三个性质： 容量限制： ? u, v V : f(u, v) c(u, v)反对称性： ? u, v V : f(u, v) = -f(v, u)守恒性： ? u V s, t : 求和 vVf(u, v) = 0 则称 f 为 G上的网络流剩余网络定义 ：设流网络 G(V ， E， c)，而 f为G中的一个流，定义顶点对 u, v V 的

11、 剩余容量为 cf(u, v) = c(u, v) - f(u, v) 。称Gf = (V, Ef, cf)为网络 G在流 f下的剩余网络，其 中 Ef = (u, v) V × V |cf(u, v) > 0增广路径 ：假设 f 是网络 G(V，E， c)中的一个流。对应于 f 的剩余网络 Gf = (V, Ef, cf) 中一条从源点到汇点的的简单路径p 称为一条增广路径。 这条路径上剩余容量最小的边称为关键边，其容量定义为这条路径上的剩余容量cf( p)=Mincf (u，v)|(u，v)p 。最大流最小割定理 ：设 f 是网络 G( V ，E，c)上的一个最大流，那么一

12、定存在一个割(S，T)使得 |f|=c( S，T)，并且这个割的容量是最小的。割与流量的关系 设G=(V,E，c)为流网络， f为G中的流，而(S,T)为 G的一个割，则 |f|=f(S,T);(2)|f| c(S,T) Prooff(S,T)=f(S,VS) |=f(S,V)-f(S,S)=f(s,V)+f(Ss,V)=|f|怎么做动态规划？(步骤) 本质上仍然是“大事化小”策略 所用的技巧：保存已求出小问题的解备用(1) 找出最优解的性质，并刻划其结构特征(2) 递归地定义最优值(3) 以规划的方式计算出最优值(4) 根据计算最优值时(自底向上的填表法、自顶向下的备忘录法)得到的信息，构造

13、最 优解区间套定理在算法 DFS( G( V,E)结束时，顶点 u的访问区间 d(u),f(u) 包含顶点 v 的访问区间 d(v),f(v) 当且仅当 u是v的祖先。如果 u和 v没有直系关系，它们的访问区间必不相交。白路径定理word 文档 可自由复制编辑 在算法 DFS（G（ V,E）执行过程中，顶点 v 成为顶点 u 的后代，当且仅当在时刻 d（u）， 图中存在一条从 u 到 v 的由白色顶点构成的路径。前向边、反向边、交叉边前向边：从某顶点出发的一条边指向该顶点的一个后代反向边：从某顶点出发的一条边指向该顶点的一个祖先 交叉边：从某顶点出发的一条边指向无直系亲属关系的顶点 P 与 NP 的概念和关系P类：容易的问题类，可以在多项式时间内求解的问题类NP 类：可能包含困难的类，可以在多项式时间内验证问题解的问题类。显然， P NP NPC若问题 L 满足：（ 1）L NP，并且（