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

算法分析與設(shè)計(jì),第10講-2016 山東大學(xué)計(jì)算機(jī)學(xué)院/軟件學(xué)院,上次內(nèi)容： (1)先行約束排工，限制很強(qiáng)時(shí)是多項(xiàng)式可解的， 沒(méi)有限制是NP-Complete。NPC和多項(xiàng)式可解有分界線嗎？ 找了一個(gè)問(wèn)題來(lái)說(shuō)明，分界線無(wú)為有時(shí)有為無(wú)。 (2)著色問(wèn)題，限制頂點(diǎn)度不超過(guò)4的圖3著色問(wèn)題是NPC， 限制平面圖的3著色問(wèn)題是NPC。 說(shuō)明有些問(wèn)題的子問(wèn)題仍然為NPC，有意思，有意義。 (3)劃分問(wèn)題的擬多項(xiàng)式算法。劃分問(wèn)題擬多項(xiàng)式時(shí)間算法。,nlog2B,需要重新認(rèn)識(shí)時(shí)間復(fù)雜度。,例如：B = 2n*n*n,Length(I)=n4 O(nB)=O(n2n*n*n),(1)一個(gè)問(wèn)題實(shí)例的編碼不是完全相同的， 因此輸入長(zhǎng)度和最大數(shù)值會(huì)跟據(jù)編碼不同有所不同。 不同人編不同的程序。 (2)有的問(wèn)題根本不含有數(shù)值參量，這樣MAX(I)=0。 定義6.1：擬多項(xiàng)式算法：判定問(wèn)題，存在解答算法A， 算法A的時(shí)間復(fù)雜度為：T=P(Length(I), Max(I)，I為的任意實(shí)例， 則稱算法A為求解問(wèn)題的擬多項(xiàng)式算法。 看問(wèn)題：?jiǎn)栴}怎樣在計(jì)算機(jī)存儲(chǔ)?首先明確輸入長(zhǎng)度為n， 則最大數(shù)值可能是2p(n)。,在考慮算法時(shí)間復(fù)雜度時(shí)，往往忽略怎樣編碼的，其實(shí)編碼也有學(xué)問(wèn)。,問(wèn)題：另外的NPC問(wèn)題是否也有這么好的算法？,(1)SAT，該問(wèn)題中根本沒(méi)有MAX(I)這一項(xiàng)。 沒(méi)有最大數(shù)值，Max(I)=0 (2)TSP，該問(wèn)題中邊長(zhǎng)，或界值K是最大數(shù)值Max(I)項(xiàng)。 Max(I)=K (3)劃分問(wèn)題，元素價(jià)值或B是Max(I)項(xiàng)。O(nB) (4)團(tuán)問(wèn)題，最大數(shù)值，J|V|。自然受到限制。 考慮(1)，Max(I)=0，這個(gè)問(wèn)題是NPC的， 可以認(rèn)為，最大數(shù)值本身受到輸入長(zhǎng)度的限制。(4)也這樣。 Max(I)P(Length(I)，P()是多項(xiàng)式函數(shù)。 考慮問(wèn)題(2)(3)，TSP問(wèn)題中， 邊長(zhǎng)根本不受輸入長(zhǎng)度的約束，每條邊長(zhǎng)可能很大， 問(wèn)題(3)的元素價(jià)值也不受到輸入長(zhǎng)度約束。,怎樣區(qū)分(1)(4)/(2)(3),什么叫不受約束：如果長(zhǎng)度為x，則數(shù)值大小為2p(x)。 受約束的含義：存在多項(xiàng)式函數(shù)P()，使Max(I)P(Length(I)。 最大數(shù)值不會(huì)增大到超過(guò)輸入長(zhǎng)度的某個(gè)多項(xiàng)式函數(shù)的程度。 將Max(I)不受Length(I)約束的問(wèn)題單獨(dú)分為一類(lèi)，給個(gè)命名。 定義6.2：對(duì)于判定問(wèn)題，若不存在多項(xiàng)式函數(shù)P()， 使對(duì)問(wèn)題的所有實(shí)例I有：Max(I)P(Length(I)， 則稱為數(shù)問(wèn)題。 最大數(shù)值不受約束。 就是最大數(shù)值可能很大的問(wèn)題是數(shù)問(wèn)題。不受輸入長(zhǎng)度約束。,SAT和團(tuán)問(wèn)題不是數(shù)問(wèn)題， 劃分問(wèn)題和貨郎問(wèn)題是數(shù)問(wèn)題。,證明：設(shè)不是數(shù)問(wèn)題，反證：若存在擬多項(xiàng)式算法A， 解答問(wèn)題實(shí)例I的時(shí)間復(fù)雜度為： T(I)= q(Length(I), Max(I)q(Length(I), p(Length(I) =q1(Length(I)。 其實(shí)算法A是多項(xiàng)式時(shí)間算法。 即：若存在解答的擬多項(xiàng)式算法， 則該算法是多項(xiàng)式算法(解答)。 則P=NP，矛盾。 問(wèn)題，多項(xiàng)式函數(shù)P()， D()表示該問(wèn)題的所有實(shí)例組成的集合。 對(duì)于多項(xiàng)式函數(shù)P()，定義一個(gè)新的實(shí)例集合： D(P) = I|ID() ，Max(I)P(Length(I)， 由D(P)中實(shí)例表達(dá)的問(wèn)題就是多項(xiàng)式可解的嗎。,BP(n),命題6.1：若NPC類(lèi)判定問(wèn)題不是數(shù)問(wèn)題，PNP， 則該問(wèn)題不能被擬多項(xiàng)式算法解答。,解釋什么問(wèn)題不是數(shù)問(wèn)題。數(shù)值不會(huì)很大的問(wèn)題。 Max(I)q(Length(I)。不存在這樣的q()。,每個(gè)D(P)的實(shí)例都是D()的實(shí)例。所以P是的子問(wèn)題。 注意多項(xiàng)式函數(shù)給定。 例如劃分問(wèn)題中，每個(gè)元素長(zhǎng)度S(a)n2，n是元素個(gè)數(shù)。 P(n)=n3，則P是多項(xiàng)式可解的。 再次強(qiáng)調(diào)問(wèn)題是實(shí)例的集合！,定義6.3：判定問(wèn)題，存在多項(xiàng)式函數(shù)P， 使P是NPC的，則稱是強(qiáng)NPC的。 (1)非數(shù)NPC問(wèn)題一定是強(qiáng)NPC問(wèn)題， 對(duì)于非數(shù)問(wèn)題，NPC與強(qiáng)NPC是等價(jià)的。 (2)主要討論數(shù)問(wèn)題是否為強(qiáng)NPC問(wèn)題,P中的每個(gè)實(shí)例I，都滿足：Max(I)P(Length(I),命題6.2：若問(wèn)題是強(qiáng)NPC的，PNP， 則一定不能被擬多項(xiàng)式算法解答。 證明：若有擬多項(xiàng)式算法A， 則證明A是解答p的多項(xiàng)式算法。 TA(I)=q(Max(I),Length(I) 因存在P()，P是NPC的。 那算法A解答P的實(shí)例I1，Max(I1)P(Length(I1) TA(I1)=q(Max(I1),Length(I1) q(P(Length(I1),Length(I1)=q1(Length(I1) 強(qiáng)NPC問(wèn)題不能有擬多項(xiàng)式算法， 否則NPC問(wèn)題就可以多項(xiàng)式解答了。 受限子問(wèn)題是NPC的，能被多項(xiàng)式時(shí)間算法解答， 則任意NP問(wèn)題都能被多項(xiàng)式時(shí)間算法解答。,I1D(p),TA(I)=q(Max(I),Length(I)：A是擬多項(xiàng)式時(shí)間算法。 TA(I)=q(Length(I)：A是多項(xiàng)式時(shí)間算法。,6.2強(qiáng)NPC類(lèi)與擬多項(xiàng)式變換 先證明貨郎問(wèn)題是強(qiáng)NPC的。 限制貨郎問(wèn)題的邊長(zhǎng)不是很大，也是NPC。 結(jié)論：限制邊長(zhǎng)為1或2的TSP問(wèn)題是NPC的。 HCTSP TSP實(shí)例給定完全圖，每條邊都有長(zhǎng)度。 HC的圖不一定是完全圖，邊也沒(méi)有長(zhǎng)度。,TSP: 實(shí)例：城市集合c1,cn，城市距離d(i,j)1,2,正整數(shù)K。 詢問(wèn)：是否存在貨郎旅游，其長(zhǎng)度不超過(guò)K？,證明：HC實(shí)例為，,將該實(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)TSP實(shí)例存在長(zhǎng)度為K的旅游， 若TSP實(shí)例存在長(zhǎng)度為K的旅游， 則HC實(shí)例存在Hamilton回路。,每條邊的長(zhǎng)度不超過(guò)2，可以認(rèn)為Max(I)=n。 滿足Max(I)Length(I)，滿足這種限制的TSP仍然是NPC的。 所以TSP問(wèn)題是強(qiáng)NPC的。 對(duì)于一個(gè)NPC問(wèn)題： 如果你能說(shuō)明其數(shù)值大小受限的子問(wèn)題是NPC的， 則就說(shuō)明這個(gè)問(wèn)題是強(qiáng)NPC的。 受限子問(wèn)題即受多項(xiàng)式函數(shù)P()約束的子問(wèn)題。,很多人分家時(shí)，數(shù)值不必很大就很難,例子：A=11,12,13,14,15,15,11,12,17, B=40,m=3,這也是一個(gè)很典型的問(wèn)題，很多人用它來(lái)證明其他問(wèn)題是NPC或強(qiáng)NPC,1,2,3,有很多東西，省略去了，4劃分是強(qiáng)NPC， 3劃分也是強(qiáng)NPC。 說(shuō)明：書(shū)上有很復(fù)雜的符號(hào)，不需要害怕。 很多內(nèi)容，理解含義，也應(yīng)該比較簡(jiǎn)單。 下面先定義什么是擬多項(xiàng)式變換： 定義6.4：先說(shuō)明想干什么？,變換的時(shí)間復(fù)雜度也不需要是輸入長(zhǎng)度的多項(xiàng)式函數(shù)了！ 對(duì)所有實(shí)例，和對(duì)受P()限制的實(shí)例的變換， 是多項(xiàng)式時(shí)間就可以！ 時(shí)間復(fù)雜度不同。,多項(xiàng)式變換,1=；2= 變換f：,(1)IL1，f(I)L2， (2)1(I)=12(f(I)=1，充分必要的。 IY(1)f(I)Y(2)。不關(guān)心回答No的實(shí)例。 實(shí)際前面NTM定義中就只關(guān)心回答Yes的實(shí)例。 (3)f變換可以在p(|I|=n)時(shí)間內(nèi)計(jì)算完成。,p q,企圖定義一種變換，當(dāng)Max(I)P(length(I)時(shí)，這個(gè)變換是多項(xiàng)式變換。,(1)判定問(wèn)題1和2，實(shí)例集合分別為：D1，D2， (2)回答yes的實(shí)例集合為：Y1和Y2 (3)兩個(gè)問(wèn)題的實(shí)例編碼后分別有輸入長(zhǎng)度和最大數(shù)值： Length(I)，Max(I)，LengthI，MaxI。 (4)存在一個(gè)變換f：D1D2，滿足： (a)對(duì)任意實(shí)例ID1，計(jì)算f(I)的時(shí)間復(fù)雜度 是Length(I)和Max(I)的多項(xiàng)式函數(shù)。 T(f(I)=P(Max(I),Length(I)。 (b)IY1當(dāng)且僅當(dāng)f(I)Y2 (c)存在多項(xiàng)式函數(shù)p1()使對(duì)ID1有 LengthI p1(Lengthf(I)， 這個(gè)限制很有用，I的長(zhǎng)度不能很大。 仔細(xì)研究的話，估計(jì)這個(gè)條件可以去掉，這個(gè)條件怪。 一般越變?cè)介L(zhǎng)，不會(huì)變短。推導(dǎo)的一步需要這個(gè)條件。,為了保證2的最大數(shù)值受到輸入長(zhǎng)度約束,q1(LengthI)Lengthf(I)P(MaxI,LengthI),Lengthf(I)p2(LengthI, MaxI)， 這個(gè)由前面的條件(a)就能得到。 (d)存在兩個(gè)變量的多項(xiàng)式函數(shù)q1,使 Maxf(I)q1(MaxI,LengthI) 則f稱為1到2的擬多項(xiàng)式變換。 變換與數(shù)值和長(zhǎng)度都有關(guān)。 說(shuō)明：如果數(shù)值參量受到輸入長(zhǎng)度約束， 就是多項(xiàng)式時(shí)間變換。 條件(a)(b)是擬多項(xiàng)式變換的基本要求， 變換計(jì)算時(shí)間復(fù)雜度要求更寬一些。 (c)需要這個(gè)條件，保證2的實(shí)例中最大數(shù)值受到輸入長(zhǎng)度約束。 (d)要求Max(*)不能增大到超過(guò)Max(*)和Length(*)的界定范圍。 擬多項(xiàng)式變換P, (1)Yes實(shí)例的變換 (2)受約束實(shí)例的變換 pq,(a)對(duì)任意實(shí)例ID1，計(jì)算f(I)的時(shí)間復(fù)雜度 是Length(I)和Max(I)的多項(xiàng)式函數(shù)。 T(f(I)=P(Max(I),Length(I)。 (b)IY(1)f(I)Y(2) (c)存在多項(xiàng)式函數(shù)p1()使對(duì)ID1有 LengthIp1(Lengthf(I)，,Lengthf(I)p(LengthI, MaxI)， 這個(gè)由前面的條件(a)就能得到。 (d)存在兩個(gè)變量的多項(xiàng)式函數(shù)q1,使 Maxf(I)q1(MaxI,LengthI) 則f稱為1到2的擬多項(xiàng)式變換。 變換與數(shù)值和長(zhǎng)度都有關(guān)。 說(shuō)明：如果數(shù)值參量受到輸入長(zhǎng)度約束， 就是多項(xiàng)式時(shí)間變換。 條件(a)(b)是擬多項(xiàng)式變換的基本要求， 變換計(jì)算時(shí)間復(fù)雜度要求更寬一些。 (c)需要這個(gè)條件，保證2的實(shí)例中最大數(shù)值受到輸入長(zhǎng)度約束。 (d)要求Max(*)不能增大到超過(guò)Max(*)和Length(*)的界定范圍。 擬多項(xiàng)式變換P, (1)Yes實(shí)例的變換 (2)受約束實(shí)例的變換 pq,Maxf(I)q1(MaxI,LengthI) q1(q(LengthI),LengthI) q1(q(p1(Lengthf(I),p1(Lengthf(I) P1(Length(f(I),T(f(I)=P(MaxI,LengthI) P(q(LengthI),LengthI) =P1(LengthI),變換的時(shí)間復(fù)雜性,中的實(shí)例，其數(shù)值參量受約束,區(qū)間排工問(wèn)題： 實(shí)例：有限任務(wù)集合，T=t1,t2,tn，只有一臺(tái)機(jī)器。 r(tk)：最早起始時(shí)間 d(tk)：最晚結(jié)束時(shí)間 L(tk)：加工長(zhǎng)度 詢問(wèn)：是否存在排工表：(tk)，k=1,2,n，使 d(tk)-L(tk)(tk)r(tk)，每個(gè)任務(wù)都能按時(shí)完成。 任意ti, tj，ij，|(ti)-(tj)|maxL(ti),L(tj)： 兩個(gè)任務(wù)不能同時(shí)進(jìn)行！ 定理6.3：區(qū)間排工是強(qiáng)NPC。 證明：三劃分P區(qū)間排工。,前面講過(guò)區(qū)間排工問(wèn)題,相差只有1,就是說(shuō)區(qū)間排工中的數(shù)值r(),d(),L()都不必很大， 問(wèn)題就很難解。 子林同構(gòu): 實(shí)例：圖G和H，G為樹(shù)，H為林。 詢問(wèn)：圖G是否包含一個(gè)子圖與H同構(gòu)。 限制G和H都是樹(shù)，則該問(wèn)題是多項(xiàng)式時(shí)間可解的。 限制G為樹(shù)，H為林，則該問(wèn)題是強(qiáng)NPC。 首先判定兩個(gè)圖是否完全同構(gòu)是否多項(xiàng)式時(shí)間可解是未知的。 子林同構(gòu)問(wèn)題根本就沒(méi)有數(shù)值參量，所謂強(qiáng)NPC與NPC等價(jià)的。 這個(gè)例子的意義在于說(shuō)明可以用證明強(qiáng)NPC的方法證明NPC。,不斷問(wèn)自己為什么？人們會(huì)猜想?yún)^(qū)間排工也會(huì)象劃分問(wèn)題那樣求解，其實(shí)不行。,定理6.4：子林同構(gòu)問(wèn)題是強(qiáng)NPC。 證明：三劃分?jǐn)M多項(xiàng)式變換到子林同構(gòu)。 A=a1,a2,a3m，S(ai), BZ+ 構(gòu)造G和H如下：,B+1個(gè)點(diǎn)。G,針對(duì)每個(gè)ai,構(gòu)造一根長(zhǎng)度為S(ai)的繩子。,首先說(shuō)明若三劃分回答yes， 則顯然可以將對(duì)應(yīng)的H的線圖接起來(lái)對(duì)到G上去。 另外若H中的線圖接到星圖上形成完全G的形狀， 則接到每一條線上去的線段的總長(zhǎng)均為B， 所以原來(lái)的三劃分問(wèn)題一定可以三劃分。,B,(3)變換的時(shí)間復(fù)雜度與B有關(guān)，(mB) 變換出來(lái)的樹(shù)的點(diǎn)的個(gè)數(shù)與B有關(guān)。 主要說(shuō)明： 限制B不大時(shí)，即為輸入長(zhǎng)度的多項(xiàng)式函數(shù)時(shí)， 三劃分問(wèn)題是NPC的， 變換本身是輸入長(zhǎng)度和最大數(shù)值的多項(xiàng)式函數(shù)， 所以是多項(xiàng)式變換 所以子林同構(gòu)是NPC的。 子林同構(gòu)中根本沒(méi)有數(shù)值參量，當(dāng)然是強(qiáng)NPC的。,6.3：復(fù)雜性類(lèi)之間的關(guān)系 很多問(wèn)題不是NP的，所以不是NPC的，但是比NPC問(wèn)題更難， 這樣的問(wèn)題怎樣說(shuō)明難度。 Hamilton問(wèn)題補(bǔ)問(wèn)題： 實(shí)例：無(wú)向簡(jiǎn)單圖G=(V,E) 詢問(wèn)：是否不存在圖G的hamilton回路？ 這個(gè)問(wèn)題不能確定是多項(xiàng)式時(shí)間可驗(yàn)證的，不能確定是NP的， 所以不能說(shuō)是NPC的。這個(gè)問(wèn)題能夠正確回答， 則hamilton回路問(wèn)題也能正確回答。,D1=G|G有Hamilton回路 任給G1和頂點(diǎn)排列，如果驗(yàn)證頂點(diǎn)排列是Hamilton回路，則G1D1,D2=G|G沒(méi)有Hamilton回路 任給G2和頂點(diǎn)排列，如果驗(yàn)證頂點(diǎn)排列不是Hamilton回路，則不能說(shuō)G2D2,假設(shè)貨郎優(yōu)化問(wèn)題有一個(gè)多項(xiàng)式算法A(G,d)。 貨郎判定問(wèn)題實(shí)例為G,d,K 則解答貨郎判定問(wèn)題的算法如下： 1