算法分析與設(shè)計(jì)2007第8講(同名22020)

《算法分析與設(shè)計(jì)2007第8講(同名22020)》由會(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,§2SAT問題屬于P類正面結(jié)果促進(jìn)較大，反面結(jié)果否定。矛盾的兩個(gè)方面，尋找規(guī)律。實(shí)例：U={u1,u2,…,un}，C={C1,…,Cm}，CiíUè{,…,}，

2、Ci

3、=2。

4、詢問：是否存在U的真值指派使C滿足。C1ù…ùCm=1。要考慮怎樣解：通過例子U={u1,u2,u3,u4,u5,u6}C={(u1,)，(u2,u5)，(,u5)，(,u4)，(,u6)，(,)}根據(jù)上述實(shí)例構(gòu)造有向圖：規(guī)則，(x,y)?u1u2u3u4u5u6112第八講存在一條從u1到的通路，u1賦值1肯定不行。引理：在2SAT項(xiàng)圖中，若存在uj?的通路，則uj≠1。即uj=0才可能使所有項(xiàng)滿足。就是只能賦值0。證明：uj?w1?w2?…?wk?，則有如下項(xiàng)：(,w1)，(,w2)，…，(,)。若uj=1，

5、則必有一個(gè)項(xiàng)不能滿足。說明一下。引理：若在2sat項(xiàng)圖中，存在路徑?uj，則uj10，必須uj?1才可能使所有項(xiàng)滿足。證明：設(shè)路徑為：?z1?z2?…?zl-1?zl?uj，則該路徑對(duì)應(yīng)如下項(xiàng)：(uj,z1),(,z2),(,z3),…,(,zl),(,uj)，矛盾。定理：若存在uj，在2sat項(xiàng)圖中，存在通路：?uj，uj?，則不存在真值指派，使所有項(xiàng)均滿足。定理：若對(duì)任意：uj，j=1,…,n，通路P(?uj)和P(uj?)不同時(shí)存在，則一定存在U的真值指派使所有項(xiàng)滿足。證明：只要設(shè)計(jì)出算法就可以了，就是當(dāng)下述

6、條件成立時(shí)：通路P(?uj)和P(uj?)不同時(shí)存在時(shí)，設(shè)計(jì)出給每個(gè)uj賦值的算法。(1)找通路，先賦值，對(duì)于uj,j=1,…,n112第八講若uj?,則uj=0；若?uj，則uj=1。(2)擴(kuò)展賦值，兩種情況。ui=1,x?{uj,}。存在邊ui?x，則x=1。x=uj，則uj?1；x=，則uj?0。ui=0，x?{uj,}。存在邊x?ui，則x=0。x=uj，則uj?0；x=，則uj?1。證明不會(huì)出現(xiàn)矛盾：112第八講(3)剩余變量賦值，怎么賦值？其余賦予相同的值(0或1)。實(shí)際上根本用不著第2步。112第八講

7、請(qǐng)證明正確性。自己完成?！?.2一類NPC問題在三角化圖上的解三角化圖的了解。(1)幾個(gè)概念，講這個(gè)內(nèi)容告訴大家很多知識(shí)，常識(shí)也很有用。G=(V,E)w(G):團(tuán)數(shù)，G的最大完全子圖定點(diǎn)個(gè)數(shù)，c(G):色數(shù)，G中定點(diǎn)著色所需最小色數(shù)，圖三著色是NPC，圖k著色是NPC，平面圖：(1)圖三著色是NPC。以后證明。(2)4112第八講著色未知，已經(jīng)用計(jì)算機(jī)證明出來了，大概現(xiàn)在研究這個(gè)問題的人很少。(3)5著色是多項(xiàng)式時(shí)間可解的，容易證明。平面圖。a(G)：G的獨(dú)立數(shù)，G的最大獨(dú)立集的頂點(diǎn)個(gè)數(shù)，k(G)：G的團(tuán)覆蓋數(shù)，覆

8、蓋G的所有頂點(diǎn)所需要的完全子圖最小個(gè)數(shù)。團(tuán)覆蓋問題。團(tuán)覆蓋也有很多應(yīng)用，在很多方面。結(jié)論：w(G)￡c(G)//w(G):團(tuán)數(shù)，G的最大完全子圖定點(diǎn)個(gè)數(shù)，//c(G):色數(shù)，G中定點(diǎn)著色所需最小色數(shù)，a(G)￡k(G)(2)什么是三角化圖：任意四邊形以上的多邊形中都有一條弦。首先舉個(gè)例子：說明什么是完美頂點(diǎn)刪除方案。我所見過的應(yīng)用，完美進(jìn)化樹，當(dāng)時(shí)不知怎么回事。單純頂點(diǎn)：與v臨接的點(diǎn)在圖中是完全子圖，任意u1,u2?Adj(v)，(u1,u2)?E，則v是單純頂點(diǎn)。完美頂點(diǎn)刪除方案：存在一個(gè)頂點(diǎn)序列v1,v2,…,

9、vn，使vk在G(vk+1,…,vn)中是單純頂點(diǎn)，則頂點(diǎn)序列稱為完美頂點(diǎn)刪除方案。112第八講k=1,2,…,n-1，G(vk+1,…,vn)稱為由vk+1,…,vn導(dǎo)出的子圖。三角化圖的定義：若圖G存在完美頂點(diǎn)刪除方案，則G是三角化圖。以下就用這個(gè)判斷。舉例子：1，5，2，3，4，6，7，8，9結(jié)論：(1)可以多項(xiàng)式時(shí)間判斷三角化圖。(2)在三角化圖上，團(tuán)問題，著色問題，獨(dú)立集問題，團(tuán)劃分問題都可多項(xiàng)式時(shí)間解決。5.2.2用字典續(xù)廣度優(yōu)先搜索判斷三角化圖Tarjan的算法,最有名的工作是判斷平面圖,例子說明：判

10、斷三角化圖很顯然是多項(xiàng)式時(shí)間可解的。112第八講adj(a)={b,e}adj(b)={a,c,d,e}adj(c)={b,d}adj(d)={b,c,e}adj(e)={a,b,d}開始任意選擇頂點(diǎn)aivabcde0LabelfffffNumber-----1Labelf{5}ff{5}Number5----2Labelf{5}{4}{4}{5,4}Num