資源描述：
《算法分析與設(shè)計(jì)2009第8講》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、上次內(nèi)容：(1)限制技術(shù)，局部替換技術(shù)，分支技術(shù)證明NPC。(2)劃分三角形，多任務(wù)排工，區(qū)間排工，最小遲序排工，是NPC。(3)NPC問題子問題是NPC嗎？是多項(xiàng)式時(shí)間可解的嗎，具體問題看。(4)Sat,3Sat,3DM,par,vc,VI,CL,HC,X3C,MC,PIT,Scedule1,Schedule2,Schedule3,(5)SAT問題為NPC問題，SAT問題的子問題3SAT問題也是NPC問題。實(shí)例：布爾變量集合U={u1,u2,…,un}，其項(xiàng)的集合Ci={c1,c2,…,cm}，且每個(gè)項(xiàng)ci(1≤i≤m)
2、恰含有2個(gè)字母，即
3、ci
4、=2。詢問：是否存在U的真值指派t，使項(xiàng)集合C滿足。證明一個(gè)問題屬于NPC類，需要構(gòu)造一個(gè)已知NPC問題到該問題的多項(xiàng)式變換，但要想證明一個(gè)問題屬于P類，則需要找到該問題的多項(xiàng)式時(shí)間求解算法。下面我們來考慮2SAT問題的復(fù)雜性。定理5.1：2SAT?P。證明：證明分兩步。第一步根據(jù)2SAT實(shí)例構(gòu)造表示變量和項(xiàng)之間關(guān)系的項(xiàng)圖。第二步觀察項(xiàng)圖的性質(zhì)，并在項(xiàng)圖指引下設(shè)計(jì)解答2SAT問題的多項(xiàng)式算法。首先根據(jù)2SAT問題的任意實(shí)例構(gòu)造有向圖G=(V,E)。假定布爾變量集合U={u1,u2,…,un}，其項(xiàng)
5、的集合C={c1,c2,…,cm}，且ci={xi,yi}(1≤i≤m)直接用變量字母表示圖的頂點(diǎn)。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)，(,)}項(xiàng)圖為：(,y1),(,z1),(,),(,z2)
7、,(,y2),(,x2)存在一條從u1到的通路，u1賦值1肯定不行。引理：在2SAT項(xiàng)圖中，若存在uj?的通路，則t(uj)≠1。即t(uj)=0才可能使所有項(xiàng)滿足。就是只能賦值0。證明：uj?w1?w2?…?wk?，則在C中必有如下項(xiàng)：(,w1)，(,w2)，…，(,)。若uj=1，則必有一個(gè)項(xiàng)不能滿足。說明一下。引理：若在2sat項(xiàng)圖中，存在路徑?uj，則必須t(uj)?1才可能使所有項(xiàng)滿足。t(uj)≠0。證明：設(shè)路徑為：?z1?z2?…?zl-1?zl?uj，則該路徑對(duì)應(yīng)如下項(xiàng)：(uj,z1),(,z2),(,z3
8、),…,(,zl),(,uj)，矛盾。在圖G上可以觀察到2SAT實(shí)例存在可滿足真值指派的充分必要條件，即：2SAT問題的實(shí)例有可滿足的真值指派，當(dāng)且僅當(dāng)其項(xiàng)圖G=(V,E)中，頂點(diǎn)uj與(1≤j≤n)不在同一強(qiáng)連通分支內(nèi)。我們分別用兩個(gè)引理來表述必要性和充分性。什么叫強(qiáng)連同分支？引理5.1：若存在j,1￡j￡n，使頂點(diǎn)uj,在圖G的同一個(gè)強(qiáng)連通分支中，則2SAT實(shí)例不存在可滿足的真值指派。剛才的例子：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)，(,)}項(xiàng)圖為：引理5.2：若任意頂點(diǎn)對(duì)uj,，1￡j￡n，均不在項(xiàng)圖G的同一個(gè)強(qiáng)連同分支內(nèi)，則必存在滿足C的真值指派。證明：x?{uj,}，一個(gè)項(xiàng)圖頂點(diǎn)為x，則uj賦值t(uj)后，也將x的賦值稱為頂點(diǎn)x的賦值，記為t(x)。即若x=uj，則t(x)=t(uj)；若x=，則t(x)=t()，另外t(x)=?表示x尚未給出賦值。性質(zhì)5.1：2SAT實(shí)例滿足，當(dāng)且僅當(dāng)在2SAT項(xiàng)圖中，對(duì)于每條有向邊(x?y
10、)，x,y的賦值t(x),t(y)為F,F或F,T或T,T。相當(dāng)于有一個(gè)項(xiàng)：(,y)，當(dāng)然不能t(x)=T(1),t(y)=F(0)若一條邊(x,y)兩個(gè)端點(diǎn)的賦值t(x),t(y)為F,F或F,T或T,T，稱邊(x,y)滿足。因此只需要給項(xiàng)圖的每個(gè)頂點(diǎn)賦值，使所有邊均滿足，即可使2SAT所有項(xiàng)滿足。性質(zhì)5.2：設(shè)x?{uj,}，y?{uk,}。若存在x到，y到的通路，則不存在到y(tǒng)和到x的通路。注意：到y(tǒng)和到x的通路，同時(shí)存亡保證放心賦值：t(x)=F(0)，t()=T(1)沒有問題。(1)根據(jù)有向通路為布爾變量賦值：假設(shè)
11、ui和不在同一個(gè)強(qiáng)連同分支中，1￡i￡n，根據(jù)有向通路首先為布爾變量賦值的方法如下。Assignation1(U,C,G)//U為布爾變量集，C為項(xiàng)集，G為由U和C得到的項(xiàng)圖。1Fori=1tondo2若G存在由ui到的有向通路，則t(ui)=F。3若G存在由到ui的有向通路，則t(ui)=T。4End
