算法分析與設(shè)計2007第8講

《算法分析與設(shè)計2007第8講》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第八講上次內(nèi)容：(1)限制技術(shù)，局部替換技術(shù)，分支技術(shù)證明NPC。(2)劃分三角形，多任務(wù)排工，區(qū)間排工，最小遲序排工，是NPC。(3)NPC問題子問題是NPC嗎？是多項式時間可解的嗎，具體問題看。(4)Sat,3Sat,3DM,par,vc,VI,CL,HC,X3C,MC,PIT,Scedule1,Schedule2,Schedule3,§2SAT問題屬于P類正面結(jié)果促進(jìn)較大，反面結(jié)果否定。矛盾的兩個方面，尋找規(guī)律。實例：U={u1,u2,…,un}，C={C1,…,Cm}，CiíUè{,…,}，

2、Ci

3、=2。詢問：是否存在U的真值指派使C滿足

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

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

6、，對于uj,j=1,…,n10第八講若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。證明不會出現(xiàn)矛盾：10第八講(3)剩余變量賦值，怎么賦值？其余賦予相同的值(0或1)。實際上根本用不著第2步。10第八講請證明正確性。自己完成?！?.2一類NPC問題在三角化圖上的解三角化圖的了解。(1)幾個概念，講這個內(nèi)容告訴大家很多知識，常識也很有用。G=(V

7、,E)w(G):團(tuán)數(shù)，G的最大完全子圖定點個數(shù)，c(G):色數(shù)，G中定點著色所需最小色數(shù)，圖三著色是NPC，圖k著色是NPC，平面圖：(1)圖三著色是NPC。以后證明。(2)410第八講著色未知，已經(jīng)用計算機(jī)證明出來了，大概現(xiàn)在研究這個問題的人很少。(3)5著色是多項式時間可解的，容易證明。平面圖。a(G)：G的獨立數(shù)，G的最大獨立集的頂點個數(shù)，k(G)：G的團(tuán)覆蓋數(shù)，覆蓋G的所有頂點所需要的完全子圖最小個數(shù)。團(tuán)覆蓋問題。團(tuán)覆蓋也有很多應(yīng)用，在很多方面。結(jié)論：w(G)￡c(G)//w(G):團(tuán)數(shù)，G的最大完全子圖定點個數(shù)，//c(G):色數(shù)，G中定

8、點著色所需最小色數(shù)，a(G)￡k(G)(2)什么是三角化圖：任意四邊形以上的多邊形中都有一條弦。首先舉個例子：說明什么是完美頂點刪除方案。我所見過的應(yīng)用，完美進(jìn)化樹，當(dāng)時不知怎么回事。單純頂點：與v臨接的點在圖中是完全子圖，任意u1,u2?Adj(v)，(u1,u2)?E，則v是單純頂點。完美頂點刪除方案：存在一個頂點序列v1,v2,…,vn，使vk在G(vk+1,…,vn)中是單純頂點，則頂點序列稱為完美頂點刪除方案。10第八講k=1,2,…,n-1，G(vk+1,…,vn)稱為由vk+1,…,vn導(dǎo)出的子圖。三角化圖的定義：若圖G存在完美頂點刪

9、除方案，則G是三角化圖。以下就用這個判斷。舉例子：1，5，2，3，4，6，7，8，9結(jié)論：(1)可以多項式時間判斷三角化圖。(2)在三角化圖上，團(tuán)問題，著色問題，獨立集問題，團(tuán)劃分問題都可多項式時間解決。5.2.2用字典續(xù)廣度優(yōu)先搜索判斷三角化圖Tarjan的算法,最有名的工作是判斷平面圖,例子說明：判斷三角化圖很顯然是多項式時間可解的。10第八講adj(a)={b,e}adj(b)={a,c,d,e}adj(c)={b,d}adj(d)={b,c,e}adj(e)={a,b,d}開始任意選擇頂點aivabcde0LabelfffffNumber-

10、----1Labelf{5}ff{5}Number5----2Labelf{5}{4}{4}{5,4}Number54--