資源描述：
《算法分析解析與設(shè)計-2016-第9講.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、算法分析與設(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的分界人們想
2、干什么？畫出一個明顯的界限，應(yīng)該是不可能的。其實沒有什么界，需要時有，不需要時沒有。其實事情做不到的，事物的好和壞，沒法嚴(yán)格區(qū)分的。找到一個界限，將P和NPC分開，開始這樣想，想象力重要，量變和質(zhì)變。解一個實例應(yīng)該簡單，一類實例復(fù)雜點。研究者想這樣。一般來說找一個明顯的界限是不可能的。是否存在一個界，過了此界，就是NPC的，不過此界就是多項式的，這個界對任何一個問題大概是不會嚴(yán)格存在的。2Sat,3Sat2DM,3DM與前面講過的最小遲序排工問題不同?先行約束排工問題：前面講的排工，多任務(wù)排工，最小遲序排工，區(qū)間排工。
3、實例：描述實例需要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)
4、{ti?T
5、?(ti)=k,1?k?D-1}
6、?m，同時加工的任務(wù)數(shù)最多是m。(2)當(dāng)ti?tj，則?(ti)
7、問題變種，現(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)
8、m?3，m?4，m?5，m?6,m?7,m?100，半序關(guān)系任意；這些問題不知道是什么樣的。沒有研究清楚，沒有明確的結(jié)果，也不是沒有用。開始時好解，逐漸不知道好解不好解，最后肯定不好解。過度越來越難！??！從易到難的過度過程，看到一種趨勢。如圖：下面再從另一個角度研究問題，求解難度，正面攻擊以后再從反面攻擊。有些問題的子問題，說明其為NP-Hard也很有用。任何事物都有兩個方面，觀察了好的一面，再去觀察壞的一面。一個問題的兩個方面，總是在變化的。問題圖的3著色問題：實例：圖G=(V,E)詢問：是否存在3種顏色為G著色。是
9、否存在映射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)問題和著色問題的共同點和相同點
10、。下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。(1)該圖能否三著色(2)是否含有三個點的團(tuán)下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并
11、不好解。下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好解。錯了下面該講怎樣著色，圖的著色。先給一個點著色，然后給其相鄰點著色，不斷進(jìn)行，嘗試所有可能。D=4，常數(shù)，用上面的圖解釋怎樣著色。限制頂點度為常數(shù)的著色問題并不好
