算法分析與設(shè)計-2016-第9講

算法分析與設(shè)計第9講-2016山東大學(xué)計算機(jī)學(xué)院上次內(nèi)容：(1)2sat的求解算法，利用一種有向圖。叫項圖，觀察項圖找規(guī)律,設(shè)計算法。需要找規(guī)律，才能設(shè)計算法。(2)三角化圖中四(五)個問題的求解：三角化圖的判定，字典序廣度優(yōu)先搜索。有完美頂點刪除方案三角化圖。三角化圖上的團(tuán)問題，著色問題，講了這兩個問題。五個問題的計算方法：團(tuán)問題，著色問題，團(tuán)覆蓋問題，獨立集問題，頂點覆蓋問題，都有多項式算法。也有很多NPC問題在三角化圖上仍然是NPC的。這五個問題已經(jīng)不是判定問題了。判定問題§5.3子問題中P和NPC的分界人們想干什么？畫出一個明顯的界限，應(yīng)該是不可能的。其實沒有什么界，需要時有，不需要時沒有。其實事情做不到的，事物的好和壞，沒法嚴(yán)格區(qū)分的。找到一個界限，將P和NPC分開，開始這樣想，想象力重要，量變和質(zhì)變。解一個實例應(yīng)該簡單，一類實例復(fù)雜點。研究者想這樣。一般來說找一個明顯的界限是不可能的。是否存在一個界，過了此界，就是NPC的，不過此界就是多項式的，這個界對任何一個問題大概是不會嚴(yán)格存在的。2Sat,3Sat2DM,3DM與前面講過的最小遲序排工問題不同?先行約束排工問題：前面講的排工，多任務(wù)排工，最小遲序排工，區(qū)間排工。實例：描述實例需要4句話。(1)T={t1,t2,…,tn}，T中每個任務(wù)均可在單位時間內(nèi)完成，L(ti)=1(2)T上有半序關(guān)系?，表達(dá)先后順序。(3)處理機(jī)臺數(shù)m。(4)完成任務(wù)的最后期限D(zhuǎn)Z+，總的最后期限。詢問：是否存在排工表，：T{0,1,2,…,D-1}，滿足(1)|{tiT|(ti)=k,1kD-1}|m，同時加工的任務(wù)數(shù)最多是m。(2)當(dāng)ti

?tj，則(ti)<(tj)，排工順序滿足半序關(guān)系。說明問題界的情況，現(xiàn)在解到什么程度不知道，這是當(dāng)時的情況，不過可以說明要說明的主題。很多排工問題變種，現(xiàn)在排工問題仍然是算法研究的重要內(nèi)容。*先要說明半序關(guān)系怎樣表達(dá)，用有向圖表達(dá)。T={t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11}，用有向無環(huán)圖表示半序關(guān)系。

123411個任務(wù)4臺機(jī)器(1)當(dāng)m=1時，該問題是多項式可解的,為什么？(2)當(dāng)m=2時，也是多項式時間可解的，總是同時安排兩個任務(wù)，當(dāng)作業(yè)。作業(yè)題。(3)半序關(guān)系為無，肯定是多項式時間可解的。因為加工長度均為1。(4)半序關(guān)系為樹，問題是多項式時間可解的。自己試試，作業(yè)題。(5)半序關(guān)系任意，m任意，該問題是NPC的。(6)m3，m4，m5，m6,m7,m100，半序關(guān)系任意；這些問題不知道是什么樣的。沒有研究清楚，沒有明確的結(jié)果，也不是沒有用。開始時好解，逐漸不知道好解不好解，最后肯定不好解。過度越來越難?。?！從易到難的過度過程，看到一種趨勢。如圖：下面再從另一個角度研究問題，求解難度，正面攻擊以后再從反面攻擊。有些問題的子問題，說明其為NP-Hard也很有用。任何事物都有兩個方面，觀察了好的一面，再去觀察壞的一面。一個問題的兩個方面，總是在變化的。問題圖的3著色問題：實例：圖G=(V,E)詢問：是否存在3種顏色為G著色。是否存在映射f：V{1,2,3}，使得當(dāng)(u,v)E時，有f(u)f(v)。任意圖的著色問題是NPC的。任意圖的團(tuán)問題是NPC的，但任意圖是否存在3個點的團(tuán)的問題是多項式可解的。任意圖的三著色問題就是NPC的。限制頂點度數(shù)不超過常數(shù)D的團(tuán)問題是P問題，為什么？所以用O(nD+1)種可能性可以一一嘗試。例如D=4，D=3。三角化圖上，團(tuán)問題與著色問題都是多項式時間可解的，但從另一個方面限制就不一樣了。三角化圖上，3著色問題當(dāng)然是多項式可解的。

//已知的在三角化圖上都是多項式的。比較圖的團(tuán)問題和著色問題的共同點和相同點。下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。

(1)該圖能否三著色(2)是否含有三個點的團(tuán)下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。

下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。

下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。

錯了下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。

下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。

下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。

另一種著色方案定理5.8：在頂點度數(shù)不超過4的無向簡單圖上的3著色問題屬于NPC類。(在頂點度數(shù)不超過4的無向簡單圖上，團(tuán)問題屬于P類。)證明：需要知道一般圖的3著色是NPC問題。一般圖3著色頂點度不超過4的圖3著色。一種特殊的圖：8個點，13條邊。

實例：無向圖G=(V,E)，任意vV,d(v)4詢問：是否存在f:V{1,2,3}，使得任意(u,v)E，f(u)f(v)定理5.8：在頂點度數(shù)不超過4的無向簡單圖上，3著色問題屬于NPC類。(在頂點度數(shù)不超過4的無向簡單圖上，團(tuán)問題屬于P類。)證明：一般圖3著色頂點度不超過4的圖3著色。一種特殊的圖：8個點，13條邊。

定理5.8：在頂點度數(shù)不超過4的無向簡單圖上，3著色問題屬于NPC類。(在頂點度數(shù)不超過4的無向簡單圖上，團(tuán)問題屬于P類。)證明：一般圖3著色頂點度不超過4的圖3著色。一種特殊的圖：8個點，13條邊。

定理5.8：在頂點度數(shù)不超過4的無向簡單圖上，3著色問題屬于NPC類。(在頂點度數(shù)不超過4的無向簡單圖上，團(tuán)問題屬于P類。)證明：一般圖3著色頂點度不超過4的圖3著色。一種特殊的圖：8個點，13條邊。

定理5.8：在頂點度數(shù)不超過4的無向簡單圖上，3著色問題屬于NPC類。(在頂點度數(shù)不超過4的無向簡單圖上，團(tuán)問題屬于P類。)證明：一般圖3著色頂點度不超過4的圖3著色。一種特殊的圖：8個點，13條邊。

這個圖的特點：(1)可以用三種顏色著色，每個頂點的度不超過4。(2)頂點1，2，3，4，5，6的度數(shù)均為2(3)頂點1，2，3，4，5，6必須使用相同的顏色著色。才能三著色?。?！所以任意舉一個圖的例子，都可以變?yōu)橐粋€頂點度不超過4的圖的例子，原圖可以3著色新圖也可以3著色；新圖可以3著色，原圖也可以3著色。7*(6-2)+1個頂點123123所以頂點度不超過4的3著色是NPC的。一個點的度最大為n-1，替換為三角圖后，增加n-3個三角形的組合圖，增加的頂點數(shù)目7(n-3)+1，多項式時間可以完成。定理5.9：平面圖3著色是NPC的。證明：任意圖3著色平面圖3著色先看一種特殊圖：Y’XX’Y判定任意圖是否可以三著色，屬于NPC類。定理5.9：平面圖3著色是NPC的。證明：任意圖3著色平面圖3著色先看一種特殊圖：Y’XX’Y定理5.9：平面圖3著色是NPC的。證明：任意圖3著色平面圖3著色先看一種特殊圖：Y’XX’Y定理5.9：平面圖3著色是NPC的。證明：任意圖3著色平面圖3著色先看一種特殊圖：Y’XX’Y定理5.9：平面圖3著色是NPC的。證明：任意圖3著色平面圖3著色先看一種特殊圖：Y’XX’Y實例：平面圖G=(V,E)詢問：是否存在f:V{1,2,3}，使得任意(u,v)E，f(u)f(v)所以頂點度不超過4的3著色是NPC的。一個點的度最大為n-1，替換為三角圖后，增加n-3個三角形的組合圖，增加的頂點數(shù)目7(n-3)+1，多項式時間可以完成。定理5.9：平面圖3著色是NPC的。證明：任意圖3著色平面圖3著色先看一種特殊圖：Y’XX’Y所以頂點度不超過4的3著色是NPC的。一個點的度最大為n-1，替換為三角圖后，增加n-3個三角形的組合圖，增加的頂點數(shù)目7(n-3)+1，多項式時間可以完成。定理5.9：平面圖3著色是NPC的。證明：任意圖3著色平面圖3著色先看一種特殊圖：Y’XX’Y所以頂點度不超過4的3著色是NPC的。一個點的度最大為n-1，替換為三角圖后，增加n-3個三角形的組合圖，增加的頂點數(shù)目7(n-3)+1，多項式時間可以完成。定理5.9：平面圖3著色是NPC的。證明：任意圖3著色平面圖3著色先看一種特殊圖：Y’XX’Y八卦圖的特點：(1)13個點，24條邊，(2)是個平面圖，可以3著色(3)能3著色X,X’同顏色，Y,Y’同顏色。舉個例子說明怎樣變換

這個圖的特點：(1)13個點，24條邊，(2)是個平面圖，可以3著色(3)X,X’必須用相同顏色著色才能3著色，(4)Y,Y’必須用相同顏色著色才能3著色，舉個例子說明怎樣變換

這個圖的特點：(1)13個點，24條邊，(2)是個平面圖，可以3著色(3)X,X’必須用相同顏色著色才能3著色，(4)Y,Y’必須用相同顏色著色才能3著色，舉個例子說明怎樣變換

這個圖的特點：(1)13個點，24條邊，(2)是個平面圖，可以3著色(3)X,X’必須用相同顏色著色才能3著色，(4)Y,Y’必須用相同顏色著色才能3著色，舉個例子說明怎樣變換

這個圖的特點：(1)13個點，24條邊，(2)是個平面圖，可以3著色(3)X,X’必須用相同顏色著色才能3著色，(4)Y,Y’必須用相同顏色著色才能3著色，舉個例子說明怎樣變換

每條邊最多與|E|-1條邊相交，每個交點增加不超過13個點。交點數(shù)目是多項式個，則增加的點數(shù)目當(dāng)然是多項式個。所以多項式時間能完成八卦圖1235467891012345678910這個圖不是平面圖，在交叉處用前面的特殊圖代替，就可以了，代替完成就變成平面圖了。代替法也有講究，需要講。這樣代替后的是平面圖，且與原圖有相同的色數(shù)，解釋為什么。上述已經(jīng)證明平面圖3著色是NPC的。

第6章：擬多項式變換與圖靈規(guī)約這一章要干什么？(1)NPC類問題中的特殊現(xiàn)象，數(shù)值參量對NPC問題計算復(fù)雜性的影響。數(shù)大時難求，數(shù)小時就好求了。界定它們的復(fù)雜性，有這種現(xiàn)象，就要觀察它們的規(guī)律性，說明它們的存在性，刻畫它。有些NPC問題很特殊：進(jìn)一步理解時間復(fù)雜度。先需要講一個算法：(2)很多問題不是NP的，當(dāng)然也不是NPC的，但是這些問題也很難找到多項式算法，比NPC問題還要難，所以需要將NPC問題推廣。怎樣說明這些問題的求解復(fù)雜度。這些問題不比NPC問題容易。

*比如SAT問題的優(yōu)化形式，SAT實例：U,C詢問：是否存在U的真值指派，使C中項全部滿足。求真值指派使?jié)M足的項數(shù)最多，這個問題稱為Max-SAT。Max-SAT實例：U,C，搜索問題詢問：求解U的真值指派，使C中滿足的項數(shù)目達(dá)到最大。TSP判定問題：實例：城市集合C={C1,C2,…,Cm}，定義距離：d(Ci,Cj)Z+，BZ+。詢問：是否存在貨郎旅游，其長度不大于B。TSP優(yōu)化問題：搜索問題實例：城市集合C={C1,C2,…,Cm}，定義距離：d(Ci,Cj)Z+，詢問：求解城市排列C(1),C(2),…,C(m-1),C(m)，滿足最優(yōu)的條件d(C(1),C(2),…,C(m-1),C(m))=min{d(P[C1,…,Cm])|P[C1,…,Cm]為任意排列}

前i個元素中是否存在子集，其中元素價值之和為0A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF12345(i)若t(i-1,j)=T，則t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，則t(i,j)=T。A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF1TTFFFFFFFFFFFFs(a1)=12345(i)若t(i-1,j)=T，則t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，則t(i,j)=T。A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF1TTFFFFFFFFFFFFs(a1)=12TTFFFFFFFTTFFFs(a2)=9345(i)若t(i-1,j)=T，則t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，則t(i,j)=T。A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF1TTFFFFFFFFFFFFs(a1)=12TTFFFFFFFTTFFFs(a2)=93TTFFFTTFFTTFFFs(a3)=545(i)若t(i-1,j)=T，則t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，則t(i,j)=T。A={1,9,5,3,8}

ji0123456789101112130TFFFFFFFFFFFFF1TTFFFFFFFFFFFFs(a1)=12TTFFFFFFFTTFFFs(a2)=93TTFFFTTFFTTFFFs(a3)=54TTFTTTTFTTTFTTs(a4)=35(i)若t(i-1,j)=T，則t(i,j)=T；(ii)若t(i-1,j-s(ai))=T，則t(i,j)=T。A={1,9