算法分析与设计-朱大鸣-CH8-算法设计与分析-第f讲.ppt

文档介绍：朱大铭教授
山东大学计算机学院
******@sdu.
Design and Analysis of Algorithm算法设计与分析
第八章近似算法设计技术
组合技术
Max-SAT问题的2近似性能比算法
Max-k-SAT问题的
1+1/k近似性能比算法
1+1/(2k-1)近似性能比算法
集合覆盖问题O(logn)近似性能比算法
线形规划技术
顶点覆盖问题的2近似性能比算法
集合覆盖问题的f近似性能比算法
原始对偶技术
局部搜索技术
Max-3-SAT问题的4/3近似度局部搜索算法
随机近似算法
Max-SAT问题的4/3近似度随机算法
第一讲组合技术
Max-SAT问题的2近似性能比算法
Max-k-SAT问题的
1+1/k近似性能比算法
1+1/(2k-1)近似性能比算法
集合覆盖问题O(logn)近似性能比算法
一、Max-SAT问题
实例:布尔变量集合U={u1,u2,…,un},项集合 C={C1,C2,…,Cm }, 。其中, 。
询问:计算U的真值指派f:U{T,F},使得可满足项的数目最大。
设项Ci={u[i,1], …, u[i,k]} ,Ci可满足的含义是:u[i,1]…u[i,k]=T ,即Ci所含有的布尔变量字母至少有一个取真值。
设含有字母ui的项集合为C[ui]C,含有字母的项集合为C[ ]C。
显然,若一个项既含有ui又含有,则无论ui赋T或F均能使该项满足,因此假设C[ui]  C[ ]=。
若|C[ui]||C[ ]|,则指派ui为T,可使C[ui] 中的所有项全部满足;否则,指派ui为F,可使C[ ]中的所有项满足。因此总可给出ui恰当的赋值使C[ui]  C[ ]中至少一半的项满足。
ui赋值后,无论其它变量如何赋值,已经满足的项仍然能保证满足;不能满足的项只能依靠其它变量的赋值才能满足。
合取范式最大可满足贪心算法Max-SAT(U,C)
对任一变量
如果含有其本身的项不少于含有其反变量的项
该变量赋值为T。
将其反变量从所有项中删除。
将所有已满足的项从项集合中删除。
如果含有其本身的项少于含有其反变量的项
该变量赋值为F。
将该变量本身从所有项中删除。
将所有已满足的项从项集合中删除。
直到所有变量都被赋值
算法Max-SAT()的近似性能比不超过2。
证明:设
MaxSAT(U,C)表示算法求得的真值指派能满足的项数。
OPT(U,C)表示U的真值指派最多能满足的项数。
显然OPT(U,C)n。我们对布尔变量数目n进行归纳,以证明
MaxSAT(U,C) n/2。
n=1时,显然成立。
假设nk-1时结论成立。
n=k时,算法对u1的真值指派至少满足1/2*|C[u1]C[ ]|个项。 u1赋值后的项集合C1中不含有u1及其反变量。根据归纳假设,Max-SAT()对u2un的赋值使可满足的项不小于:
1/2*|C1|。所有算法满足:
MaxSAT(U,C) 1/2*|C[u1]C[ ]| + 1/2*|C1|=n/2
从而算法的近似性能比不超过2。
二、Max-K-SAT问题
如果对Max-SAT问题的输入子句加以限制,使得每个子句都至少含有k个布尔变量字母,则得到的子问题为Max-K-SAT。
当K1时,所有的Max-K-SAT问题都是NPC的。
下面的算法是Johnson于1974年设计的。
Johnson’s Max-k-SAT(U,C)贪心算法(一)
设SU=,True=,Left=C,Lit=U ,
如果Lit中的任一变量都不出现在Left的任意子句中,则结束。
设y为Lit中的某变量字母,满足在Left中包含y的子句最多。YT为该包含Y的子句的集合。
SU=SUYT,Left=Left-YT, True=True{y},
Lit=Lit-{y, }。
转第2步。
注意,上述算法中的y可以为某ui,也可为ui的反变量,并且默认反变量的反变量为变量本身。
算法Max-k-SAT(U,C)的近似度不大于1+1/k
证明:
每次将变量y添加到True集合中,肯定满足|C[y]||C[ ]|。
称|C[ ]|中的项为被y伤害的项。
算法结束时,如果某个项未能满足,则该项受伤害的次数为其含有的变量个数。从而,总的受伤害的次数至少为:k*|Left|。
所以有|SU| k*|Left|。则有:|C|= |SU|+|Left|(1+1/k)|SU|。
A tight example for k=3:
S={{x1,x2,x3},{ ,x4,x5},{ ,x6,x7},{ ,x8,x9}}
选择三个反变量加入True,只能