資源描述：
《算法分析與設(shè)計(jì)2009第9講》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、上次內(nèi)容：(1)2sat的求解算法，利用一種有向圖。叫項(xiàng)圖，分析項(xiàng)圖找規(guī)律。(2)三角化圖中四個(gè)問題的求解：三角化圖的判定，字典序廣度優(yōu)先搜索。有完美頂點(diǎn)刪除方案就是三角化圖。l三角化圖的團(tuán)問題，著色問題，講了這兩個(gè)問題。l四個(gè)問題的計(jì)算方法：團(tuán)問題，著色問題，團(tuán)覆蓋問題，獨(dú)立集問題。§5.3子問題中P和NPC的分界人們想干什么？畫出一個(gè)明顯的界限，應(yīng)該是不可能的。找到一個(gè)界限，將P和NPC分開，開始這樣想，想象力重要，量變和質(zhì)變。解一個(gè)實(shí)例應(yīng)該簡(jiǎn)單，一類實(shí)例復(fù)雜點(diǎn)。研究者想這樣。一般來(lái)說(shuō)找一個(gè)明顯的界限是不可能的。是否存在一個(gè)界，過(guò)了此界，就是NPC的，不過(guò)此界就是多項(xiàng)式的，這個(gè)界對(duì)任何一個(gè)
2、問題大概是不會(huì)嚴(yán)格存在的。2sat,3sat先行約束排工問題：前面講的排工，多任務(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+，總的最后期限。與前面的最小遲續(xù)排工不同。詢問：是否存在排工表，s：T?{0,1,2,…,D-1}，滿足(1)
3、{ti?T
4、s(ti)=k,1￡k￡D-1}
5、￡m，同時(shí)加工的任務(wù)數(shù)最多是m。(2)當(dāng)ti?tj，則s(ti)6、道，這是當(dāng)時(shí)的情況，不過(guò)可以說(shuō)明問題。很多排工問題變種，現(xiàn)在排工問題仍然是算法研究的重要內(nèi)容。排工協(xié)會(huì)，專門研究排工。*先要說(shuō)明半序關(guān)系怎樣表達(dá)，用有向圖表達(dá)。T={t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11}，用有向無(wú)環(huán)圖表示半序關(guān)系。(1)當(dāng)m=1時(shí)，該問題是多項(xiàng)式可解的,為什么？(2)當(dāng)m=2時(shí)，也是多項(xiàng)式時(shí)間可解的，總是同時(shí)安排兩個(gè)任務(wù)，當(dāng)作作業(yè)研究問題時(shí)要看清楚難在什么地方。作業(yè)題。(3)半序關(guān)系為無(wú)，肯定是多項(xiàng)式時(shí)間可解的。因?yàn)榧庸らL(zhǎng)度均為1。(4)半序關(guān)系為樹，問題是多項(xiàng)式時(shí)間可解的。自己試試。作業(yè)題(5)半序關(guān)系任意，m任意，該問題是NPC的。(6)m
7、￡3，m￡4，m￡5，m￡6,m￡7,m￡100，半序關(guān)系任意；這些問題不知道是什么樣的。沒有人研究過(guò)，沒有明顯結(jié)果，也不是沒有用。開始時(shí)好解，逐漸不知道好解不好解，最后肯定不好解。過(guò)度越來(lái)越難！??！下面再?gòu)牧硪粋€(gè)角度研究問題，求解難度，正面進(jìn)攻以后再進(jìn)行反面進(jìn)攻。圖的3著色問題：實(shí)例：圖G=(V,E)詢問：圖G是否可以用3種顏色著色。是否存在映射f：V?{1,2,3}，使得當(dāng)(u,v)?E時(shí)，有f(u)1f(v)。l任意圖的3著色問題是NPC的。//已知的l限制頂點(diǎn)度數(shù)不超過(guò)常數(shù)D的團(tuán)問題是P問題，為什么？所以用O(nD+1)種可能性可以一一嘗試。三角化圖上，團(tuán)問題與著色問題都是多項(xiàng)式時(shí)間的
8、，但從另一個(gè)方面限制就不一樣了。三角化圖上，3著色問題當(dāng)然是多項(xiàng)式可解的。3下面該講怎樣著色，圖的著色。先給一個(gè)點(diǎn)著色，然后給其相鄰點(diǎn)著色，不斷進(jìn)行，嘗試所有可能。21465D=3，常數(shù)，用上面的圖解釋怎樣著色。限制頂點(diǎn)度為常數(shù)的著色問題并不好解。定理5.8：對(duì)頂點(diǎn)度數(shù)不超過(guò)4的圖，3著色問題屬于NPC類。證明：一般圖3著色μ頂點(diǎn)度不超過(guò)4的圖3著色。一種特殊的圖：3(a)2(a)1(a)這個(gè)圖的特點(diǎn)：(1)可以用三種顏色著色，(2)頂點(diǎn)1，2，3，4度數(shù)均為26(3)頂點(diǎn)1，2，3，4肯定使用相同的顏色著色。才能三著色?。?！所以任意舉一個(gè)圖的例子，都可以變?yōu)橐粋€(gè)頂點(diǎn)度不超過(guò)4的圖的例子，若原
9、圖可以3著色，新圖也可以3著色，新圖可以3著色，原圖也可以3著色。5所以頂點(diǎn)度不超過(guò)4的3著色是NPC的。定理5.9：平面圖3著色是NPC的。證明：任意圖3著色μ平面圖3著色先看一種特殊圖：這個(gè)圖的特點(diǎn)：(1)13個(gè)點(diǎn)，24條邊，(2)是個(gè)平面圖，可以3著色(3)X,X’必須用相同顏色著色才能3著色，(4)Y,Y’必須用相同顏色著色才能3著色，舉個(gè)例子說(shuō)明怎樣變換這個(gè)圖不是平面圖，在交叉處用前面的特殊圖代替，就可以了。代替法也有講究，需要講。這樣代替后的是平面圖，且與原圖有相同的色數(shù)，解釋為什么。上述已經(jīng)證明平面圖3著色是NPC的。第6章：擬多項(xiàng)式變換與圖靈規(guī)約這一章的背景：(1)NPC類問題
10、中的特殊現(xiàn)象，數(shù)值參量對(duì)NPC問題計(jì)算復(fù)雜性的影響。數(shù)大時(shí)難求，數(shù)小時(shí)就好求了。有些NPC問題很特殊：進(jìn)一步理解時(shí)間復(fù)雜度。先需要講一個(gè)算法：(2)很多問題不是NP的，當(dāng)然也不是NPC的，但是這些問題也很難找到多項(xiàng)式算法。怎樣說(shuō)明這些問題的求解復(fù)雜度。這些問題不比NPC問題容易。*比如SAT問題的優(yōu)化形式，求真值指派使?jié)M足的項(xiàng)數(shù)最多。這個(gè)問題稱為Max-Sat。TSP判定問題：實(shí)例：城市集合C={
