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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

*比如SAT問題的優(yōu)化形式，SAT實(shí)例：U,C詢問：是否存在U的真值指派，使C中項(xiàng)全部滿足。求真值指派使?jié)M足的項(xiàng)數(shù)最多，這個(gè)問題稱為Max-SAT。Max-SAT實(shí)例：U,C，搜索問題詢問：求解U的真值指派，使C中滿足的項(xiàng)數(shù)目達(dá)到最大。TSP判定問題：實(shí)例：城市集合C={C1,C2,…,Cm}，定義距離：d(Ci,Cj)Z+，BZ+。詢問：是否存在貨郎旅游，其長(zhǎng)度不大于B。TSP優(yōu)化問題：搜索問題實(shí)例：城市集合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個(gè)元素中是否存在子集，其中元素價(jià)值之和為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