資源描述：
《算法分析與設(shè)計(jì)2007第7講》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第七講上次內(nèi)容：(1)證明npc問(wèn)題(2)sat,3sat,3dm,vc,cl,par,vi,hc(3)進(jìn)一步證明，x3c，子圖同構(gòu)，集合覆蓋，等等，其他自己看書(shū)，原來(lái)有的人專門(mén)看怎樣證明npc問(wèn)題。用的是限制技術(shù)。下面繼續(xù)證明：背包問(wèn)題：這個(gè)問(wèn)題以后會(huì)用，經(jīng)常用。應(yīng)用背景：挑選最大價(jià)值的東西裝入背包中，很多東西，從中挑選。背包容量是有限的。實(shí)例：有限集合：U={u1,u2,…,un}，S(ui)?Z+表示每個(gè)元素的價(jià)值，w(ui)?Z+表示每個(gè)元素的重量。B?Z+，K?Z+。詢問(wèn)：是否存在U’íU，滿足，。國(guó)家預(yù)算，科技投資，背包問(wèn)題。定理：背包問(wèn)題K
2、napsack?NPC。證明：限制技術(shù)，注意針對(duì)實(shí)例限制。不能針對(duì)其他限制。限制為偶數(shù)，S(ui)=W(ui)，B=K=。上述問(wèn)題變?yōu)閯澐謫?wèn)題，滿足條件的背包實(shí)例一定是劃分問(wèn)題實(shí)例。因?yàn)閯澐謫?wèn)題是NPC，所以背包問(wèn)題也是NPC。好好理解怎么回事。多任務(wù)排工問(wèn)題：獨(dú)立任務(wù)的多個(gè)機(jī)器排工。背景是什么：很多任務(wù)，加工時(shí)間不同，用m臺(tái)機(jī)器并行加工，怎樣排列任務(wù)使并行加工時(shí)間最短。實(shí)例：有限任務(wù)集合：A={a1,a2,…,an}，每個(gè)任務(wù)的加工時(shí)間長(zhǎng)度L(ai)?Z+。加工機(jī)器數(shù)m?Z+，加工最后期限D(zhuǎn)?Z+。詢問(wèn)：是否存在劃分A=A1èA2è…èAm，Ai?Aj
3、=?(第8頁(yè)第七講劃分本身就有這樣的含義)，使￡D。解釋：A1中任務(wù)的總時(shí)間、A2中任務(wù)的總時(shí)間、。。。、Am中任務(wù)的總時(shí)間。那個(gè)最長(zhǎng)。加工時(shí)間最長(zhǎng)的機(jī)器所用時(shí)間最短。中國(guó)的排工協(xié)會(huì)。Scheduling。用最少時(shí)間完成全部任務(wù)。用最少的時(shí)間完成所有任務(wù)。定理：多任務(wù)排工屬于NPC。證明：限制m=2，D=，這樣限制后的實(shí)例成為劃分問(wèn)題實(shí)例。所以劃分問(wèn)題是NPC的。4.2.2局部替換技術(shù)*3sat的證明中，將一個(gè)sat子句替換為若干3sat子句，得到證明。劃分三角形問(wèn)題：PIT，劃分三角形，原創(chuàng)很精彩。這也是一個(gè)原創(chuàng)型的證明。實(shí)例：G=(V,E)，
4、V
5、=
6、3q，q?Z+。詢問(wèn)：是否存在V的劃分：V=V1èV2è…èVq滿足任意
7、Vi
8、=3，且Vi={vi[1],vi[2],vi[3]}中的3個(gè)點(diǎn)在G中形成三角形。定理：劃分三角形問(wèn)題屬于NPC類，證明：X3CμPIT，后來(lái)我也用了一次。替換是常用的技術(shù)。實(shí)例：X={x1,x2,…,x3q}，C={c1,…,cn}，ciíX，
9、ci
10、=3。詢問(wèn)：是否存在C的子集C’，嚴(yán)格覆蓋X。第8頁(yè)第七講例子：X3C的實(shí)例，
11、X
12、=3q，
13、C
14、=n。X={x1,y1,z1,x2,y2,z2}，C={(x1,y1,z1)，(x1,y1,z2)，(x2,y2,z2)}q’=q
15、+3n=2+3*3=11有的三角圖可劃分4個(gè)三角形，有的三角圖可劃分3個(gè)三角形。一個(gè)三角圖最多劃分4個(gè)三角形。?X3C實(shí)例中有3元素嚴(yán)格覆蓋，則能劃分出4q+3(n-q)=q+3n個(gè)三角形。能否劃分超過(guò)q+3n個(gè)三角形。?若PIT中能劃分出q+3n個(gè)三角形，必有q個(gè)三腳圖能劃分出4個(gè)三角形。這就是最多的。不可能超過(guò)q個(gè)，這是當(dāng)然的。若少于q個(gè)，則最后劃分出三角形個(gè)數(shù)少于q+3n個(gè)。例如是q1個(gè)，剩余的三腳圖都是不完整的，每個(gè)最多劃分3個(gè)三角形，于是三角形個(gè)數(shù)為：4q1+3(n-q1)=q1+3n個(gè)。q是上限所以得證。第8頁(yè)第七講區(qū)間排工問(wèn)題：實(shí)例：有限任
16、務(wù)集合，T={t1,t2,…,tn}，只有一臺(tái)機(jī)器。r(tk)：最早起始時(shí)間d(tk)：最晚結(jié)束時(shí)間L(tk)：加工長(zhǎng)度詢問(wèn)：是否存在排工表：s(tk)，k=1,2,…,n，使d(tk)-L(tk)3s(tk)3r(tk)，每個(gè)任務(wù)都能按時(shí)完成。任意ti,tj，i1j，s(ti)3s(tj)+L(tj)或s(tj)3s(ti)+L(ti)就一臺(tái)機(jī)器，處理機(jī)，當(dāng)然要這樣了。一心不可二用。定理：區(qū)間排工屬于NPC類。證明：PARμ區(qū)間排工。PAR的例子，A={a1,a2,a3,a4,a5}，S(a1)=2，S(a2)=5，S(a3)=10，S(a4)=9，S
17、(a5)=8。T={t1,t2,t3,t4,t5,t}B=，應(yīng)該假設(shè)B是偶數(shù)，才好。r(t1)=r(t2)=r(t3)=r(t4)=r(t5)=0。d(t1)=d(t2)=d(t3)=d(t4)=d(t5)=B+1=35，比總價(jià)值多1。L(t1)=S(a1)=2，L(t2)=S(a2)=5，L(t3)=S(a3)=10，L(t4)=S(a4)=9，L(t5)=S(a5)=8。r()==17，d()=+1=18，L()=1。(?)若劃分問(wèn)題實(shí)例回答是，則將一部分總長(zhǎng)度為第8頁(yè)第七講的元素對(duì)應(yīng)的任務(wù)分別排在[0，]和[+1，B+1]區(qū)間，[，+1]排，于是為
18、滿足條件的解。(?)若有滿足條件的排工，則只能排在[，+1]，其他任務(wù)排在兩邊，
