資源描述：
《算法分析與設計2009第8講》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、上次內(nèi)容：(1)限制技術，局部替換技術，分支技術證明NPC。(2)劃分三角形，多任務排工，區(qū)間排工，最小遲序排工，是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。證明：證明分兩步。第一步根據(jù)2SAT實例構造表示變量和項之間關系的項圖。第二步觀察項圖的性質(zhì)，并在項圖指引下設計解答2SAT問題的多項式算法。首先根據(jù)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)不在同一強連通分支內(nèi)。我們分別用兩個引理來表述必要性和充分性。什么叫強連同分支？引理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的同一個強連同分支內(nèi)，則必存在滿足C的真值指派。證明：x?{uj,}，一個項圖頂點為x，則uj賦值t(uj)后，也將x的賦值稱為頂點x的賦值，記為t(x)。即若x=uj，則t(x)=t(uj)；若x=，則t(x)=t()，另外t(x)=?表示x尚未給出賦值。性質(zhì)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所有項滿足。性質(zhì)5.2：設x?{uj,}，y?{uk,}。若存在x到，y到的通路，則不存在到y(tǒng)和到x的通路。注意：到y(tǒng)和到x的通路，同時存亡保證放心賦值：t(x)=F(0)，t()=T(1)沒有問題。(1)根據(jù)有向通路為布爾變量賦值：假設
11、ui和不在同一個強連同分支中，1￡i￡n，根據(jù)有向通路首先為布爾變量賦值的方法如下。Assignation1(U,C,G)//U為布爾變量集，C為項集，G為由U和C得到的項圖。1Fori=1tondo2若G存在由ui到的有向通路，則t(ui)=F。3若G存在由到ui的有向通路，則t(ui)=T。4End
