完全問題一些典型的例子課件

NP-完全問題(NPCompleteProblem)

ThinkingaboutAlgorithmsAbstractlyxxx天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院1感謝你的觀看2019年5月19日NP-完全問題(NPCompleteProblem)

T主要內(nèi)容NP-完全問題：一些典型的例子NP-完全問題：相關(guān)定義近似算法兩種新的計(jì)算模型2感謝你的觀看2019年5月19日主要內(nèi)容NP-完全問題：一些典型的例子2感謝你的觀看2019NP-Complete:涵義N-NondeterministicDeterministicalgorithm:Givenaparticularinput,itwillalwaysproducethesamecorrectoutputNon-deterministicalgorithm:withoneormorechoicepointswheremultipledifferentcontinuationsarepossible,withoutanyspecificationofwhichonewillbetakenP-Polynomial(time)ComputablePolynomialtimeisassumedthelowestcomplexityCompleteReducible輸入/輸出算法復(fù)雜性變換/封閉性3感謝你的觀看2019年5月19日NP-Complete:涵義N-NondeterminisNP-C:典型的問題（1）問題1圖著色問題判定問題：是否存在不超過k種顏色的著色方案?優(yōu)化問題：求圖的最小著色數(shù)和著色方案問題2作業(yè)調(diào)度問題判定問題：是否存在罰款額不超過k的作業(yè)調(diào)度?優(yōu)化問題：求最小罰款額調(diào)度4感謝你的觀看2019年5月19日NP-C:典型的問題（1）問題1圖著色問題4感謝你的觀看NP-C:典型的問題（2）問題3Binpacking問題：假設(shè)有n種物品，它們的尺寸分別為s1,…,sn，0<si≤1另有任意多個(gè)箱子(Bins)，箱子的容量為1，判定問題：任意給定k，是否存在一種裝箱方法使用的箱子數(shù)≤k？?jī)?yōu)化問題：求使用最小箱數(shù)的裝箱方法5感謝你的觀看2019年5月19日NP-C:典型的問題（2）問題3Binpacking問NP-C:典型的問題（3）問題4背包問題判定問題：是否存在效益值至少為k的可行子集?優(yōu)化問題問題5子集和數(shù)問題s1,s2,┅,sn,C判定問題：是否存在和數(shù)等于C的子集?優(yōu)化問題：求≤C的最大子集和數(shù).可歸約為背包問題:pi=wi.6感謝你的觀看2019年5月19日NP-C:典型的問題（3）問題4背包問題6感謝你的觀看2NP-C:典型的問題（3）問題6CNF(合取范式)-可滿足問題(SAT)判定問題：是否存在真假賦值使得該CNF為真.合取范式例:問題7Hamiltonian回路判定問題問題8TSP(旅行商)問題判定問題：任意給定一整數(shù)k，是否存在一長(zhǎng)度不超過k的Hamiltonian回路？?jī)?yōu)化問題7感謝你的觀看2019年5月19日NP-C:典型的問題（3）問題6CNF(合取范式)-可滿NP-C:典型的問題（4）問題9:節(jié)點(diǎn)覆蓋:無向圖中的每一條邊都被某些節(jié)點(diǎn)關(guān)聯(lián)判定問題：給定無向圖G和正整數(shù)k,是否存在一k節(jié)點(diǎn)覆蓋.優(yōu)化問題：最小節(jié)點(diǎn)覆蓋問題10:給定一無向圖G,k-獨(dú)立集;最大獨(dú)立集.問題11:給定一無向圖G,k-集團(tuán);最大集團(tuán).問題10和11可互相轉(zhuǎn)化:邊互補(bǔ)圖目標(biāo)函數(shù)取整數(shù)值時(shí),優(yōu)化值問題和判定問題等價(jià)我們可用二分查找從判定問題解得到優(yōu)化值的問題的解8感謝你的觀看2019年5月19日NP-C:典型的問題（4）問題9:節(jié)點(diǎn)覆蓋:無向圖中的每一條類P與類NP（ClassP&ClassNP）9感謝你的觀看2019年5月19日類P與類NP9感謝你的觀看2019年5月19日類P(1)算法輸入為問題實(shí)例的二進(jìn)制編碼.定義該0/1字符串的長(zhǎng)度為輸入長(zhǎng)度.例如n個(gè)節(jié)點(diǎn)和m條邊的圖的長(zhǎng)度為Θ(mlogn)(見圖13.1).多項(xiàng)式界:如一算法的最壞情形時(shí)間復(fù)雜度T(n)=O(p(n)),其中p(n)為輸入長(zhǎng)度n的多項(xiàng)式,則稱該算法有多項(xiàng)式界.如一個(gè)問題有多項(xiàng)式界的算法,則稱該問題有多項(xiàng)式界.10感謝你的觀看2019年5月19日類P(1)算法輸入為問題實(shí)例的二進(jìn)制編碼.定義該0/1字符類P(2)類P的定義一個(gè)算法解決判定問題指:對(duì)該判定問題的yes實(shí)例,算法要停機(jī)并給出yes回答.對(duì)no實(shí)例算法要停機(jī)并給出no的回答.具有多項(xiàng)式界的判定問題組成的類稱為類P.多項(xiàng)式的相加,相乘及復(fù)合仍為多項(xiàng)式;所以一個(gè)有多項(xiàng)式界的算法調(diào)用另一有多項(xiàng)式界的算法構(gòu)成的算法仍有多項(xiàng)式界.11感謝你的觀看2019年5月19日類P(2)類P的定義11感謝你的觀看2019年5月19日類NPNon-deterministic--不確定的算法：對(duì)給定輸入字符串w,1.Guessing

不確定地寫一個(gè)稱為”certificate”(guessed解)的字符串c.c實(shí)際上是可行解的一種表示;例如,表示背包問題的n元組,表示圖的字符串或鄰接矩陣.2.checking

使用一確定的有多項(xiàng)式界的算法驗(yàn)證c是否為問題的答案.如果是給出yes,反之,不回答.Polynomial--多項(xiàng)式界:寫c和驗(yàn)證的時(shí)間為O(q(|w|)),q()為某一多項(xiàng)式,w為輸入長(zhǎng)度.12感謝你的觀看2019年5月19日類NPNon-deterministic--不確定的算法：對(duì)不確定的算法:偽代碼VoidnondetA(Stringinput)

Strings=genCertif();

booleancheckOK=verifyA(input,s)

if(checkOK)Output“yes“

returnchecOK為false時(shí)不作反應(yīng).13感謝你的觀看2019年5月19日不確定的算法:偽代碼VoidnondetA(String類NP：幾點(diǎn)說明“不確定”指:對(duì)同一輸入w,算法使用任意多個(gè)不同的c,進(jìn)行驗(yàn)證.對(duì)不同c的這些計(jì)算,可以看作是同時(shí)進(jìn)行的.一個(gè)不確定算法解決判定問題指:對(duì)輸入w,如果它有解,不確定算法一定會(huì)寫出一個(gè)c,使得驗(yàn)證階段能通過,并返回一個(gè)yes回答.如果一個(gè)判定問題有不確定的多項(xiàng)式界的算法則稱它屬于類NP.14感謝你的觀看2019年5月19日類NP：幾點(diǎn)說明“不確定”指:對(duì)同一輸入w,算法使用任意圖著色問題Input:(著色數(shù))k,(節(jié)點(diǎn)數(shù))5,(圖的邊)(1,2)(1,4)...Guessing指寫出長(zhǎng)度為n(節(jié)點(diǎn)數(shù))的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$@等.至少有kn個(gè)“guessings”.Checking指檢查一guessed字符串是否合法及是否是一個(gè)k-著色.如果寫字符串的時(shí)間是O(p1(n)),checking時(shí)間是O(p2(n));而且p1(n),p2(n)是n的多項(xiàng)式(從而也是輸入長(zhǎng)度的多項(xiàng)式),則該不確定算法有多項(xiàng)式界.如果輸入的圖能k著色則不確定算法停機(jī)并給出yes回答.3124515感謝你的觀看2019年5月19日?qǐng)D著色問題Input:(著色數(shù))k,(節(jié)點(diǎn)數(shù))5,(P=NP?類NP：由不確定的多項(xiàng)式界算法的判定問題構(gòu)成的類稱為類NP。P=NP?是計(jì)算機(jī)科學(xué)中最大的問題之一16感謝你的觀看2019年5月19日P=NP?類NP：由不確定的多項(xiàng)式界算法的判定問題構(gòu)成的類稱輸入尺寸（thesizeofinput）(1)是否存在j,k>1使得n=jk?即n是否為一合數(shù)?factor=0;

for(j=2;j<n;j++)

if((nmodj)==0)factor=j;

break;

returnfactor(nmodj)計(jì)算時(shí)間為Θ(log2n)(bit級(jí)運(yùn)算).算法的復(fù)雜度為Θ(nlog2n).但n是輸入長(zhǎng)度m=log2n的指數(shù)函數(shù).所以它是指數(shù)復(fù)雜度算法.ManindraAgrawal等證明了:”n是否為一素?cái)?shù)?”

屬于PManindraAgrawal,NeerajKayal,NitinSaxena,"PRIMESisinP",AnnalsofMathematics160(2004),no.2,pp.781–793.17感謝你的觀看2019年5月19日輸入尺寸（thesizeofinput）(1)是否Thesizeofinput(2)背包問題輸入長(zhǎng)度m為

m=Θ(log2n+log2c+Σlog2pi+Σlog2wi)假定pi=O(c)wi=O(c),則m=O(nlog2c)Θ(nc)不能以m的多項(xiàng)式加以限界,即

nc=O(mk)

不成立,因?yàn)閚c/(nlog2c)k→∞(c→∞),對(duì)所有常數(shù)k.除了涉及數(shù)的計(jì)算外,以前我們分析的多項(xiàng)式復(fù)雜度算法,在以字符串為輸入時(shí),仍是多項(xiàng)式復(fù)雜度算法.18感謝你的觀看2019年5月19日Thesizeofinput(2)背包問題輸入長(zhǎng)度m多項(xiàng)式約化問題P可多項(xiàng)式地約化為問題Q,如果存在一個(gè)有多項(xiàng)式界的確定性算法T,使得：對(duì)每個(gè)輸入字符串x,T產(chǎn)生一字符串T(x).x是P的合法輸入且P對(duì)x有yes答案當(dāng)且僅當(dāng)T(x)是Q的合法輸入且有yes答案證明多項(xiàng)式約化關(guān)鍵在“當(dāng)且僅當(dāng)”問題P可多項(xiàng)式地約化為Q,表示為：PpQTxT(x)PYes/noanswerQ19感謝你的觀看2019年5月19日多項(xiàng)式約化問題P可多項(xiàng)式地約化為問題Q,如果TxT(x)多項(xiàng)式約化定理13.3IfPpQ且Q在P中則P也在P中存在解Q的算法有多項(xiàng)式界q,設(shè)T的復(fù)雜度為多項(xiàng)式p.則T(x)的長(zhǎng)度O(p(|x|))對(duì)輸入T(x)所需時(shí)間為O(q(p(|x|)))解P的復(fù)雜度為O(p(|x|)+q(p(|x|)))可約化的意義:Q至少和P一樣“難”約化關(guān)系有傳遞性20感謝你的觀看2019年5月19日多項(xiàng)式約化定理13.3IfPpQ且Q在P中則P也在P子集和數(shù)可約化為調(diào)度問題多項(xiàng)式變換子集和數(shù)問題的實(shí)例:s1,s2,┅,sn,C;假定S=∑1≤i≤nsi>C對(duì)應(yīng)調(diào)度問題實(shí)例

pi=ti=si,di=C,k=S-Cif部分:子集和數(shù)有解則調(diào)度問題有解onlyif:假定上述調(diào)度問題有罰款額≤k的解該可行調(diào)度的執(zhí)行時(shí)間ti之和≤C(可行性)又因ti=pi=si,所以該可行調(diào)度對(duì)應(yīng)罰款額=S-Σpi=S-Σti≥S-C=k所以其罰款額＝k，而且被調(diào)度的作業(yè)的時(shí)間之和＝C21感謝你的觀看2019年5月19日子集和數(shù)可約化為調(diào)度問題多項(xiàng)式變換21感謝你的觀看2019年NP-難度和NP-完全問題問題Q是NP-難度問題，如果：每個(gè)NP問題都可多項(xiàng)式地約化為問題Q.問題Q是NP-完全問題.如果:它是NP問題,同時(shí)它還是NP-難度問題.NP-完全問題的性質(zhì)所有NP-完全問題,相對(duì)于多項(xiàng)式約化關(guān)系,是自反,對(duì)稱,傳遞的,即構(gòu)成一個(gè)閉類.如果能找到一個(gè)NP完全問題的多項(xiàng)式算法則P=NP有NP-難度問題但不知它是否在NP類內(nèi)(第kth重子集問題)22感謝你的觀看2019年5月19日NP-難度和NP-完全問題問題Q是NP-難度問題，如果：22Problems-unknowninNPKth重子集問題:任給定n+2個(gè)正整數(shù)c1,┅cn,k,L;是否存在{1,2,┅,n}的k個(gè)不同子集S1,┅Sk

使得對(duì)所有i=1,┅,k有Σ部分稱為子集的重量,重量排序第k的子集.當(dāng)k=2n-1時(shí),表示可行解的字符串的長(zhǎng)度有指數(shù)的長(zhǎng)度.我們不知道該問題是否在NP中.圖G的最大集團(tuán)的節(jié)點(diǎn)數(shù)是否=k?上述問題是否在NP?也是未知的!(驗(yàn)證最大集團(tuán),不能在多項(xiàng)式時(shí)間內(nèi)做到)23感謝你的觀看2019年5月19日Problems-unknowninNPKth重子集問題CNF-satisfiablity問題是NP-完全問題定理13.5CNF-satisfiablity問題是NP-完全問題這是著名的Cook定理Cook定理的推論:如果CNF-可滿足問題有多項(xiàng)式界的算法，則P=NP.24感謝你的觀看2019年5月19日CNF-satisfiablity問題是NP-完全問題定理1NP-完全問題證明證明問題Q是NP-完全問題的步驟：

(1)選擇一已知的NP-完全問題P。(2)證明P可多項(xiàng)式的約化為Q背包問題屬于NP＝>子集和數(shù)屬于NP子集和數(shù)問題屬于NP＝>調(diào)度問題屬于NP不計(jì)其數(shù)的這種推導(dǎo).25感謝你的觀看2019年5月19日NP-完全問題證明證明問題Q是NP-完全問題的步驟：25感謝ListsofNP-CompleteproblemsBooleansatisfiabilityproblem(SAT)N-puzzle

Knapsackproblem

Hamiltonianpathproblem

Travelingsalesmanproblem

Subgraphisomorphismproblem

Subsetsumproblem

Cliqueproblem

Vertexcoverproblem

Independentsetproblem

Graphcoloringproblem

26感謝你的觀看2019年5月19日ListsofNP-CompleteproblemsWhatmakesaproblemhard(1)限定問題的一般性（問題的附加限制）實(shí)際應(yīng)用中有特殊性,有可能找到多項(xiàng)式算法例：Hamiltonian回路頂點(diǎn)度<=2時(shí)，Hamiltonian回路問題有多項(xiàng)式算法工程中有靈活性,以某種方式優(yōu)化是NP-難度問題;但以另一方式提出問題可能不是(優(yōu)化標(biāo)準(zhǔn))了解“難問題”的特點(diǎn)27感謝你的觀看2019年5月19日Whatmakesaproblemhard(1)限定Whatmakesaproblemhard(2)3-滿足問題仍為NP-完全問題,但2-滿足問題有多項(xiàng)式算法集團(tuán)問題,當(dāng)頂點(diǎn)度<=常數(shù)d時(shí)屬于類P平面圖集團(tuán)問題屬于類P，因?yàn)槠矫鎴D至多有4-集團(tuán)實(shí)際有意義的做法是提出合理的限制條件和求近似解,研究啟發(fā)式算法.28感謝你的觀看2019年5月19日Whatmakesaproblemhard(2)3-優(yōu)化問題和判定問題3種問題判定問題求優(yōu)化值問題求優(yōu)化解問題優(yōu)化問題至少與判定問題一樣“難”優(yōu)化值問題有多項(xiàng)式算法，則判定問題有多項(xiàng)式算法多數(shù)情況下，如果能在多項(xiàng)式時(shí)間內(nèi)求解決策問題，那么也能在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)值（圖著色問題）；有時(shí)則不能（TSP）29感謝你的觀看2019年5月19日優(yōu)化問題和判定問題3種問題29感謝你的觀看2019年5月19近似算法（1）返回次優(yōu)解的算法。這種算法經(jīng)?？梢酝ㄟ^啟發(fā)式方法得到，例如：貪心法。近似算法必須是多項(xiàng)式時(shí)間算法。為量度近似解對(duì)優(yōu)化解的近似程度定義以下術(shù)語FS(I)是輸入I的可行解集。Val(I,x):實(shí)例I的可行解x的目標(biāo)函數(shù)值opt(I):實(shí)例I的優(yōu)化解的值30感謝你的觀看2019年5月19日近似算法（1）返回次優(yōu)解的算法。這種算法經(jīng)常可以通過啟發(fā)式方近似算法（2）設(shè)A為一近似算法,令A(yù)(I)為輸入I時(shí)該算法輸出的可行解極小化和極大化問題度量近似性能的指標(biāo)rA(I)31感謝你的觀看2019年5月19日近似算法（2）設(shè)A為一近似算法,令A(yù)(I)為輸入I時(shí)該算法輸續(xù)式(13.5)定義的RA(m)為最壞情形rA(I)的值,是與輸入I無關(guān)的指標(biāo):在固定優(yōu)化值m下求最壞情形的比值式(13.6)定義的SA(n)也是一與輸入獨(dú)立的指標(biāo)32感謝你的觀看2019年5月19日續(xù)式(13.5)定義的RA(m)為最壞情形rA(I)的值,是Bin-Packing的近似算法怎么裝不同大小、不同形狀的貨物才能使占用的箱子數(shù)最少。該問題形式化如下：裝箱問題設(shè)S=(s1,…,sn)0<si<=1，1<=i<=n將s1,…,sn

裝入盡可能少的箱子里。假定每個(gè)箱子都有容量1。裝箱問題是NP-難度問題搜索算法有指數(shù)的復(fù)雜度：須試所有可能的S的分劃。33感謝你的觀看2019年5月19日Bin-Packing的近似算法怎么裝不同大小、不同形狀的貨裝箱問題：FFD算法（貪心法）將物品按尺寸遞減排序，箱子從左到右排列并盡可能放在前面的箱子里。算法的時(shí)間復(fù)雜度t(n)=(n2)34感謝你的觀看2019年5月19日裝箱問題：FFD算法（貪心法）將物品按尺寸遞減排序，箱子從左算法：裝箱問題輸入:S=(s1,….,sn)，0<si≤1，1≤i≤n.S代表貨物1,...,n的尺寸，每個(gè)箱子的容量都是1.0。輸出:bin[i]是放物品i的箱子號(hào),1≤i≤n.為了使算法簡(jiǎn)單，在裝箱前，貨物已經(jīng)按尺寸從大到小排序。35感謝你的觀看2019年5月19日算法：裝箱問題輸入:S=(s1,….,sn)，0<si≤裝箱問題的程序binpackFFd(S,n,bin){float[]used=newfloat[n+1];//used[j]是箱子j已經(jīng)使用的空間

inti,j;//used[j]初始為0，S已按降序排列s1>=S2>=…>=Sn.for(i=1;i<=n;i++){//尋找能裝下s[i]的箱子.for(j=1;j<=n;j++){if(used[j]+si<+1.0)//+1.0，每個(gè)箱子的容量都是1.0bin[i]=j;used[j]+=si;break;//裝完退出循環(huán)j,裝下一個(gè)箱子，繼續(xù)循環(huán)i.}}}36感謝你的觀看2019年5月19日裝箱問題的程序binpackFFd(S,n,bin)36感謝近似分析引理13.9:設(shè)S為算法的輸入.令opt(S)為優(yōu)化的裝箱數(shù).令i為第一個(gè)被FFD算法裝入第opt(S)+1號(hào)箱子的物品,則si<＝1/3

證明:(反證法)

假設(shè)si>1/3,則FFD算法在裝到si

時(shí),前面的箱子的不會(huì)如圖13.7的情形.產(chǎn)生的裝箱情況如圖13.8.(k≥0):k個(gè)箱子只放一個(gè)物品;opt-k個(gè)箱子放2個(gè)size>1/3的物品.

37感謝你的觀看2019年5月19日近似分析引理13.9:設(shè)S為算法的輸入.令opt(S)為優(yōu)近似分析FFD算法沒把物品k+1,…,i-1放在前k個(gè)箱子內(nèi)(放不下),這些物品的數(shù)目為2(opt-k)盡管優(yōu)化解的裝箱情況和FFD不同,但前k個(gè)物品在優(yōu)化解中也必須分放在k個(gè)箱子里:前k個(gè)物品中任2個(gè)都不能放在一個(gè)箱子內(nèi).優(yōu)化解中物品k+1,…,i-1,放在其余的opt-k個(gè)箱子內(nèi).因?yàn)檫@些物品的尺寸均>1/3.所以這些箱子中每個(gè)箱子都要放2個(gè),盡管放法和FFD不一定相同.因此si

在優(yōu)化解中無法安排,矛盾.38感謝你的觀看2019年5月19日近似分析FFD算法沒把物品k+1,…,i-1放在前k個(gè)箱子近似分析引理13.10:FFD在前opt(S)箱子裝不下的物品數(shù)量至多為opt(S)-1

反證法:如有opt(S)個(gè)物品放在多用的箱內(nèi),則有:

但其中bi為裝在第i個(gè)箱子內(nèi)物品的總量;ti為前opt箱子裝不下的物品的重量;按FFD算法后者不能裝入第i個(gè)箱子.所有bi+ti>1.定理13.11RFFD(m)<=(4/3)+(1/3m);SFFD(n)<=3/239感謝你的觀看2019年5月19日近似分析引理13.10:FFD在前opt(S)箱子裝不下的近似分析FFD至多有m-1個(gè)物品放在extra箱子內(nèi),放的物品size<=1/3,所以FFD多用的箱子數(shù)不超過更強(qiáng)的結(jié)果為RFFD(m)≤11/9+4/m對(duì)任意大的m有例子證明RFFD≥11/9,即最壞情形22％的誤差(較優(yōu)化解多用的箱數(shù))是緊上界(tightbound)40感謝你的觀看2019年5月19日近似分析FFD至多有m-1個(gè)物品放在extra箱子內(nèi),放的物BestFit,NextFitHeuristicsBestFit:尺寸s的物品放入滿足條件used[j]+s≤1,且used[j]最大的箱內(nèi)當(dāng)物品按尺寸s的非增順序排列時(shí)BestFit策略和FFD產(chǎn)生的裝箱方法差不多相同NextFit:物品不排序,所以可用于在線應(yīng)用;如果下一物品不能放入當(dāng)前使用的箱子,則使用一個(gè)新箱子NextFit至多用2opt(S)個(gè)箱子:產(chǎn)生的方案中相鄰的2個(gè)箱子裝入的物品尺寸>1.41感謝你的觀看2019年5月19日BestFit,NextFitHeuristicsB背包和子集和數(shù)問題當(dāng)所有pi=si時(shí)，背包問題轉(zhuǎn)化為子集和數(shù)的優(yōu)化問題算法13.2為上述簡(jiǎn)化的背包問題的近似算法sKnapk，類似k－優(yōu)化的背包問題的貪心算法。定理13.13RsKnapk(m)和SsKnapk(n)均<=1+1/k42感謝你的觀看2019年5月19日背包和子集和數(shù)問題當(dāng)所有pi=si時(shí)，背包問題轉(zhuǎn)化為子集和4續(xù)定理13.13證明要點(diǎn)：設(shè)T是優(yōu)化解中k個(gè)重量最大的物品構(gòu)成的子集,k-優(yōu)化算法考慮過先裝這k種物品的情形;設(shè)j是優(yōu)化解中第一個(gè)未被貪心法在這種情形加入T中的物品的下標(biāo).Opt(I)=m>=k個(gè)最重的重量之和+Sj>=(k+1)Sj,所以Sj<=m/(k+1)因Sj

被貪心法拒絕，所以Val(sKnapk(I))+Sj>C>=m,所以

Val(sKnapk(I))>m-Sj>=m-(m/(k+1))

=mk/(k+1)

r(I)=m/Val<(k+1)/k=1+1/k

43感謝你的觀看2019年5月19日續(xù)定理13.13證明要點(diǎn)：設(shè)T是優(yōu)化解中k個(gè)重量最大的物品構(gòu)圖著色算法13.3for(i=1;i≤n;i++)for(c=1;c≤n;c++){如沒有與vi

相鄰的頂點(diǎn)有著色c,對(duì)vi

著色c并break;}Fig.13.11如按先a類頂點(diǎn)后b類頂點(diǎn)著色算法13.3只需2種顏色;如交叉進(jìn)行則需k種顏色RSC(2)=∞;SSC(n)≥n/4(k=n/2,opt=2)44感謝你的觀看2019年5月19日?qǐng)D著色算法13.344感謝你的觀看2019年5月19日旅行商問題給定一個(gè)帶權(quán)重的完全圖找具有最小權(quán)重的周游路線（通過所有頂點(diǎn)的環(huán)）。45感謝你的觀看2019年5月19日旅行商問題給定一個(gè)帶權(quán)重的完全圖45感謝你的觀看2019年5旅行商問題的近似算法最近鄰居策略NearestTSP(V,E,W)

選擇任一頂點(diǎn)s作為周游路線C的起點(diǎn)

v=s;While有頂點(diǎn)不再C中:{選擇有最小權(quán)重的邊vw，其中w不在C中.

將邊vw加入C中;v=w;}

將邊vs加入C.returnC;時(shí)間復(fù)雜度t(n)=O(n2)n是頂點(diǎn)的數(shù)量46感謝你的觀看2019年5月19日旅行商問題的近似算法最近鄰居策略46感謝你的觀看2019年5續(xù)最短鏈路策略:與C中邊不構(gòu)成環(huán)路且不構(gòu)成與v或w伴隨的第3條邊(無向圖)最小權(quán)值邊(v,w)上述兩個(gè)算法都不保證產(chǎn)生優(yōu)化解，而且對(duì)其近似程度也不能給出界定理13.22設(shè)A是TSP問題的近似算法，如對(duì)任何輸入I有rA(I)<=c，則P＝NP從該定理可看出TSP的難度47感謝你的觀看2019年5月19日續(xù)最短鏈路策略:與C中邊不構(gòu)成環(huán)路且不構(gòu)成與v或w伴隨的第3DNAComputerOriginfromsimilaritywithTuring-computingCodes:(0,1)(A,T,G,C)Operator:(and,or,not)(copy,cut,paste)InitiatedbyLeonardAdlemanforsolvingHamiltonianpathproblemin1994.Increasingperformance(faster,tiny),butnotreducingthecomputationalcomplexityCapabilityHighlyparallelHugeVolumeofstorageMainbottleneckMaterials---ShapiroE,BenensonY(2006)BringingDNAComputerstoLife.ScientificAmerican,TURINGMACHINEDNAMACHINE48感謝你的觀看2019年5月19日DNAComputerOriginfromsimila49感謝你的觀看2019年5月19日49感謝你的觀看2019年5月19日QuantumComputerMotivation

Moore’sLaw:Wehitthequantumlevel2010~2020.Quantumcomputationismorepowerfulthanclassicalcomputation.Morecanbecomputedinlesstime—thecomplexityclassesaredifferent!Acomputationmodelbasedonquantumprinciplesofphysics(Thephysicaluniverseisirreduciblyrandom)StoragecapabilityConventionalbitsholdflatbinarydata(0or1)QuantumBits(Qubits)holdprobabilitiesofvalues(superposition)PowerofQuantumParallelismAsingleoperationappliestoallsuperpositionsatonceAllpossibleresultsofanoperationareretrievedShor'sAlgorithm-quantumcomputingalgorithmtoactuallyfactorlargenumbersinpolynomialtime.50感謝你的觀看2019年5月19日QuantumComputerMotivation50感謝51感謝你的觀看2019年5月19日51感謝你的觀看2019年5月19日NP-完全問題(NPCompleteProblem)

ThinkingaboutAlgorithmsAbstractlyxxx天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院52感謝你的觀看2019年5月19日NP-完全問題(NPCompleteProblem)

T主要內(nèi)容NP-完全問題：一些典型的例子NP-完全問題：相關(guān)定義近似算法兩種新的計(jì)算模型53感謝你的觀看2019年5月19日主要內(nèi)容NP-完全問題：一些典型的例子2感謝你的觀看2019NP-Complete:涵義N-NondeterministicDeterministicalgorithm:Givenaparticularinput,itwillalwaysproducethesamecorrectoutputNon-deterministicalgorithm:withoneormorechoicepointswheremultipledifferentcontinuationsarepossible,withoutanyspecificationofwhichonewillbetakenP-Polynomial(time)ComputablePolynomialtimeisassumedthelowestcomplexityCompleteReducible輸入/輸出算法復(fù)雜性變換/封閉性54感謝你的觀看2019年5月19日NP-Complete:涵義N-NondeterminisNP-C:典型的問題（1）問題1圖著色問題判定問題：是否存在不超過k種顏色的著色方案?優(yōu)化問題：求圖的最小著色數(shù)和著色方案問題2作業(yè)調(diào)度問題判定問題：是否存在罰款額不超過k的作業(yè)調(diào)度?優(yōu)化問題：求最小罰款額調(diào)度55感謝你的觀看2019年5月19日NP-C:典型的問題（1）問題1圖著色問題4感謝你的觀看NP-C:典型的問題（2）問題3Binpacking問題：假設(shè)有n種物品，它們的尺寸分別為s1,…,sn，0<si≤1另有任意多個(gè)箱子(Bins)，箱子的容量為1，判定問題：任意給定k，是否存在一種裝箱方法使用的箱子數(shù)≤k？?jī)?yōu)化問題：求使用最小箱數(shù)的裝箱方法56感謝你的觀看2019年5月19日NP-C:典型的問題（2）問題3Binpacking問NP-C:典型的問題（3）問題4背包問題判定問題：是否存在效益值至少為k的可行子集?優(yōu)化問題問題5子集和數(shù)問題s1,s2,┅,sn,C判定問題：是否存在和數(shù)等于C的子集?優(yōu)化問題：求≤C的最大子集和數(shù).可歸約為背包問題:pi=wi.57感謝你的觀看2019年5月19日NP-C:典型的問題（3）問題4背包問題6感謝你的觀看2NP-C:典型的問題（3）問題6CNF(合取范式)-可滿足問題(SAT)判定問題：是否存在真假賦值使得該CNF為真.合取范式例:問題7Hamiltonian回路判定問題問題8TSP(旅行商)問題判定問題：任意給定一整數(shù)k，是否存在一長(zhǎng)度不超過k的Hamiltonian回路？?jī)?yōu)化問題58感謝你的觀看2019年5月19日NP-C:典型的問題（3）問題6CNF(合取范式)-可滿NP-C:典型的問題（4）問題9:節(jié)點(diǎn)覆蓋:無向圖中的每一條邊都被某些節(jié)點(diǎn)關(guān)聯(lián)判定問題：給定無向圖G和正整數(shù)k,是否存在一k節(jié)點(diǎn)覆蓋.優(yōu)化問題：最小節(jié)點(diǎn)覆蓋問題10:給定一無向圖G,k-獨(dú)立集;最大獨(dú)立集.問題11:給定一無向圖G,k-集團(tuán);最大集團(tuán).問題10和11可互相轉(zhuǎn)化:邊互補(bǔ)圖目標(biāo)函數(shù)取整數(shù)值時(shí),優(yōu)化值問題和判定問題等價(jià)我們可用二分查找從判定問題解得到優(yōu)化值的問題的解59感謝你的觀看2019年5月19日NP-C:典型的問題（4）問題9:節(jié)點(diǎn)覆蓋:無向圖中的每一條類P與類NP（ClassP&ClassNP）60感謝你的觀看2019年5月19日類P與類NP9感謝你的觀看2019年5月19日類P(1)算法輸入為問題實(shí)例的二進(jìn)制編碼.定義該0/1字符串的長(zhǎng)度為輸入長(zhǎng)度.例如n個(gè)節(jié)點(diǎn)和m條邊的圖的長(zhǎng)度為Θ(mlogn)(見圖13.1).多項(xiàng)式界:如一算法的最壞情形時(shí)間復(fù)雜度T(n)=O(p(n)),其中p(n)為輸入長(zhǎng)度n的多項(xiàng)式,則稱該算法有多項(xiàng)式界.如一個(gè)問題有多項(xiàng)式界的算法,則稱該問題有多項(xiàng)式界.61感謝你的觀看2019年5月19日類P(1)算法輸入為問題實(shí)例的二進(jìn)制編碼.定義該0/1字符類P(2)類P的定義一個(gè)算法解決判定問題指:對(duì)該判定問題的yes實(shí)例,算法要停機(jī)并給出yes回答.對(duì)no實(shí)例算法要停機(jī)并給出no的回答.具有多項(xiàng)式界的判定問題組成的類稱為類P.多項(xiàng)式的相加,相乘及復(fù)合仍為多項(xiàng)式;所以一個(gè)有多項(xiàng)式界的算法調(diào)用另一有多項(xiàng)式界的算法構(gòu)成的算法仍有多項(xiàng)式界.62感謝你的觀看2019年5月19日類P(2)類P的定義11感謝你的觀看2019年5月19日類NPNon-deterministic--不確定的算法：對(duì)給定輸入字符串w,1.Guessing

不確定地寫一個(gè)稱為”certificate”(guessed解)的字符串c.c實(shí)際上是可行解的一種表示;例如,表示背包問題的n元組,表示圖的字符串或鄰接矩陣.2.checking

使用一確定的有多項(xiàng)式界的算法驗(yàn)證c是否為問題的答案.如果是給出yes,反之,不回答.Polynomial--多項(xiàng)式界:寫c和驗(yàn)證的時(shí)間為O(q(|w|)),q()為某一多項(xiàng)式,w為輸入長(zhǎng)度.63感謝你的觀看2019年5月19日類NPNon-deterministic--不確定的算法：對(duì)不確定的算法:偽代碼VoidnondetA(Stringinput)

Strings=genCertif();

booleancheckOK=verifyA(input,s)

if(checkOK)Output“yes“

returnchecOK為false時(shí)不作反應(yīng).64感謝你的觀看2019年5月19日不確定的算法:偽代碼VoidnondetA(String類NP：幾點(diǎn)說明“不確定”指:對(duì)同一輸入w,算法使用任意多個(gè)不同的c,進(jìn)行驗(yàn)證.對(duì)不同c的這些計(jì)算,可以看作是同時(shí)進(jìn)行的.一個(gè)不確定算法解決判定問題指:對(duì)輸入w,如果它有解,不確定算法一定會(huì)寫出一個(gè)c,使得驗(yàn)證階段能通過,并返回一個(gè)yes回答.如果一個(gè)判定問題有不確定的多項(xiàng)式界的算法則稱它屬于類NP.65感謝你的觀看2019年5月19日類NP：幾點(diǎn)說明“不確定”指:對(duì)同一輸入w,算法使用任意圖著色問題Input:(著色數(shù))k,(節(jié)點(diǎn)數(shù))5,(圖的邊)(1,2)(1,4)...Guessing指寫出長(zhǎng)度為n(節(jié)點(diǎn)數(shù))的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$@等.至少有kn個(gè)“guessings”.Checking指檢查一guessed字符串是否合法及是否是一個(gè)k-著色.如果寫字符串的時(shí)間是O(p1(n)),checking時(shí)間是O(p2(n));而且p1(n),p2(n)是n的多項(xiàng)式(從而也是輸入長(zhǎng)度的多項(xiàng)式),則該不確定算法有多項(xiàng)式界.如果輸入的圖能k著色則不確定算法停機(jī)并給出yes回答.3124566感謝你的觀看2019年5月19日?qǐng)D著色問題Input:(著色數(shù))k,(節(jié)點(diǎn)數(shù))5,(P=NP?類NP：由不確定的多項(xiàng)式界算法的判定問題構(gòu)成的類稱為類NP。P=NP?是計(jì)算機(jī)科學(xué)中最大的問題之一67感謝你的觀看2019年5月19日P=NP?類NP：由不確定的多項(xiàng)式界算法的判定問題構(gòu)成的類稱輸入尺寸（thesizeofinput）(1)是否存在j,k>1使得n=jk?即n是否為一合數(shù)?factor=0;

for(j=2;j<n;j++)

if((nmodj)==0)factor=j;

break;

returnfactor(nmodj)計(jì)算時(shí)間為Θ(log2n)(bit級(jí)運(yùn)算).算法的復(fù)雜度為Θ(nlog2n).但n是輸入長(zhǎng)度m=log2n的指數(shù)函數(shù).所以它是指數(shù)復(fù)雜度算法.ManindraAgrawal等證明了:”n是否為一素?cái)?shù)?”

屬于PManindraAgrawal,NeerajKayal,NitinSaxena,"PRIMESisinP",AnnalsofMathematics160(2004),no.2,pp.781–793.68感謝你的觀看2019年5月19日輸入尺寸（thesizeofinput）(1)是否Thesizeofinput(2)背包問題輸入長(zhǎng)度m為

m=Θ(log2n+log2c+Σlog2pi+Σlog2wi)假定pi=O(c)wi=O(c),則m=O(nlog2c)Θ(nc)不能以m的多項(xiàng)式加以限界,即

nc=O(mk)

不成立,因?yàn)閚c/(nlog2c)k→∞(c→∞),對(duì)所有常數(shù)k.除了涉及數(shù)的計(jì)算外,以前我們分析的多項(xiàng)式復(fù)雜度算法,在以字符串為輸入時(shí),仍是多項(xiàng)式復(fù)雜度算法.69感謝你的觀看2019年5月19日Thesizeofinput(2)背包問題輸入長(zhǎng)度m多項(xiàng)式約化問題P可多項(xiàng)式地約化為問題Q,如果存在一個(gè)有多項(xiàng)式界的確定性算法T,使得：對(duì)每個(gè)輸入字符串x,T產(chǎn)生一字符串T(x).x是P的合法輸入且P對(duì)x有yes答案當(dāng)且僅當(dāng)T(x)是Q的合法輸入且有yes答案證明多項(xiàng)式約化關(guān)鍵在“當(dāng)且僅當(dāng)”問題P可多項(xiàng)式地約化為Q,表示為：PpQTxT(x)PYes/noanswerQ70感謝你的觀看2019年5月19日多項(xiàng)式約化問題P可多項(xiàng)式地約化為問題Q,如果TxT(x)多項(xiàng)式約化定理13.3IfPpQ且Q在P中則P也在P中存在解Q的算法有多項(xiàng)式界q,設(shè)T的復(fù)雜度為多項(xiàng)式p.則T(x)的長(zhǎng)度O(p(|x|))對(duì)輸入T(x)所需時(shí)間為O(q(p(|x|)))解P的復(fù)雜度為O(p(|x|)+q(p(|x|)))可約化的意義:Q至少和P一樣“難”約化關(guān)系有傳遞性71感謝你的觀看2019年5月19日多項(xiàng)式約化定理13.3IfPpQ且Q在P中則P也在P子集和數(shù)可約化為調(diào)度問題多項(xiàng)式變換子集和數(shù)問題的實(shí)例:s1,s2,┅,sn,C;假定S=∑1≤i≤nsi>C對(duì)應(yīng)調(diào)度問題實(shí)例

pi=ti=si,di=C,k=S-Cif部分:子集和數(shù)有解則調(diào)度問題有解onlyif:假定上述調(diào)度問題有罰款額≤k的解該可行調(diào)度的執(zhí)行時(shí)間ti之和≤C(可行性)又因ti=pi=si,所以該可行調(diào)度對(duì)應(yīng)罰款額=S-Σpi=S-Σti≥S-C=k所以其罰款額＝k，而且被調(diào)度的作業(yè)的時(shí)間之和＝C72感謝你的觀看2019年5月19日子集和數(shù)可約化為調(diào)度問題多項(xiàng)式變換21感謝你的觀看2019年NP-難度和NP-完全問題問題Q是NP-難度問題，如果：每個(gè)NP問題都可多項(xiàng)式地約化為問題Q.問題Q是NP-完全問題.如果:它是NP問題,同時(shí)它還是NP-難度問題.NP-完全問題的性質(zhì)所有NP-完全問題,相對(duì)于多項(xiàng)式約化關(guān)系,是自反,對(duì)稱,傳遞的,即構(gòu)成一個(gè)閉類.如果能找到一個(gè)NP完全問題的多項(xiàng)式算法則P=NP有NP-難度問題但不知它是否在NP類內(nèi)(第kth重子集問題)73感謝你的觀看2019年5月19日NP-難度和NP-完全問題問題Q是NP-難度問題，如果：22Problems-unknowninNPKth重子集問題:任給定n+2個(gè)正整數(shù)c1,┅cn,k,L;是否存在{1,2,┅,n}的k個(gè)不同子集S1,┅Sk

使得對(duì)所有i=1,┅,k有Σ部分稱為子集的重量,重量排序第k的子集.當(dāng)k=2n-1時(shí),表示可行解的字符串的長(zhǎng)度有指數(shù)的長(zhǎng)度.我們不知道該問題是否在NP中.圖G的最大集團(tuán)的節(jié)點(diǎn)數(shù)是否=k?上述問題是否在NP?也是未知的!(驗(yàn)證最大集團(tuán),不能在多項(xiàng)式時(shí)間內(nèi)做到)74感謝你的觀看2019年5月19日Problems-unknowninNPKth重子集問題CNF-satisfiablity問題是NP-完全問題定理13.5CNF-satisfiablity問題是NP-完全問題這是著名的Cook定理Cook定理的推論:如果CNF-可滿足問題有多項(xiàng)式界的算法，則P=NP.75感謝你的觀看2019年5月19日CNF-satisfiablity問題是NP-完全問題定理1NP-完全問題證明證明問題Q是NP-完全問題的步驟：

(1)選擇一已知的NP-完全問題P。(2)證明P可多項(xiàng)式的約化為Q背包問題屬于NP＝>子集和數(shù)屬于NP子集和數(shù)問題屬于NP＝>調(diào)度問題屬于NP不計(jì)其數(shù)的這種推導(dǎo).76感謝你的觀看2019年5月19日NP-完全問題證明證明問題Q是NP-完全問題的步驟：25感謝ListsofNP-CompleteproblemsBooleansatisfiabilityproblem(SAT)N-puzzle

Knapsackproblem

Hamiltonianpathproblem

Travelingsalesmanproblem

Subgraphisomorphismproblem

Subsetsumproblem

Cliqueproblem

Vertexcoverproblem

Independentsetproblem

Graphcoloringproblem

77感謝你的觀看2019年5月19日ListsofNP-CompleteproblemsWhatmakesaproblemhard(1)限定問題的一般性（問題的附加限制）實(shí)際應(yīng)用中有特殊性,有可能找到多項(xiàng)式算法例：Hamiltonian回路頂點(diǎn)度<=2時(shí)，Hamiltonian回路問題有多項(xiàng)式算法工程中有靈活性,以某種方式優(yōu)化是NP-難度問題;但以另一方式提出問題可能不是(優(yōu)化標(biāo)準(zhǔn))了解“難問題”的特點(diǎn)78感謝你的觀看2019年5月19日Whatmakesaproblemhard(1)限定Whatmakesaproblemhard(2)3-滿足問題仍為NP-完全問題,但2-滿足問題有多項(xiàng)式算法集團(tuán)問題,當(dāng)頂點(diǎn)度<=常數(shù)d時(shí)屬于類P平面圖集團(tuán)問題屬于類P，因?yàn)槠矫鎴D至多有4-集團(tuán)實(shí)際有意義的做法是提出合理的限制條件和求近似解,研究啟發(fā)式算法.79感謝你的觀看2019年5月19日Whatmakesaproblemhard(2)3-優(yōu)化問題和判定問題3種問題判定問題求優(yōu)化值問題求優(yōu)化解問題優(yōu)化問題至少與判定問題一樣“難”優(yōu)化值問題有多項(xiàng)式算法，則判定問題有多項(xiàng)式算法多數(shù)情況下，如果能在多項(xiàng)式時(shí)間內(nèi)求解決策問題，那么也能在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)值（圖著色問題）；有時(shí)則不能（TSP）80感謝你的觀看2019年5月19日優(yōu)化問題和判定問題3種問題29感謝你的觀看2019年5月19近似算法（1）返回次優(yōu)解的算法。這種算法經(jīng)?？梢酝ㄟ^啟發(fā)式方法得到，例如：貪心法。近似算法必須是多項(xiàng)式時(shí)間算法。為量度近似解對(duì)優(yōu)化解的近似程度定義以下術(shù)語FS(I)是輸入I的可行解集。Val(I,x):實(shí)例I的可行解x的目標(biāo)函數(shù)值opt(I):實(shí)例I的優(yōu)化解的值81感謝你的觀看2019年5月19日近似算法（1）返回次優(yōu)解的算法。這種算法經(jīng)?？梢酝ㄟ^啟發(fā)式方近似算法（2）設(shè)A為一近似算法,令A(yù)(I)為輸入I時(shí)該算法輸出的可行解極小化和極大化問題度量近似性能的指標(biāo)rA(I)82感謝你的觀看2019年5月19日近似算法（2）設(shè)A為一近似算法,令A(yù)(I)為輸入I時(shí)該算法輸續(xù)式(13.5)定義的RA(m)為最壞情形rA(I)的值,是與輸入I無關(guān)的指標(biāo):在固定優(yōu)化值m下求最壞情形的比值式(13.6)定義的SA(n)也是一與輸入獨(dú)立的指標(biāo)83感謝你的觀看2019年5月19日續(xù)式(13.5)定義的RA(m)為最壞情形rA(I)的值,是Bin-Packing的近似算法怎么裝不同大小、不同形狀的貨物才能使占用的箱子數(shù)最少。該問題形式化如下：裝箱問題設(shè)S=(s1,…,sn)0<si<=1，1<=i<=n將s1,…,sn

裝入盡可能少的箱子里。假定每個(gè)箱子都有容量1。裝箱問題是NP-難度問題搜索算法有指數(shù)的復(fù)雜度：須試所有可能的S的分劃。84感謝你的觀看2019年5月19日Bin-Packing的近似算法怎么裝不同大小、不同形狀的貨裝箱問題：FFD算法（貪心法）將物品按尺寸遞減排序，箱子從左到右排列并盡可能放在前面的箱子里。算法的時(shí)間復(fù)雜度t(n)=(n2)85感謝你的觀看2019年5月19日裝箱問題：FFD算法（貪心法）將物品按尺寸遞減排序，箱子從左算法：裝箱問題輸入:S=(s1,….,sn)，0<si≤1，1≤i≤n.S代表貨物1,...,n的尺寸，每個(gè)箱子的容量都是1.0。輸出:bin[i]是放物品i的箱子號(hào),1≤i≤n.為了使算法簡(jiǎn)單，在裝箱前，貨物已經(jīng)按尺寸從大到小排序。86感謝你的觀看2019年5月19日算法：裝箱問題輸入:S=(s1,….,sn)，0<si≤裝箱問題的程序binpackFFd(S,n,bin){float[]used=newfloat[n+1];//used[j]是箱子j已經(jīng)使用的空間

inti,j;//used[j]初始為0，S已按降序排列s1>=S2>=…>=Sn.for(i=1;i<=n;i++){//尋找能裝下s[i]的箱子.for(j=1;j<=n;j++){if(used[j]+si<+1.0)//+1.0，每個(gè)箱子的容量都是1.0bin[i]=j;used[j]+=si;break;//裝完退出循環(huán)j,裝下一個(gè)箱子，繼續(xù)循環(huán)i.}}}87感謝你的觀看2019年5月19日裝箱問題的程序binpackFFd(S,n,bin)36感謝近似分析引理13.9:設(shè)S為算法的輸入.令opt(S)為優(yōu)化的裝箱數(shù).令i為第一個(gè)被FFD算法裝入第opt(S)+1號(hào)箱子的物品,則si<＝1/3

證明:(反證法)

假設(shè)si>1/3,則FFD算法在裝到si

時(shí),前面的箱子的不會(huì)如圖13.7的情形.產(chǎn)生的裝箱情況如圖13.8.(k≥0):k個(gè)箱子只放一個(gè)物品;opt-k個(gè)箱子放2個(gè)size>1/3的物品.

88感謝你的觀看2019年5月19日近似分析引理13.9:設(shè)S為算法的輸入.令opt(S)為優(yōu)近似分析FFD算法沒把物品k+1,…,i-1放在前k個(gè)箱子內(nèi)(放不下),這些物品的數(shù)目為2(opt-k)盡管優(yōu)化解的裝箱情況和FFD不同,但前k個(gè)物品在優(yōu)化解中也必須分放在k個(gè)箱子里:前k個(gè)物品中任2個(gè)都不能放在一個(gè)箱子內(nèi).優(yōu)化解中物品k+1,…,i-1,放在其余的opt-k個(gè)箱子內(nèi).因?yàn)檫@些物品的尺寸均>1/3.所以這些箱子中每個(gè)箱子都要放2個(gè),盡管放法和FFD不一定相同.因此si

在優(yōu)化解中無法安排,矛盾.89感謝你的觀看2019年5月19日近似分析FFD算法沒把物品k+1,…,i-1放在前k個(gè)箱子近似分析引理13.10:FFD在前opt(S)箱子裝不下的物品數(shù)量至多為opt(S)-1

反證法:如有opt(S)個(gè)物品放在多用的箱內(nèi),則有:

但其中bi為裝在第i個(gè)箱子內(nèi)物品的總量;ti為前opt箱子裝不下的物品的重量;按FFD算法后者不能裝入第i個(gè)箱子.所有bi+ti>1.定理13.11RFFD(m)<=(4/3)+(1/3m);SFFD(n)<=3/290感謝你的觀看2019年5月19日近似分析引理13.10:FFD在前opt(S)箱子裝不下的近似分析FFD至多有m-1個(gè)物品放在extra箱子內(nèi),放的物品size<=1/3,所以FFD多用的箱子數(shù)不超過更強(qiáng)的結(jié)果為RFFD(m)≤11/9+4/m對(duì)任意大的m有例子證明RFFD≥11/9,即最壞情形22％的誤差(較優(yōu)化解多用的箱數(shù))是緊上界(tightbound)91感謝你的觀看2019年5月19日近似分析FFD至多有m-1個(gè)物品放在extra箱子內(nèi),放的物BestFit,NextFitHeuristicsBestFit:尺寸s的物品放入滿足條件used[j]+s≤1,且used[j]最大的箱內(nèi)當(dāng)物品按尺寸s的非增順序排列時(shí)BestFit策略和FFD產(chǎn)生的裝箱方法差不多相同NextFit:物品不排序,所以可用于在線應(yīng)用;如果下一物品不能放入當(dāng)前使用的箱子,則使用一個(gè)新箱子NextFit至多用2opt(S)個(gè)箱子:產(chǎn)生的方案中相鄰的2個(gè)箱子裝入的物品尺寸>1.92感謝你的觀看2019年5月19日BestFit,NextFitHeuristicsB背包和子集和數(shù)問題當(dāng)所有pi=si時(shí)，背包問題轉(zhuǎn)化為子集和數(shù)的優(yōu)化問題算法13.2為上述簡(jiǎn)化的背包問題的近似算法sKnapk，類似k－優(yōu)化的背包問題的貪心算法。定理13.13RsKnapk(m)和SsKnapk(n)均<=1+1/k93感謝