5thenreturn{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+4x2x310,1xj3,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),1in,其中Vi={ui,ūi},Ei={{ui,ūi}}
任意覆盖必至少包含ui或ūi中的一个,否则不能覆盖边{ui或ūi}.
满足性检验分量:
Sj=(Vj’,Ej’),1jm,
其中
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=(V1V2...Vn)(V1’V2’...Vm’)
E=E1E2...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’中的两个顶点.
如下得到赋值
uiV’t(ui)=T
ūiV’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,aA,s(a)Z+.
问:
是否存在A’A,使得
显然均分是NP类问题。
下面将3DM变换到均分问题
设W,X,Y,MWXY是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位,每段对应一个WXY中的元素.Wf(i),xg(i),yh(i)所代表的段的最右位为1,其它为0.
w1
w2
…
wq
x1
x2
…
xq
y1
y2
…
yq
注:
plog(k+1),2pk+1,k2p1,
当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:
1ik}满足
当且仅当M’={mi:
aiA’}是M的匹配
A的最后两个元素b1,b2
考虑包含b1的子集A’,必有
因此A’-{b1}的元素对应的三元组构成M的匹配
反之,若子集M’构成M的匹配,则
A’={b1}{ai:
miM’}
满足
证明题的考点: