資源描述：
《算法分析與設(shè)計(jì)2009第a講》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、上次內(nèi)容：(1)先行約束排工，限制很強(qiáng)時(shí)是多項(xiàng)式可解的，沒有限制是NP-Complete。(2)著色問題，限制頂點(diǎn)度不超過4的圖3著色問題是NPC，限制平面圖的3著色問題是NPC。(3)擬多項(xiàng)式變換與NPC類，劃分問題的擬多項(xiàng)式算法。劃分問題擬多項(xiàng)式時(shí)間算法。一個(gè)問題實(shí)例中有兩個(gè)因素影響算法時(shí)間復(fù)雜度：劃分問題。輸入長度：Length(I)=
2、A
3、log2
4、A
5、+
6、A
7、log2()最大數(shù)值：問題的實(shí)例中碰到的最大數(shù)值。Max(I)=B=算法時(shí)間復(fù)雜性：O(nB)=P(Length(I),Max(I)
8、)說明：可以設(shè)計(jì)算法與兩個(gè)參數(shù)有關(guān)系。l一個(gè)問題的編碼不是完全相同的，因此輸入長度和最大數(shù)值會(huì)根據(jù)編碼不同有所不同。不同人編不同的程序。l有的問題根本不含有數(shù)值參量，這樣MAX(I)=0。定義6.1：擬多項(xiàng)式算法：判定問題p，存在解答算法A，算法A的時(shí)間復(fù)雜度為：T=P(Length(I),Max(I))，I為任意實(shí)例，則稱算法A為求解問題p的擬多項(xiàng)式算法。看問題：問題怎樣在計(jì)算機(jī)存儲(chǔ)?首先明確輸入長度為n，則最大數(shù)值可能是2n。(1)SAT，該問題中根本沒有MAX(I)這一項(xiàng)。沒有最大數(shù)值，Max
9、(I)=0(2)TSP，該問題中邊長或K是最大數(shù)值MAX(I)項(xiàng)。(3)劃分問題，元素重量或B是Max(I)項(xiàng)。O(nB)(4)團(tuán)問題，最大數(shù)值，J￡
10、V
11、。自然受到限制。考慮(1)，Max(I)=0，這個(gè)問題是NPC的，可以認(rèn)為，最大數(shù)值本身受到輸入長度的限制。Max(I)￡P(guān)(Length(I))，P(·)是多項(xiàng)式函數(shù)。考慮問題(2)(3)，TSP問題中，邊長根本不受輸入長度的約束，每條邊長可能很大，問題3的元素重量也不受到輸入長度約束。受約束的含義：存在多項(xiàng)式函數(shù)P(·)，使Max(I)￡P(guān)(
12、Length(I))。將Max(I)不受Length(I)約束的問題單獨(dú)分為一類，給個(gè)名份。定義6.2：對(duì)于判定問題p，若不存在多項(xiàng)式函數(shù)P()，使對(duì)所有實(shí)例I有：Max(I)￡P(guān)(Length(I))，則稱p為數(shù)問題。最大數(shù)值不受約束。就是最大數(shù)值可能很大的問題是數(shù)問題。不受輸入長度約束。命題6.1：若判定問題不是數(shù)問題，P1NP，則該問題不能被擬多項(xiàng)式算法解答。解釋什么問題不是數(shù)問題。證明：設(shè)p不是數(shù)問題，T=q(Length(I),Max(I))￡q(length(I),p(length(I)
13、))=q1(length(I))。若存在解答p的擬多項(xiàng)式算法，則有多項(xiàng)式算法解答p，則P=NP，矛盾。問題p，多項(xiàng)式函數(shù)P()，D(p)表示該問題的所有實(shí)例組成的集合。對(duì)于多項(xiàng)式函數(shù)P(·)，定義一個(gè)新的實(shí)例集合：D(pP)={I
14、I?Dp,Max(I)￡P(guān)(Length(I))}，由D(pP)中實(shí)例表達(dá)的問題就是多項(xiàng)式可解的嗎。注意多項(xiàng)式函數(shù)給定。例如劃分問題中，每個(gè)元素長度S(a)￡n2，n是元素個(gè)數(shù)。P(n)=n2，則pP是多項(xiàng)式可解得。再次強(qiáng)調(diào)問題是實(shí)例的集合！定義6.3：判定問題p，存在多
15、項(xiàng)式函數(shù)P，使pP是NPC的，則稱p是強(qiáng)NPC的。(1)非數(shù)NPC問題一定是強(qiáng)NPC問題(2)主要討論數(shù)問題是否為強(qiáng)NPC問題命題6.2：若問題p是強(qiáng)NPC的，P1NP，則p一定不能被擬多項(xiàng)式算法解答。強(qiáng)NPC問題不能有擬多項(xiàng)式算法，否則NPC問題就可以多項(xiàng)式解答了。受限子問題是NPC的，能被多項(xiàng)式時(shí)間算法解答，則任意NP問題都能被多項(xiàng)式時(shí)間算法解答。§6.2證明強(qiáng)NPC與擬多項(xiàng)式變換先證明貨郎問題是強(qiáng)NPC的。限制貨郎問題的邊長不是很大，也是NPC。結(jié)論：限制邊長為1或2的TSP問題是NPC的。H
16、CμTSPHC實(shí)例為：?將該實(shí)例變?yōu)樨浝蓡栴}實(shí)例如下：d(a,b)=d(a,c)=d(a,d)=d(a,e)=d(b,c)=d(c,d)=d(c,e)=d(d,e)=1，d(b,d)=d(b,e)=2常數(shù)K=5顯然，若HC實(shí)例存在hamilton回路，則相應(yīng)TSP實(shí)例存在不超過K的旅游，若TSP實(shí)例存在不超過K的旅游，則HC實(shí)例存在hamilton回路。每條邊的長度不超過2，可以認(rèn)為Max(I)=2。滿足下式否？Max(I)￡Length(I)，滿足這種限制的TSP仍然是NPC的。所以TSP問題是強(qiáng)
17、NPC的。對(duì)于一個(gè)NPC問題，如果你能說明其受限子問題是NPC的，則就說明這個(gè)問題是強(qiáng)NPC的。先講一個(gè)問題，3劃分問題實(shí)例：講清楚，但不證明。(1)集合A，含有3m個(gè)元素，A={a1,a2,…,a3m}，(2)S(ai)?Z+，(3)存在正整數(shù)B?Z+，滿足：B/4
