算法导论复习资料.docx
《算法导论复习资料.docx》由会员分享，可在线阅读，更多相关《算法导论复习资料.docx（19页珍藏版）》请在冰点文库上搜索。
算法导论复习资料
算法导论复习资料
一、选择题：
第一章的概念、术语。
二、考点分析：
1、复杂度的渐进表示，复杂度分析。
2、正确性证明。
考点：
1）正确性分析（冒泡，归并，选择）；2）复杂度分析（渐进表示O，Ｑ，?
，替换法证明，先猜想，然后给出递归方程）。
循环不变性的三个性质：
1）初始化：
它在循环的第一轮迭代开始之前，应该是正确的；
2）保持：
如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确；
3）当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。
插入排序算法：
INSERTION-SORT（A）
1forj←2tolength[A]
2dokey←A[j]
3?
InsertA[j]intothesortedsequenceA[1，j-1].
4i←j-1
5whilei>0andA[i]>key
6doA[i+1]←A[i]
7i←i-1
8A[i+1]←key
插入排序的正确性证明：
课本11页。
归并排序算法：
课本17页及19页。
归并排序的正确性分析：
课本20页。
3、分治法（基本步骤，复杂度分析）。
——许多问题都可以递归求解
考点：
快速排序，归并排序，渐进排序，例如：
12球里面有一个坏球，怎样用最少的次数找出来。
（解：
共有24种状态，至少称重3次可以找出不同的球）
不是考点：
线性时间选择，最接近点对，斯特拉算法求解。
解：
基本步骤：
一、分解：
将原问题分解成一系列的子问题；
二、解决：
递归地解各子问题。
若子问题足够小，则直接求解；
三、合并：
将子问题的结果合并成原问题的解。
复杂度分析：
分分治算法中的递归式是基于基本模式中的三个步骤的，T（n）为一个规模为n的运行时间，得到递归式
T（n）=Q
（1）n<=c
T（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）利用一种“剪切粘贴法”，来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。
备注：
Aproblemexhibitsoptimalsubstructureifanoptimalsolutiontotheproblemcontainswithinitoptimalsolutionstosubproblems.
Wheneveraproblemexhibitsoptimalsubstuctureitisagoodcluethatdynamicprogrammingmightapply.
c）最长公共子序列的算法：
这里以两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}为输入，注意课本211页的自底向上填表方法。
LCS-LENGTH（X,Y）注：
此程序运行时间为O（mn），每个表项的计算时间为O
（1）
1m←length[X]
2n←length[Y]
3fori←1tom
4doc[i,0]←0
5forj←0ton
6doc[0,j]←0
7fori←1tom
8doforj←1ton
9doifxi=yj
10thenc[i,j]←c[i-1,j-1]+1
11b[i,j]←“="
12elseifc[i-1,j]≥c[i,j-1]
13thenc[i,j]←c[i-1,j]
14b[i,j]←"↑"
15elsec[i,j]←c[i,j-1]
16b[i,j]←"←"
17returncandb
PRINT-LCS（b,X,i,j）注：
此程序运行时间为O（m+n）
1ifi=0orj=0
2thenreturn
3ifb[i,j]="="
4thenPRINT-LCS（b,X,i-1,j-1）
5printxi
6elseifb[i,j]="↑"
7thenPRINT-LCS（b,X,i-1,j）
8elsePRINT-LCS（b,X,i,j-1）
d）矩阵链乘法的算法：
参照课本上的矩阵链表得出矩阵相乘的最小算法。
MATRIX-CHAIN-ORDER（p）每个表项的复杂度是O（n），共有O（n^2）表项，则为O（n^3）
1n←length[p]-1
2fori←1ton
3dom[i,i]←0
4forl←2ton?
listhechainlength.
5dofori←1ton-l+1
6doj←i+l-1
7m[i,j]←∞
8fork←itoj-1
9doq←m[i,k]+m[k+1,j]+pi-1pkpj
10ifq11thenm[i,j]←q
12s[i,j]←k
13returnmands
PRINT-OPTIMAL-PARENS（s,i,j）
1ifi=j
2thenprint"Ai"
3elseprint"（"
4PRINT-OPTIMAL-PARENS（s,i,s[i,j]）
5PRINT-OPTIMAL-PARENS（s,s[i,j]+1,j）
6print"）"
e）备忘录算法：
1）程序结构采用自顶向上；2）保留了递归结构，开销较大；3）当所有的子问题都需要求解时，自底向上的方法效率较高，否则可以采用备忘录方法。
备忘录算法的代码可以参照课本207页。
f）最优二叉查找树：
1）一棵最优二叉查找树不一定是一棵整体高度最小的树，也不一定总是把有最大概率的关键字放在根部来构造一棵最优二叉查找树。
5、贪心法（最优子结构性质+贪心选择性质）。
考点：
学会证明最优子结构性质和贪心选择性质的问题。
a）活动选择问题：
注意课本上224页地贪婪法定理证明，这就是贪婪法的合理性证明。
RECURSIVE-ACTIVITY-SELECTOR（s,f,i,j）
1m←i+1
2whilemFindthefirstactivityinSij.
3dom←m+1
4ifm5thenreturn{am}∪RECURSIVE-ACTIVITY-SELECTOR（s,f,m,j）
6elsereturn
GREEDY-ACTIVITY-SELECTOR（s,f）
1n←length[s]
2A←{a1}
3i←12
4form←2ton
5doifsm≥fi
6thenA←A∪{am}
7i←m
8returnA
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）s（s的入度为0）
–存在汇结点（sink）t（t的出度为0）
–任意结点v∈V，有s~v~t
–容量函数C：
E→R+
称G为流网络。
流的定义：
流网络G，若函数p：
VXV→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、增广路径；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页的引理。
二、增广路径：
注意课本403页引理和引理。
三、流网络的割：
注意403页的几个引理。
四、最大流最小割定理：
几个相互等价的条件。
FORD-FULKERSON（G,s,t）
1foreachedge（u,v）∈E[G]
2dof[u,v]←0
3f[v,u]←0
4whilethereexistsapathpfromstotintheresidualnetworkGf
5docf（p）←min{cf（u,v）:
（u,v）isinp}
6foreachedge（u,v）inp
7dof[u,v]←f[u,v]+cf（p）
8f[v,u]←-f[u,v]
FORD-FULKERSON的复杂性：
FORD-FULKERSON过程的运行时间取决于如何决定第四行中的增广路径，选择不好，算法可能不会终止。
假设容量是整数
•1~3行O（|E|）
•4~8循环执行O（|f*|）
•找增广路O（|E|）
•O（|E||f*|）
FORD-FULKERSON算法有其缺点，可以参照课本406页。
4）Edmonds-Karp算法：
如果在第四行中用广度优先搜索来实现对增光路径p的计算。
即如果增光路径是残留网络中从s到t的最短路径（其中每条边为单位距离，或权），则能够改进FORD-FULKERSON算法的界；称FORD-FULKERSON方法的这种实现为Edmonds-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问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就成为NPC问题。
换言之，如果这个问题解决了，那么所有的NP问题也都能解决了。
若问题L满足
–L∈NP,and
–L′≤PLforeveryL′∈NP.
则问题L是NPC的，若L只满足条件2则称问题是NP-hard的。
注意：
如果任何NP完全问题可以在多项式时间内解决，则NP中所有问题都有一个多项式时间的算法。
1）多项式时间内的规约：
–若问题2可以被多项式时间求解，则问题1也可被多项式时间求解；
–若问题1不能被多项式时间求解，则问题2也不能多项式时间求解；
–problem1≤pproblem2表明：
问题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完全问题就是电路可满足性问题。
2）NP完全性与可归约性：
课本609页引理
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’={a1[j],a2[j],a3[j]}
Ej’={{a1[j],a2[j]},{a1[j],a3[j]},{a2[j],a3[j]}}
覆盖至少包含Vj’中的两个顶点,否则不能覆盖Ej’中的三角形
联络边:
沟通分量之间的关系
对于每个子句cj,设cj={xj,yj,zj},则
Ej’’={{a1[j],xj},{a2[j],yj},{a3[j],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}，定义费用函数为
c（i，j）={0，如果（i，j）属于E
{1，如果（i，j）不属于E
Notice：
因为G是无向图，它没有自环路，因而对所有的顶点v属于V，都有c（v，v）=1，于是就是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.
w1
w2
…
wq
x1
x2
…
xq
y1
y2
…
yq
注：
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）=010000010001=210+24+20
s（a2）=010000010100=210+24+22
s（a3）=000101000100=28+26+22
B=010101010101
子集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’}
满足
证明题的考点：
升级会员 