资源描述：
《算法分析与设计2009第8讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、上次内容：(1)限制技术，局部替换技术，分支技术证明NPC。(2)划分三角形，多任务排工，区间排工，最小迟序排工，是NPC。(3)NPC问题子问题是NPC吗？是多项式时间可解的吗，具体问题看。(4)Sat,3Sat,3DM,par,vc,VI,CL,HC,X3C,MC,PIT,Scedule1,Schedule2,Schedule3,(5)SAT问题为NPC问题，SAT问题的子问题3SAT问题也是NPC问题。实例：布尔变量集合U={u1,u2,…,un}，其项的集合Ci={c1,c2,…,cm}，且每个项ci(1≤i≤m)
2、恰含有2个字母，即
3、ci
4、=2。询问：是否存在U的真值指派t，使项集合C满足。证明一个问题属于NPC类，需要构造一个已知NPC问题到该问题的多项式变换，但要想证明一个问题属于P类，则需要找到该问题的多项式时间求解算法。下面我们来考虑2SAT问题的复杂性。定理5.1：2SATÎP。证明：证明分两步。第一步根据2SAT实例构造表示变量和项之间关系的项图。第二步观察项图的性质，并在项图指引下设计解答2SAT问题的多项式算法。首先根据2SAT问题的任意实例构造有向图G=(V,E)。假定布尔变量集合U={u1,u2,…,un}，其项
5、的集合C={c1,c2,…,cm}，且ci={xi,yi}(1≤i≤m)直接用变量字母表示图的顶点。V={u1,…,un,,…,}E={(®yi),(®xi)
6、ci={xi,yi}ÎC,xi,yi,,ÎV,1≤i≤m}例子：U={x1,x2,x3,y1,y2,y3,z1,z2,z3}C={(,x2),(,x3),(,x1),(,y2),(,y3),(,y1),(,z2),(,z3),(,z1),(,y1),(,z1),(,y2),(,z2),(,y3),(,z3)，(,)}项图为：(,y1),(,z1),(,),(,z2)
7、,(,y2),(,x2)存在一条从u1到的通路，u1赋值1肯定不行。引理：在2SAT项图中，若存在uj®的通路，则t(uj)≠1。即t(uj)=0才可能使所有项满足。就是只能赋值0。证明：uj®w1®w2®…®wk®，则在C中必有如下项：(,w1)，(,w2)，…，(,)。若uj=1，则必有一个项不能满足。说明一下。引理：若在2sat项图中，存在路径®uj，则必须t(uj)¬1才可能使所有项满足。t(uj)≠0。证明：设路径为：®z1®z2®…®zl-1®zl®uj，则该路径对应如下项：(uj,z1),(,z2),(,z3
8、),…,(,zl),(,uj)，矛盾。在图G上可以观察到2SAT实例存在可满足真值指派的充分必要条件，即：2SAT问题的实例有可满足的真值指派，当且仅当其项图G=(V,E)中，顶点uj与(1≤j≤n)不在同一强连通分支内。我们分别用两个引理来表述必要性和充分性。什么叫强连同分支？引理5.1：若存在j,1£j£n，使顶点uj,在图G的同一个强连通分支中，则2SAT实例不存在可满足的真值指派。刚才的例子：U={x1,x2,x3,y1,y2,y3,z1,z2,z3}C={(x2),(,x3),(,x1),(,y2),(,y3),
9、(,y1),(,z2),(,z3),(,z1),(,y1),(,z1),(,y2),(,z2),(,y3),(,z3)，(,)}项图为：引理5.2：若任意顶点对uj,，1£j£n，均不在项图G的同一个强连同分支内，则必存在满足C的真值指派。证明：xÎ{uj,}，一个项图顶点为x，则uj赋值t(uj)后，也将x的赋值称为顶点x的赋值，记为t(x)。即若x=uj，则t(x)=t(uj)；若x=，则t(x)=t()，另外t(x)=Æ表示x尚未给出赋值。性质5.1：2SAT实例满足，当且仅当在2SAT项图中，对于每条有向边(x®y
10、)，x,y的赋值t(x),t(y)为F,F或F,T或T,T。相当于有一个项：(,y)，当然不能t(x)=T(1),t(y)=F(0)若一条边(x,y)两个端点的赋值t(x),t(y)为F,F或F,T或T,T，称边(x,y)满足。因此只需要给项图的每个顶点赋值，使所有边均满足，即可使2SAT所有项满足。性质5.2：设xÎ{uj,}，yÎ{uk,}。若存在x到，y到的通路，则不存在到y和到x的通路。注意：到y和到x的通路，同时存亡保证放心赋值：t(x)=F(0)，t()=T(1)没有问题。(1)根据有向通路为布尔变量赋值：假设
11、ui和不在同一个强连同分支中，1£i£n，根据有向通路首先为布尔变量赋值的方法如下。Assignation1(U,C,G)//U为布尔变量集，C为项集，G为由U和C得到的项图。1Fori=1tondo2若G存在由ui到的有向通路，则t(ui)=F。3若G存在由到ui的有向通路，则t(ui)=T。4End
