33算法經(jīng)典22題TSPNPC背包排工團(tuán)等

1、一、設(shè)L為n元數(shù)組，其中的數(shù)已按增序排列，另給定數(shù)值 x,試采 用二分搜索技術(shù)設(shè)計(jì)算法，查找數(shù)值是否在 L中。要求若x在L中, 則輸出j,使L(j)=x ;其x不在L中，則輸出0。并證明，在最壞情 況下，對(duì)所有n元數(shù)組L(n>1)二分搜索算法將數(shù)值x與L中元素 比較次數(shù)為10g2 n 1。解：1、 11, r n2、if(1 r) j 0轉(zhuǎn) 64、 if (x 1 ( j)轉(zhuǎn) 65、if (x 1 (j)則 1 j 1,否則 r j 1,轉(zhuǎn) 26、輸出j ,結(jié)束比較次數(shù)：由于是2分搜索，每次比較或者成功，或者將搜索范圍縮小一半。因此最多比較次數(shù)為 2的對(duì)數(shù)，又當(dāng)n 1時(shí)，至少比較 1次，

2、所以比較次數(shù)不超過10g2n 1。二、滿足三角不等式的TSP問題是否是NPC?為什么？解：證明思路，將哈密頓回路HC問題多項(xiàng)式變換到 TSP問題:HC TSP,且變換到TSP問題的實(shí)例是滿足三角不等式的。因?yàn)镠C NPC ,故滿足三角不等式的TSP NPC。多項(xiàng)式變換：HC TSP設(shè)HC的實(shí)例為G ”及V1V2,Vm ,據(jù)此構(gòu)造TS實(shí)例G (V,E),V V,(G必為完全圖)，兩個(gè)頂點(diǎn)之間的距離定義為1 i, j E di, j2 i,j E,并設(shè)TSP旅游界值為B m。易知這個(gè)變換是多項(xiàng)式的。若HC存在一條哈密頓回路，則這條回路在 G上的長(zhǎng)度必為B,而B m是最短旅游的界值，故這條回路是滿足

3、實(shí)例的一個(gè) TSP旅游。若G存在一個(gè)滿足B的TSP旅游，則該旅游必經(jīng)過長(zhǎng)度為1的邊, 而這些邊均在G上，因此這個(gè)TSP旅游在G上是一條HC回路。這樣就將HC TSP ,而HC NPC。變換到的TSP實(shí)例的邊長(zhǎng)為1或2,可知該實(shí)例滿足三角不等式，這就證明了滿足三角不等式的 TSP問題是NPC問題。三、給定城市集合C Ci.Cn,任兩城市距離 d(i,j),d(i,j) d(i,k) d(k,j),求最小貨郎旅游。試證明滿足三角不等式 的貨郎優(yōu)化問題為NP-hard。求滿足三角不等式的TSP的近似算法， 并設(shè)計(jì)出能解答該問題的多項(xiàng)式時(shí)間近似算法A,其近似性能比為RA |0證明：即滿足三角不等式的T

4、SP問題。證明思路，將哈密頓回路HC問題多項(xiàng)式變換到TSP問 題:HC TSP且變換到TSP問題的實(shí)例是滿足三角不等式的(見第 1 題)。因?yàn)镠C NPC ,故滿足三角不等式的TSP問題是NPC問題。設(shè)存在TSP優(yōu)化問題求解算法A,設(shè)計(jì)TSP判定問題的算法如下:對(duì)于給定TSP判定問題的實(shí)例：G，d，k,調(diào)用A(G，d),求得城市* *d(C i ,C i1) k排列：C1，C 2,若，則回答yes,否則回答no。若A為多項(xiàng)式算法，則上述算法能夠在多項(xiàng)式時(shí)間內(nèi)解答，故TSP判定問題可以圖靈歸約到 TSP優(yōu)化問題，而已知 TSP判定問題是NPC的，所以TSP優(yōu)化問題是NPH的。算法A：對(duì)G調(diào)用最小

5、支撐樹(有權(quán)圖權(quán)值之和最小的連通子圖) 算法, 得到樹T(V，Et)設(shè)T的奇數(shù)頂點(diǎn)為V1% 在G中求點(diǎn)集VlV2,的最小對(duì)集Ep e1©, E,將EP加入T中，形成歐拉圖 在工中求歐拉回路V (1)V (2)，V (2m 2)V抄近路得到TSP：VVV (m)V證明Ra 2：因?yàn)門SP是回路，最小生成樹是樹，所以 d(T) OpT(l)又對(duì)于所有最小對(duì)集的兩條邊，d(Vi，vi 1)d(vi 2,vi 3)小于這四點(diǎn)相1連的最小TSP旅游距離2 ,133d(T1) d(T) -OPT(I) -OPT (I ) MM (I ) d(T1) - OPT (I)所以22,2三、假設(shè)一臺(tái)處理

6、機(jī)可連續(xù)加工任務(wù)。 但在每個(gè)時(shí)刻，只允許加工一 個(gè)任務(wù)，含有待加工任務(wù)集合TT2,。其中所有任務(wù)都有相同的加工最早起始時(shí)間t1 t2tn 0,但它們所需要的加工時(shí)間 和加工最遲完成時(shí)間不同，即對(duì)于一個(gè)任務(wù)Ti T,其所需加工時(shí)間為L(zhǎng)i ,加工最遲完成時(shí)間為 d i (1 i n)且Li Lj,di dj,(i j),試設(shè)計(jì)一個(gè)多項(xiàng)式時(shí)間算法，給出任務(wù)集合的排工表，使能按要求完成的任務(wù)數(shù)達(dá)到最大。要求證明你所設(shè)計(jì)算法的正確性，并分析其時(shí)間復(fù)雜性，并通過 下述實(shí)例說明算法的運(yùn)行情況：T,T2 T 3 T 4 T5 T6,Li 6,L2 4,L3 3, L4 5L 7,L6 2;di 8,d29,d

7、3 10,d4 11,d5 16,d6 17;算法，將所有任務(wù)按其結(jié)束時(shí)間di由小到大排列，若滿足1 i n時(shí)， 有di dj。令S空，S為排工表。 S S T1, k 1,m 1若k n,轉(zhuǎn)設(shè)對(duì)k個(gè)任務(wù)，已經(jīng)安排了 m個(gè)任務(wù)加工。L(s) L(T)。則對(duì) Ti S第k 1個(gè)任務(wù)，只要有L(s) Lk1 dk1,則將其安排為第m 1個(gè)任務(wù)：即S S Tk 1, m m 1,k k 1,然后轉(zhuǎn)若L(s) Lk 1 dk1,則從已安排的m個(gè)任務(wù)中，另?yè)褚粋€(gè)加工時(shí)間 最長(zhǎng)的任務(wù)I,若Li Lk 1,則將I從S中移出，將I后的任務(wù)前移， 再把丁并入S, L(s) L(s) Lk 1 Li,k k 1

8、,轉(zhuǎn)否則，k=k+1,轉(zhuǎn)完成，S即排工表。正確性：由于di的排序是一定的，只需證明每一步操作都使加工時(shí)間 最短，則它的加工任務(wù)最多。歸納法證明:(1)當(dāng)n 1時(shí)，顯然成立；(2)假設(shè)n k(k 1)時(shí)正確，即若k個(gè)中拔下m個(gè)，且加工時(shí)間 最短，下面證明n k 1時(shí)也正確。當(dāng)n k 1時(shí)，若L(s) Lk 1 dk 1 ,則安排第k 1個(gè)任務(wù)，顯然k 1個(gè) 任務(wù)最多能安排m 1個(gè)，且時(shí)間最短；若L(s) Lk1 dk1 ,則由于算法中選擇了 S中最長(zhǎng)的任務(wù)且當(dāng) Li Lk 1時(shí)用Tk 1代替I ,使總加工時(shí)間L(s) Lk 1 Li L(s),故仍滿足加 工時(shí)間最短，任務(wù)最多。綜上所述，把n個(gè)任

9、務(wù)排完時(shí)，算法是正確的。復(fù)雜性：設(shè)有n個(gè)任務(wù)，則最壞情況下對(duì)每個(gè)加工任務(wù)都有 L(s) Lk1 dk1 ,從而從S中查找最長(zhǎng)加工時(shí)間任務(wù)，則一次查找為 O(n),每個(gè)任務(wù)都查找為O(n2),排序加工任務(wù)為O(nlogn),因此總的 復(fù)雜度為O(n2)。算法的實(shí)例運(yùn)行情況：d1 8,d2 9,d3 10,d4 11& 16,d6 17;L1 6,L2 4, L3 3,L4 5,Ls 7,L6 2;S=t1 k=1 m=1 Ls=6S=t2 Ls+L2=10>d2 Ti=t1,Li>L2,Ti out, T2 in k=2, Ls=4S=t2t3ls+L3=6<10, k

10、=3,m=2,Ls=6S=t2t3t4Ls+L4=11=d4,k=4,m=3,Ls=11 m=3S=t2t3t4Ls+l5=18>d5,Ti=T4,Li<L5,k=5,Ls=11S=t2t3t4t6Ls+L6=13<d6,k=6,Ls=13,m=4K=6,putout S=t2t3t4t6四、對(duì)于背包問題nmaxPiXin i 1 Xi 0,1 P,W( Z 1 i nWXj m i 1證明：(1)、當(dāng)P NP時(shí)，該問題不存在多項(xiàng)式時(shí)間絕對(duì)近似算法(2)、背包問題存在絕對(duì)近似性能比 Ra 2的多項(xiàng)式時(shí)間近似算法 證明：(1)假設(shè)存在A,則存在常數(shù)(2):實(shí)例P P.Pn為價(jià)值

11、，W W1.Wn為重量，m Z為背包容量nmax PiXi 詢問：求0,1向量X,使n i 1。WXi m i 1算法：將物體按照巴排序，使且 旦 康 WW W2Wn從1到n將物體裝包，直到不能裝為止，記其總價(jià)值和為GA(I)取 A(I) maxGA(I),maxP(Wi B) 1 i n復(fù)雜性：步驟O(nlog n),步驟O(n),故總的時(shí)間復(fù)雜性為O(nlog n)近似性能比：設(shè)GA(I)包含物體價(jià)值為PiP.，則P P2 . Pr Pr 1 OPT(I),而 A(I)rP,A(I) Max ,r故 2A(I)Pi Pmax OPT(I),i 1即 OPTin 2,Ra 2 A(I) n五

12、、n個(gè)整數(shù)a遇2,.an ,正整數(shù)m。求向量x1,x2,xnai 。i 1i 1證明是NPC的；若aaj ,求多項(xiàng)式時(shí)間算法，證明其正確性。j i六、給定WPAR問題實(shí)例：集合R ri,0，對(duì)于每個(gè)ri R有長(zhǎng)度S(rJ Z*,1 i n。詢問：是否存在子集R R,使S(ri) 因此，必存在R R使 S(ri) - S(ri)R2 R RS(ri)?ri R'2 ri RR'、試?yán)脛澐諴AR是NPC問題，證明WPAR問題屬于NPC類;(2)、試設(shè)計(jì)擬多項(xiàng)式算法：(a)判斷R是否存在，(b)若存在，應(yīng)給出一個(gè)滿足詢問條件的R。(3)、針對(duì)如下實(shí)例，說明你設(shè)計(jì)算法的執(zhí)行過程R J

13、 , % , % , L , 1S ( ri)1,5,7,8.9解：(1)、證明WPAR是NPC證明：(將 PAR WPAR)設(shè) PAR 實(shí)例為 A:為.4 , B S(a),73構(gòu)造 WPAR 實(shí)例：:”2,.anbz,其中 4 7B,b2 -B若PAR中存在一個(gè)劃分，使得 S(ai)-,則在 WPAR中， a2，B 7B 3-S(ai) bi 一 B 4B,而 S(ai) b2 B 2B。A22A A221若 WPAR 中存在 R R使 S(ri) S(n),則 S(r) 2B。R2 R RR分析元素構(gòu)成，R中必含d不含“，而R R中必含bi ,不含b2。則有S(ri) b2旦，S(ri)

14、 bi B,即A中存在一個(gè)劃分。R2 R R2又上述變換可在多項(xiàng)式時(shí)間內(nèi)進(jìn)行，因此PAR WPAR ,又PAR NPC ,因止匕 WPAR NPC(2)、設(shè)計(jì)WPAR擬多項(xiàng)式算法解：設(shè)BS(n),若B不能被3整除則無劃分；若B能被3整除，則設(shè)計(jì)表t為n行，旦1列。3.T,前i個(gè)元素中有元素和為j","F,其它情況'若tn,與t ,則最終回答yes,否則no 3 ti,0 T t(1,j) T若 ti 1, j則 ti,j T若 ti 1, j S(ri) T ,則 ti, j T ti, 1 F t0, j F求解算法：記旦為b,記n a31、if (a 0或b 0

15、),則返回A為所求else if (ta 1,bT)2、a , go1 else3、將a加入集合b b S ai ;a , go1(3)、用設(shè)計(jì)算法求解實(shí)例R 1,5,7,8,9, B 30j： i01TT2TTTT3TTTTTT4TTTTTTT5TTTTTTTT七、給定2SAT問題實(shí)例，布爾變量集合 U u1,u2,.嗚，項(xiàng)集合 C C1,C2,.Cn,Ci Xi,y u“2,.un U,?,1 i n,x,y 為 U 上布爾 變量字母。試設(shè)計(jì)多項(xiàng)式時(shí)間算法：（1）、判定2SAT實(shí)例是否有可滿 足真值指派；（2）、若有可滿足真值指派則算法給出使 C滿足U的真 值指派。八、證明團(tuán)問題屬于NPC

16、思路：已知頂點(diǎn)覆蓋VC NPC,而VC最大獨(dú)立集問題，故最大獨(dú)立 集問題 NPC （若V是G上的點(diǎn)覆蓋，則V V是G上的最大獨(dú)立集。 若V是G上的最大獨(dú)立集，則V V是G上的點(diǎn)覆蓋）。又最大獨(dú)立集 問題 CL,故CL NPC （若V是G上的最大獨(dú)立集，則V在G的補(bǔ)圖Go 上所對(duì)應(yīng)的子圖是Go上的團(tuán)）點(diǎn)覆蓋：G上的最小頂點(diǎn)集合V , V覆蓋G上所有的邊；獨(dú)立集：G上的點(diǎn)集合V , V中任兩點(diǎn)之間無邊；補(bǔ)圖：Go V ,E ,V V, （? ? ?）團(tuán)：G上最大完全子圖九、TSP判定問題是數(shù)問題嗎？是否存在擬多項(xiàng)式算法？為什么？答：TSP判定問題是數(shù)問題，因?yàn)槿蝺沙鞘虚g的距離d i,j及界值B 沒

17、有任何約束。因?yàn)榭梢詫?HC TSP,從而證明TSP NPC,而TSP有 限制1 d i,j 2,事實(shí)上d i,j 1或2,故不受限制的原始TSP問題 是強(qiáng)NPC。因此TSP問題不存在擬多項(xiàng)式時(shí)間算法。十、集合覆蓋問題T實(shí)例： S s1s2,.sn, C C1C2,Cn, C 為子集族詢問：求C C,使Ci S且C|最小Ci C求證：P NP時(shí)，上述問題無多項(xiàng)式時(shí)間絕對(duì)近似算法證明：若限制S 3q,Ci 3,Ci C,則集合覆蓋問題變?yōu)閄3C問題。而X3C NPC ,故集合覆蓋問題是 NPC問題。(反證法)設(shè)存在多項(xiàng)式時(shí)間絕對(duì)算法 A,有A(I) OPT(I) k現(xiàn)將I復(fù)制K 1份到I ,易知

18、OPT (I ) (k 1)OPT(I),在I上應(yīng)用算法AA(I )kA(I )k 1有 A(I ) OPT (I ) k, A(I ) (k 1)OPT(I ) k, OPT (I) 1,故： k1k 1OPT(I )(之所以取整，是因?yàn)榧细采w問題是求最小值問題)因此可以構(gòu)造算法A： (1)、I I ; (2)、對(duì)I調(diào)用A,得子集族的子集及A(I ) ； (3)、計(jì)算 如 即為實(shí)例I的最優(yōu)解值OPT(I) k 1因?yàn)锳是多項(xiàng)式的，所以A也是多項(xiàng)式的，這就多項(xiàng)式時(shí)間回答了集合覆蓋問題。而我們已知集合覆蓋問題是 NPC,這與P NP矛盾，故假設(shè)不成立。即不存在多項(xiàng)式時(shí)間絕對(duì)近似算法。十二、排工

19、問題(區(qū)間排工)實(shí)例：只有一臺(tái)機(jī)器，n個(gè)任務(wù)，T,T2,.Tn。對(duì)于每任務(wù)有加工起始時(shí)間n ,終止時(shí)間di ,加工長(zhǎng)度l詢問：加工表(tj9),(tn),(tn)表示。的真正開始。使 (tk) r(tk)按時(shí)完成。i j 時(shí)，(ti)(tj) l(tj) , tj 在 ti 之前(tk) l(tk) d(tk)開始，或 (ti) l(tj) (tj) ,ti在tj之前開始。(兩個(gè)任務(wù)不同時(shí)開始 進(jìn)行)試證：(1)、問題NPC(2)、若限制ri r2 .rn r。，稱為限制排工問題，試設(shè)計(jì)一多項(xiàng)式算法，限制排工任務(wù)數(shù)目最大，再證明算法的正確性，分析其復(fù)雜性。解：(1)見教材，試圖將PAR區(qū)間排工

20、。 n設(shè)PAR實(shí)例A ai,a2an,對(duì)每一個(gè)a、有S0)均為整數(shù),BS(a“。1 1根據(jù)PAR問題實(shí)例構(gòu)造排工問題實(shí)例：T3',.3, E, r(ti) r(t2) r(tn)0BB 1d(ti) d(t2) . d(tn) B 1,L(ti) S(ai),r(E)- ,d(E) ,我們不考慮B為奇數(shù)的情況，因?yàn)锽為奇數(shù)時(shí)，PAR不存在一 個(gè)劃分。若PAR存在一個(gè)劃分A,則可如此排工：將A中a、所對(duì)應(yīng)的任務(wù) ti安排在E之前完成，將A A所對(duì)應(yīng)的任務(wù)安排在E之后完成。由 此排工問題存在一個(gè)排工。若排工問題存在一個(gè)排工，則可如此進(jìn)行劃分：將位于E之前的 任務(wù)t對(duì)應(yīng)的ai置入集合A ,

21、E之后的任務(wù)所對(duì)應(yīng)的a放在A A中。 由于E之前的任務(wù)加工長(zhǎng)度為 旦 旦(B為偶數(shù))，E之后的任務(wù)加2 2一一 一、，B 1BB工長(zhǎng)度為B 1 B 1 ( 1)一, 而L(ti) ?(ai), 故222BS(ai)S(ai);,即PAR存在一個(gè)劃分。ai Aai A A2因此，我們得 PAR區(qū)間排工，由于 PAR NPC ,故區(qū)間排工NPC。(2)、算法，將所有任務(wù)按其結(jié)束時(shí)間di由小到大排列，若滿足1 i n時(shí)，有di dj。令S空，S為排工表。 S S T1, k 1,m 1若k n,轉(zhuǎn)設(shè)對(duì)k個(gè)任務(wù)，已經(jīng)安排了 m個(gè)任務(wù)加工。L(s) L(T)。則對(duì) Ti S第k 1個(gè)任務(wù)，只要有L(s)

22、 Lk1 dk1,則將其安排為第m 1個(gè)任務(wù)：即S S Tk 1, m m 1,k k 1,然后轉(zhuǎn)若L(s) Lk 1 dk1,則從已安排的m個(gè)任務(wù)中，另?yè)褚粋€(gè)加工時(shí)間 最長(zhǎng)的任務(wù)I,若Li Lk 1,則將I從S中移出，將I后的任務(wù)前移， 再把丁并入S, L(s) L(s) Lk 1 Li,k k 1 ,轉(zhuǎn)否則，k=k+1,轉(zhuǎn)完成，S即排工表。正確性：由于di的排序是一定的，只需證明每一步操作都使加工時(shí)間 最短，則它的加工任務(wù)最多。歸納法證明：(3)當(dāng)n 1時(shí)，顯然成立；(4)假設(shè)n k(k 1)時(shí)正確，即若k個(gè)中拔下m個(gè)，且加工時(shí)間 最短，下面證明n k 1時(shí)也正確。當(dāng) n k 1 時(shí)，若

23、L(s) Lk 1dk1,則安排第k 1個(gè)任務(wù)，顯然k 1個(gè)任務(wù)最多能安排m 1個(gè)，且時(shí)間最短；若L(s) Lki dki ,則由于算法中選擇了 S中最長(zhǎng)的任務(wù)且當(dāng) Li Lk i時(shí)用Tk i代替工，使總加工時(shí)間L(s) Lk i Li L(s),故仍滿足加 工時(shí)間最短，任務(wù)最多。綜上所述，把n個(gè)任務(wù)排完時(shí)，算法是正確的。復(fù)雜性：設(shè)有n個(gè)任務(wù)，則最壞情況下對(duì)每個(gè)加工任務(wù)都有 L(s) Lki dki ,從而從S中查找最長(zhǎng)加工時(shí)間任務(wù)，則一次查找為 O(n),每個(gè)任務(wù)都查找為O(n2),排序加工任務(wù)為O(nlogn),因此總的 復(fù)雜度為O(n2)。ii十三、給定n個(gè)整數(shù)&戶2,.an,滿

24、足ai aj (超遞增序列)，有一正 j in整數(shù)s,試設(shè)計(jì)算法A,找出一 n維0, I向量Xi.Xn,使得s aiXiii或無解。解：算法Assfor i n downto i doif s ai thenxi i; s s ai;elseXi 0;endifendforif s 0 then向量X %xn為答案 else 回答noendifi ii i證明：因?yàn)閍 aj,所以若ds ,必有aj s,故Xi應(yīng)為1,否則ji使X1x全為1也沒有正確答案復(fù)雜度：易知為O(n)。十四、(1)平面圖的最大團(tuán)問題有多項(xiàng)式時(shí)間算法嗎？Why?答：有，因?yàn)楫?dāng)在平面圖上考慮團(tuán)問題時(shí)，任何平面圖都不會(huì)含有多于

25、4個(gè)頂點(diǎn)的完全圖，故只需檢查所有的頂點(diǎn)個(gè)數(shù)，不超過4個(gè)子圖 就能找到極大團(tuán)。因4是常數(shù)，故子圖數(shù)目是多項(xiàng)式有界的。所以必 有多項(xiàng)式算法。平面圖的3著色問題有多項(xiàng)式算法嗎？ Why?答：沒有，因?yàn)槲覀兛梢栽O(shè)計(jì)一個(gè)轉(zhuǎn)線軌道圖，用局部替換技術(shù)將一 般圖中的交點(diǎn)處理，將其轉(zhuǎn)化為平面圖。一般圖的3著色問題NPC, 故平面圖3著色也是NPC的，所以不存在多項(xiàng)式時(shí)間算法。十五、當(dāng)P NP時(shí)，TSP優(yōu)化問題是否存在Ra的多項(xiàng)式算法？答：不存在，用反證法證明。證明：設(shè)存在常數(shù)k ,使Ra k ,即存在算法A ,對(duì)TSP的任意實(shí)例G 有A(G) k*OPT(G)。設(shè)Gh (V,E)是哈密頓問題任意實(shí)例，由Gh構(gòu)造

26、 TSP問題實(shí)例Gtsp如下。V(Gtsp) V(Gh) V1,(u,v) E(Gh)d(u,v)kv,(u,v) E(Gh)若 Gh 存在哈密頓回路，則 OPT(Gtsp) V , A(Gtsp) KOPT(Gtsp) kv 若 Gh 不存在哈密頓回路，則 OPT(Gtsp) V,A(Gtsp) OPT(Gtsp) kv 因此可以設(shè)計(jì)哈密頓問題的TSP實(shí)例，調(diào)用A算法由A(G) kV是否成立判定哈密頓是否存在解，又 A是多項(xiàng)式時(shí)間的，即哈密頓可以多項(xiàng)式時(shí)間求解，這與HC NPC矛盾。故假設(shè)不成立，TSP不存在Ra的多項(xiàng)式算法。十六、劃分問題的擬多項(xiàng)式時(shí)間算法，并求劃分的具體方案BS(ai)解

27、：設(shè)ai A ，若B為奇數(shù)，顯然不能劃分。若B為偶數(shù)，設(shè)一. T如果a.包括總價(jià)值為j的子集個(gè)布爾變量：(,)F其它情況t(n,力 T若 2，則回答yes,否則no計(jì)算。j) T的條件：若t(i 1，j) T,則 t(i，j) T若 t(i 1，j S(a。)T,則 t(i,j) T。0) T t(i， 1) F框圖如右：B時(shí)間復(fù)雜度：外循環(huán)n,內(nèi)循環(huán)3,故O(nB)。因?yàn)锽的輸入長(zhǎng)度為 log2B,并不是輸入長(zhǎng)度的多項(xiàng)式，故不是多項(xiàng)式算法，是擬多項(xiàng)式 算法，O(nB) O(n210g2B)。十七、已知 MAXLA問題屬于NPC類，MAXLA問題描述為實(shí)例：簡(jiǎn)單圖G=(V, E)及正整數(shù)K。詢

28、問：是否存在對(duì)應(yīng)映射 P:A1,2，.，|V|,使 |P(u) P(v)| K?(u,v) E試證明MINLA問題也屬于NPC類，MINLA問題為實(shí)例：與MAXLA相同詢問：是否存在對(duì)應(yīng)映射 P:VJ1,2,.,|V|,使 |P(u) P(v)| K?(u,v) E證明：試圖將MAXLA MINLA設(shè)圖G(V,E)及正整數(shù)k為MAXLA的實(shí)例，定義MINLA的實(shí)例為圖G (V ,E)其 中 V V,E (u,v)|u v,(u,v) E.n(n2 1)6n(n 1)( n 1) kk,即G為G的補(bǔ)圖。對(duì)頂點(diǎn)集合V中所有可能的映射P,考慮：固定一點(diǎn)i與其它所P(u)固定頂點(diǎn) i , P0) P(

29、j)P(i)P(u)P(v)P(i) - 11i(ni)P(i)u,v V u vn 12 ii 1n(n 1)(2n 1) 1n(n 61)又G與G互為補(bǔ)圖P(u)所以(u,v) eP(v)n(n2 1)P(u) P(v)(u,v) EP(u)(u,v) EP(v)|P(u)所以(u，v) eP(v)|K當(dāng)且僅當(dāng)|P(u)(u,v) EP(v)| 嗎6所以MAXLAMINLAMINLA NPC十八、用圖靈歸約技術(shù)證明k個(gè)最大子集 NP HARDk個(gè)最大子集問題:實(shí)例：Ae但.%, n個(gè)元素,S(a) Z* ,每個(gè)元素有一個(gè)長(zhǎng)S(q) Z*o兩個(gè)非負(fù)整數(shù)B S(a)和k 2 A a A詢問：A

30、中是否有k個(gè)不同的子集A Ao滿足S(A) S(a) B且S(A) B, a A A,其中 S(A) S(a) a A證明：假設(shè)SA,S,B,K是解k個(gè)最大子集問題的子程序，其中A 電an，長(zhǎng)度函數(shù)S：A Z ,B S(A),k 21A設(shè)集合A ai，a2an和長(zhǎng)度函數(shù)S:A Z是劃分問題的任意實(shí)例。設(shè)計(jì)劃分問題的算法。從計(jì)算S(A)開始，若S(A)是奇數(shù)，則回答NO。b S(A)否則 工，并調(diào)用子程序SA，S，B，K算法A：若S(A)為奇數(shù)，則劃分問題回答NO,結(jié)束。b2置 2 ,調(diào)用算法B算法B：求滿足S(A) b，S(A) S(a) b，a A A的子集A的最大數(shù)目L*。Lmin 0,L

31、max 2n , ( L可能的界限) *若Lmax Lmin 1 ,則L Lmin并結(jié)束。L(Lmax /。)/2；調(diào)用SIASbU ,檢查是否有L個(gè)子集A滿足S(A) b若回答YES,則扁 L，轉(zhuǎn)若回答NO ,則Lmax L,轉(zhuǎn)根據(jù)求出的滿足S(A) b的子集A的最大數(shù)目L*,調(diào)用一次_ _ *SA,S,b 1, L若回答 YES,則表明所有滿足S(A) b的子集A ,也都滿足S(A) b 故相應(yīng)劃分問題回答 No若回答NO ,則滿足S(A) b的子集一定存在，所以劃分回答Yes。十九、排工問題大全1、區(qū)間排工實(shí)例：有限任務(wù)集合T ti,t2,.tj,r(tk)最早開始時(shí)間，d(tk)最晚結(jié)

32、 束時(shí)間，l(tk)加工長(zhǎng)度。詢問：是否存在排工表(tk) k 1,2n(1)區(qū)間排工 NPC,用劃分 區(qū)間排工區(qū)間排工強(qiáng)NPC證明：將3劃分區(qū)間排工設(shè)三劃分實(shí)例為A a1，a2備a3m), S(ai) Z,B Z由此構(gòu)造區(qū)間排工實(shí)例：T A t1,tm i), L(ti) 1,i 1.m 1, L(ai) S(a),i 1.3m, r(ti) iB ir(ai) 0, d (ti) iB i, d (ai) mB m 1若三劃分問題回答yes,變換后的區(qū)間排工也回答yes。若區(qū)間排工回答yes,則三劃分問題也回答yes。且該變換是擬多 項(xiàng)式變換。因?yàn)椋喝齽澐?強(qiáng)NPC,所以：區(qū)間排工強(qiáng)NPC

33、2、最小遲序排工，有半序關(guān)系和最晚結(jié)束時(shí)間，不能按時(shí)完成的任務(wù)k,證明 NPC,用CL證明。3、先行約束排工：L為1,處理機(jī)為m ,半序關(guān)系(1)沒有半序或半序?yàn)闃鋾r(shí)是 P問題(2) m 1or2日寸是P問題4、多任務(wù)排工實(shí)例：m個(gè)處理機(jī)Pi,P2,Pm處理任務(wù)T 我.tn,加工時(shí)間u(ti),任務(wù)之間有半序關(guān)系。詢問：最短時(shí)間內(nèi)完成NI(I,L) 2 2(1) OPT(I) m (任意主次表，有空就加工)，非空閑算法算法：開始所有處理都空閑，所有任務(wù)都未加工對(duì)任務(wù)主次表從左向右掃描，判定每個(gè)任務(wù) tj是否處于加工狀態(tài)。若可加工，則安排至下標(biāo)最小的空閑處理機(jī)上加工 任務(wù)主次表是按半序關(guān)系的。N

34、I(I,L) c 1 2 -證明OPT(I) m將N(I ,L)的時(shí)間區(qū)0,N(I, L)分成兩部分：A每個(gè)區(qū)間所有機(jī)器都空 閑B至少有一臺(tái)機(jī)器空閑B 1. J顯然k不相交則在半序關(guān)系中存在一條通路ti1,t2,.%,該通路覆蓋子區(qū)間1 . kl所以：OPT (I) u(tj) j 1ku(j 1j)OPT(I)1 nu(tij)m j 1NI(I,L)1 n一(u(tj)m j 1(mk1) u(i 11 n m 1 i) u(tj)m j 1mku( i) OPT(I) i 1OPT (I)即 NI (I,L)注：當(dāng)最大加工時(shí)間D,限制m 2,D 13)時(shí)，變成PAR問題2ai A5、獨(dú)立

35、任務(wù)排工實(shí)例：任務(wù)T1T2,.丁一加工長(zhǎng)度1也,.儲(chǔ)(1) LPT算法，先排時(shí)間長(zhǎng)的. LPT(I). OPT(I)4 13 3m將任務(wù)排序，形成加工主次表L Ti,T2,.Tn, ti t2tn對(duì)主次表從1到n掃描，若有空閑機(jī)器，則將任務(wù)安排空閑機(jī)器上加工，直至完成。復(fù)雜度：O(nlogn),多項(xiàng)式算法證皿42：OPT (I)3 3m當(dāng)m 1時(shí)，顯然成立。當(dāng)m 1時(shí)，假設(shè)最后完成的任務(wù)為tn。若最后完成的任務(wù)是tk,則只考慮前k個(gè)任務(wù)，若前k個(gè)滿足，則n個(gè)當(dāng)然滿足在0,LPT(I) tn內(nèi)所有任務(wù)都非?？臻en 1LPT(I) tn t -i 1 mLPT (I)一tim i 1tn1 n又

36、OPT (I)tim i 1LPT(I) 1 m JtnOPT (I) m OPT (I)若OPT (I) 3tn,則每個(gè)機(jī)器上最多安排 2個(gè)任務(wù)，這樣的排工是最優(yōu)的，當(dāng)然滿足;若0PT(I)竟,則副4 13 3m綜上得證(再舉例說明上界不能小于 3)(2) F算法：多項(xiàng)式近似方案:F1 _1LOPT(I) 1 2將任務(wù)從大到小時(shí)間排序:T Ti,T2,.Tn確定正整數(shù)k,對(duì)前k個(gè)任務(wù)，求最優(yōu)先排工，后n k個(gè)按 先大后小順序排工。證明：設(shè)T是前k個(gè)任務(wù)的排工時(shí)間,若F(I) T,則OPT(I) F(I ), 設(shè) F(I) T。在0,F(I) tki區(qū)間所有的處理器非空閑，tki開始做時(shí)，其它

37、有 任務(wù)可能未做完。 nti m(F(I) tki) tk i i 11 nm 1OPT(I ) ti F(I) tk 1 m i 1m又，至少有一臺(tái)機(jī)器加工了 tk1和前k個(gè)任務(wù)的平均個(gè)數(shù)，即1 -m個(gè)任務(wù)；又，tk1是前k 1個(gè)中最小的。kOPT(I) (1- )tk 1mm 1m 11F (I )1 m tk 11 m tk 11 mOPT (I) OPT (I)1 點(diǎn) tk1 1 寺算法復(fù)雜度：TA(m,n) O(mk nlog n)二十、裝箱問題實(shí)例：n個(gè)物體集合，S ai,a2an,每個(gè)物體a S,體積為W(ai), 容量為C的箱子。詢問：需要多少個(gè)箱子才能全部裝完首次適合算法Fi

38、t-First:劇2算法：按照一定順序依次裝入箱子。O(n)。證明：任意兩個(gè)相鄰箱子Bi上裝入物體體積大于c,B1.Bk,n若 FF(I)為偶數(shù),則 2 W(ai) C FF(I)；又,i 1nW(ai) C OPT (I) i 1FF (I) 2OPT (I)n若 FF(I)為奇數(shù)，則 2 W(ai) C (FF(I) 1),i 1FF(I ) 2OPT(I ) 1又，F(xiàn)F(I),OPT(I)為整數(shù)，OF* 2(2) FD算法，先大后小將物體排序，體積從大到小依次裝箱,11FD(I) OPT(I) 49卜一、背包問題實(shí)例：有限集合 UUi,U2,.Un, S(u)Z為重量,W(u) Z為價(jià)值

39、判定問題：是否存在UU,S(Ui)Ui UB, V(Ui)Ui UMaxPiXi優(yōu)化問題:,求向量不.%。nXiWi Mi 1(1)、判定問題 NPC限制 S(u)為偶數(shù)，S(u) V(u)B k 1 S(uJ ,則上述問題變?yōu)?u u2 ui uPAR 問題。 PAR NPC,背包 NPC。(2)、背包問題無多項(xiàng)式時(shí)間絕對(duì)近似算法，將價(jià)值擴(kuò)大k 1倍，變成另一個(gè)問題。反證法.(3)、Ra(I) 2的A算法(見前文)*，(4)、多項(xiàng)式近似方案： 1 ,證明這個(gè)公式，要求給出時(shí)間Pmax1 k復(fù)雜度算法描述：對(duì)任意一種k個(gè)元素的組合都先放入包中嘗試，最后選擇一個(gè)最好的嘗試。偽代碼：k)Procedure approx (P,W, M , n, k) /(價(jià)值、重量向量、重量 限制、元素個(gè)數(shù)、 Pmax 0for all combinatio ns I of size k and weight M do Pi P i IPmax max Pmax, P L(I, P,W, M , n) /L()子程序 end forend下面算法先裝k個(gè)再繼續(xù)裝：Procedure L(I,P,W,M