CH8-算法设计与分析-第f讲

朱大铭教授山东大学计算机学院dmzhu,DesignandAnalysisofAlgorithm算法设计与分析,第八章近似算法设计技术,8.1组合技术Max-SAT问题的2近似性能比算法Max-k-SAT问题的1+1/k近似性能比算法1+1/(2k-1)近似性能比算法集合覆盖问题O(logn)近似性能比算法8.2线形规划技术顶点覆盖问题的2近似性能比算法集合覆盖问题的f近似性能比算法8.3原始对偶技术8.4局部搜索技术Max-3-SAT问题的4/3近似度局部搜索算法8.5随机近似算法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：UT,F，使得可满足项的数目最大。设项Ci=ui,1,ui,k，Ci可满足的含义是：ui,1ui,k=T，即Ci所含有的布尔变量字母至少有一个取真值。,设含有字母ui的项集合为CuiC，含有字母的项集合为CC。显然，若一个项既含有ui又含有，则无论ui赋T或F均能使该项满足，因此假设CuiC=。若|Cui|C|，则指派ui为T，可使Cui中的所有项全部满足；否则，指派ui为F，可使C中的所有项满足。因此总可给出ui恰当的赋值使CuiC中至少一半的项满足。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时，显然成立。假设nk-1时结论成立。n=k时，算法对u1的真值指派至少满足1/2*|Cu1C|个项。u1赋值后的项集合C1中不含有u1及其反变量。根据归纳假设，Max-SAT()对u2un的赋值使可满足的项不小于：1/2*|C1|。所有算法满足：MaxSAT(U,C)1/2*|Cu1C|+1/2*|C1|=n/2从而算法的近似性能比不超过2。,二、Max-K-SAT问题,如果对Max-SAT问题的输入子句加以限制，使得每个子句都至少含有k个布尔变量字母，则得到的子问题为Max-K-SAT。当K1时，所有的Max-K-SAT问题都是NPC的。下面的算法是Johnson于1974年设计的。,JohnsonsMax-k-SAT(U,C)贪心算法（一）,设SU=，True=，Left=C，Lit=U，如果Lit中的任一变量都不出现在Left的任意子句中，则结束。设y为Lit中的某变量字母，满足在Left中包含y的子句最多。YT为该包含Y的子句的集合。SU=SUYT，Left=Left-YT，True=Truey，Lit=Lit-y,。转第2步。注意，上述算法中的y可以为某ui，也可为ui的反变量，并且默认反变量的反变量为变量本身。,算法Max-k-SAT(U,C)的近似度不大于1+1/k,证明：每次将变量y添加到True集合中，肯定满足|Cy|C|。称|C|中的项为被y伤害的项。算法结束时，如果某个项未能满足，则该项受伤害的次数为其含有的变量个数。从而，总的受伤害的次数至少为：k*|Left|。所以有|SU|k*|Left|。则有：|C|=|SU|+|Left|(1+1/k)|SU|。Atightexamplefork=3：S=x1,x2,x3,x4,x5,x6,x7,x8,x9选择三个反变量加入True，只能使3个项满足。为了使受伤害次数较多的项尽可能满足，考虑给项加上权。,Johnsons改进算法Max-k-SAT-W(U,C)（二）,对C中的每个项c赋权W(c)=2-|c|。设SU=，True=，Left=C，Lit=U，如果Lit中的任一变量都不出现在Left的任意子句中，则结束。设y为Lit中的某变量符号，YT为该包含y的子句的集合，YF为包含y的反变量的子句的集合。如果YT中子句的权之和不小于YF中子句的权之和，则：True=Truey，SU=SUYT，Left=Left-YT。YF中所有子句的权加倍。否则，True=True，SU=SUYF，Left=Left-YT。YT中所有子句的权加倍。6.Lit=Lit-y,，转第3步。,算法Max-k-SAT-W(U,C)的近似度不大于2K/(2k-1),证明：开始时，Left中所有项的权重不超过|C|/2k。每次循环，集合Left中裁掉的项的权重总和不小于留在Left中被伤害的项增加的权重总和。所以Left中项的权重总和不会增加。当算法结束时，Left中所有项的权重不超过|C|/2k。算法结束时，每个不能被满足的项的受伤害次数为它含有的变量字母个数，从而，每个不能被满足的项的权值为1。即|Left|C|/2k。|SU|C|(1-1/2k)。得证！AtightExamplefork=3如果第一次选择加入集合True，则最后只能有7个项满足。,三、集合覆盖问题,实例：基本元素集合E=e1,e2,en,E的子集的集合S=s1,s2,sm，siE，1im。目标：求S的一个标号子集I1,2,m，满足：，使|I|最小化。下面给出求解集合覆盖问题的贪心算法，该算法虽然简单，其性能却是最好的。,集合覆盖贪心算法Set-Cover(E,S),I=，Uncov=E，Seti=si，1im。如果Uncov=，则结束。选择j，使得|Setj|最大。I=Ij，Uncov=Uncov-Setj，Seti=Seti-Setj，1im。5.转第2步。,先讨论算法的性质：,定义如下符号：（第i次循环开始时)Setij：可选择的子集数组。1jm。Uncovi：未被覆盖的元素构成的集合。Setji：第i次循环选择的集合。假设算法共执行t-1次循环，则Uncovt=；且对于it，Uncovi。则算法可用如下序列R表示：R=Set11m,Uncov1,j1,Sett-11m,Uncovt-1,jt-1,Sett1m,Uncovt.显然每次选择ji后，置集合Setji为空，所以任何集合均不可能被重复选择。,I(R)=j1,j2,jt-1表示算法一个运行序列所选择的集合的下标的集合。对于正整数集合M,如果存在算法的一个运行序列R，使得M=I(R)，则称M为可选择的。根据上面的定义，很显然有：设S1S是E的一个子覆盖，M1=i:siS1，则M1是可选择的，当且仅当存在算法的一个运行序列R，使得M1=I(R)。,关键引理：设M1是任意可选择的正整数集合，S0为E的任意子覆盖，则有：证明：设M0=i:siS0,h=max|si|:iM0，根据h的取值进行归纳证明。h=0时，M0=，Uncov=，则M1=，结论成立。假设h=k-1时结论成立。下面证明h=k时亦成立。设M1=j1,jt-1，其中r为满足Setjrk的第一个ji的下标。设Cov=Setj1Setj2Setjr-1，则Cov=Uncov1-Uncovr，且r-1|Cov|/k（1）对于任意的iM0，|Setri|0。目标：求顶点子集VV,满足：对任意的(i,j)E,i,jV。最小化。形式化描述为整数规划的形式：约束条件：xi+xj1，(i,j)Exi0,1，iV,松弛为线性规划：将每个变量的取值范围松弛为0,即可。对应的线性规划为：约束条件：xi+xj1，(i,j)Exi0，iV（8.9）设ZLP(G,W)是线性规划(8.9)式的解，OPT(G,W)是顶点覆盖实例的最优解解值，则显然有：ZLP(G,W)OPT(G,W)因为整数规划的可行解必然是线性规划的可行解！,顶点覆盖算法Round(X,W,LP),求解线性规划(8.9)得到最优解x*=(,)；取所有1/2的顶点得到集合C。1in。算法得到的顶点集合是图G=(V,E)的顶点覆盖。证明：若存在(i,j)E，使得i,j均不在C中。则必有1/2,1/2，所以+0，1im。目标：求S的一个标号子集I1,2,m，满足：，使最小化。整数规划：约束条件为xj0,1，1jm将变量的取值范围松弛为0,)得到对应的线性规划。,设OPT(E,S,W)是整数规划的解值，ZLP(E,S,W)是线性规划的解值，则ZLP(E,S,W)OPT(E,S,W)。设E中任意元素最多在S中出现f次，即：C(ei)=|j|eiSj|，f=maxC(ei)，1in。下面给出近似性能比不超过f的线性规划算法。,集合覆盖算法SC-Round(X,W,LP),求解线性规划得到最优解x*=(,)；取所有1/f的集合得集合覆盖I。1im。算法得到的子集集合I是集合覆盖实例的可行解。证明：若存在eiE，使得ei不在I的任何集合中。则对每个含有ei的Sj，均有1/f,从而这与关于ei的条件矛盾或x*是线性规划的可行解矛盾。,算法SC-Round()的绝对近似性能比RSCRf,证明：且对于任意的jI，有*f1。所以,Max-3SAT问题的局部搜索算法,相关说明：Max-3SAT实例为U=u1,u2,un，C=C1,C2,Cm，每个项均含有不少于3个布尔变量字母。欲求U的真值指派，使C中可满足的项最多。其中一个项Ci=ui,1,ui,2,ui,3被赋值f满足指f(ui,1)f(ui,2)f(ui,3)=T。我们总假设某变量及其反变量不同时出现在同一个项中。,局部搜索算法Max-3SAT(U,C),所有布尔变量随机赋值，得满足的项集合C(a)。如果存在变量ui，改变其赋值能使得满足的项数增加，则改变此变量的赋值。直到找不到这样的变量为止。算法的复杂性由读者尝试分析，肯定是多项式时间的。下面分析算法的性能。设算法得到一个可行解a(U)使满足的项集合为C(a)，我们证明C(a)中的项至少为所有项数目的3/4。,设a(U)为算法Max-3SAT()求得的一个U的真值指派。将任意布尔变量ui的赋值取反，由不满足变为满足的项集合为Ci,F，则。证明：对于每个未被满足的项x,y,z,必然出现且仅出现在Cx,F、Cy,F、Cz,F。因此，每个C-C(a)中的项在C1,F,Cn,F中必出现3次。得证！,设a(U)为算法Max-3SAT()求得的一个U的真值指派。将布尔变量ui的赋值取反，由满足变为不满足的项集合为Ci,T，则。证明：对于每个C(a)中已满足的项,最多在C1,T,Cn,T中出现1次。得证！,将ui的赋值取反，由满足变为不满足的项集合为Ci,T，由不满足变为满足的项集合为Ci,F，则|Ci,T|Ci,F|。证明：a(U)是局部最优解。|C(a)|3/4*|C|。证明：Atightcase当a(u1)=a(u2)=a(u3)=F时，算法得到一个局部最优解，C1不能被a(U)满足，C2,C3,C4均被满足。,Max-SAT问题随机算法,Rand-Max-SAT(U,C)：对每一变量，以1/2的概率赋真或假。对任意MaxSAT实例U,C，设算法得到的真值指派使满足的项数目为ZMaxSAT，则EZMaxSAT1/2*|C|。证明：设Zi为随机变量，若Ci满足则Zi=1，否则Zi=0，1im。则ZMaxSAT=Z1+Z2+Zm。设Ci含有k个布尔变量字母，则Ci不满足的概率为2-k。EZi=1-2-k1/2。所以EZMaxSAT=EZ1+EZ2+EZm1/2*m=1/2*|C|,如果每个项均含有k个变量，则算法可使平均(1-2-k)|C|个项满足。因此如果项集合C中每个项包含至少2个字母，则前面的算法的平均近似性能比即为4/3。下面再给出另外一个线性规划算法，当项集合C含有一个字母的项时，有更好的性能。对于任意MaxSAT问题实例，两个算法之一总能达到4/3的平均近似性能比。所以针对一个实例分别运行两个算法，从中选择较好的解即可保证总有平均近似性能比不大于4/3。,Max-SAT可描述为如下的整数规划：对每个项设置参数z；对每个变量设置参数y；Cj+表示出现在Cj中的正变量的下标集合；Cj-表示出现在Cj中的负变量的下标集合。（8.59）约束条件为：(1)(2)yi,zj0,1，1in，1jm松弛z，y的取值区间为0,1,得到相应的线性规划。,Round-MaxSAT(U,C)求解(8.59)的线性规划，得到和。yi以概率取1；以1-概率取0。k=1-(1-1/k)k设Cj是含有k个字母的项，随机舍入后，Cj被满足的概率不小于k*。证明：设Cj=u