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