NP-完全問題(NPCompleteProblem)

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

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

使用一確定的有多項式界的算法驗證c是否為問題的答案.如果是給出yes,反之,不回答.Polynomial--多項式界:寫c和驗證的時間為O(q(|w|)),q()為某一多項式,w為輸入長度.不確定的算法:偽代碼VoidnondetA(Stringinput)

Strings=genCertif();

booleancheckOK=verifyA(input,s)

if(checkOK)Output“yes“

returnchecOK為false時不作反應.類NP：幾點說明“不確定”指:對同一輸入w,算法使用任意多個不同的c,進行驗證.對不同c的這些計算,可以看作是同時進行的.一個不確定算法解決判定問題指:對輸入w,如果它有解,不確定算法一定會寫出一個c,使得驗證階段能通過,并返回一個yes回答.如果一個判定問題有不確定的多項式界的算法則稱它屬于類NP.圖著色問題Input:(著色數)k,(節點數)5,(圖的邊)(1,2)(1,4)...Guessing指寫出長度為n(節點數)的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$@等.至少有kn個“guessings”.Checking指檢查一guessed字符串是否合法及是否是一個k-著色.如果寫字符串的時間是O(p1(n)),checking時間是O(p2(n));而且p1(n),p2(n)是n的多項式(從而也是輸入長度的多項式),則該不確定算法有多項式界.如果輸入的圖能k著色則不確定算法停機并給出yes回答.31245P=NP?類NP：由不確定的多項式界算法的判定問題構成的類稱為類NP。P=NP?是計算機科學中最大的問題之一輸入尺寸（thesizeofinput）(1)是否存在j,k>1使得n=jk?即n是否為一合數?factor=0;

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

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

break;

returnfactor(nmodj)計算時間為Θ(log2n)(bit級運算).算法的復雜度為Θ(nlog2n).但n是輸入長度m=log2n的指數函數.所以它是指數復雜度算法.ManindraAgrawal等證明了:”n是否為一素數?”

屬于PManindraAgrawal,NeerajKayal,NitinSaxena,"PRIMESisinP",AnnalsofMathematics160(2004),no.2,pp.781–793.Thesizeofinput(2)背包問題輸入長度m為

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

nc=O(mk)

不成立,因為nc/(nlog2c)k→∞(c→∞),對所有常數k.除了涉及數的計算外,以前我們分析的多項式復雜度算法,在以字符串為輸入時,仍是多項式復雜度算法.多項式約化問題P可多項式地約化為問題Q,如果存在一個有多項式界的確定性算法T,使得：對每個輸入字符串x,T產生一字符串T(x).x是P的合法輸入且P對x有yes答案當且僅當T(x)是Q的合法輸入且有yes答案證明多項式約化關鍵在“當且僅當”問題P可多項式地約化為Q,表示為：P

pQTxT(x)PYes/noanswerQ多項式約化定理13.3IfP

pQ且Q在P中則P也在P中存在解Q的算法有多項式界q,設T的復雜度為多項式p.則T(x)的長度O(p(|x|))對輸入T(x)所需時間為O(q(p(|x|)))解P的復雜度為O(p(|x|)+q(p(|x|)))可約化的意義:Q至少和P一樣“難”約化關系有傳遞性子集和數可約化為調度問題多項式變換子集和數問題的實例:s1,s2,┅,sn,C;假定S=∑1≤i≤nsi>C對應調度問題實例

pi=ti=si,di=C,k=S-Cif部分:子集和數有解則調度問題有解onlyif:假定上述調度問題有罰款額≤k的解該可行調度的執行時間ti之和≤C(可行性)又因ti=pi=si,所以該可行調度對應罰款額=S-Σpi=S-Σti≥S-C=k所以其罰款額＝k，而且被調度的作業的時間之和＝CNP-難度和NP-完全問題問題Q是NP-難度問題，如果：每個NP問題都可多項式地約化為問題Q.問題Q是NP-完全問題.如果:它是NP問題,同時它還是NP-難度問題.NP-完全問題的性質所有NP-完全問題,相對于多項式約化關系,是自反,對稱,傳遞的,即構成一個閉類.如果能找到一個NP完全問題的多項式算法則P=NP有NP-難度問題但不知它是否在NP類內(第kth重子集問題)Problems-unknowninNPKth重子集問題:任給定n+2個正整數c1,┅cn,k,L;是否存在{1,2,┅,n}的k個不同子集S1,┅Sk

使得對所有i=1,┅,k有Σ部分稱為子集的重量,重量排序第k的子集.當k=2n-1時,表示可行解的字符串的長度有指數的長度.我們不知道該問題是否在NP中.圖G的最大集團的節點數是否=k?上述問題是否在NP?也是未知的!(驗證最大集團,不能在多項式時間內做到)CNF-satisfiablity問題是NP-完全問題定理13.5CNF-satisfiablity問題是NP-完全問題這是著名的Cook定理Cook定理的推論:如果CNF-可滿足問題有多項式界的算法，則P=NP.NP-完全問題證明證明問題Q是NP-完全問題的步驟：

(1)選擇一已知的NP-完全問題P。(2)證明P可多項式的約化為Q背包問題屬于NP＝>子集和數屬于NP子集和數問題屬于NP＝>調度問題屬于NP不計其數的這種推導.ListsofNP-CompleteproblemsBooleansatisfiabilityproblem(SAT)N-puzzle

Knapsackproblem

Hamiltonianpathproblem

Travelingsalesmanproblem

Subgraphisomorphismproblem

Subsetsumproblem

Cliqueproblem

Vertexcoverproblem

Independentsetproblem

Graphcoloringproblem

Whatmakesaproblemhard(1)限定問題的一般性（問題的附加限制）實際應用中有特殊性,有可能找到多項式算法例：Hamiltonian回路頂點度<=2時，Hamiltonian回路問題有多項式算法工程中有靈活性,以某種方式優化是NP-難度問題;但以另一方式提出問題可能不是(優化標準)了解“難問題”的特點Whatmakesaproblemhard(2)3-滿足問題仍為NP-完全問題,但2-滿足問題有多項式算法集團問題,當頂點度<=常數d時屬于類P平面圖集團問題屬于類P，因為平面圖至多有4-集團實際有意義的做法是提出合理的限制條件和求近似解,研究啟發式算法.優化問題和判定問題3種問題判定問題求優化值問題求優化解問題優化問題至少與判定問題一樣“難”優化值問題有多項式算法，則判定問題有多項式算法多數情況下，如果能在多項式時間內求解決策問題，那么也能在多項式時間內獲得最優值（圖著色問題）；有時則不能（TSP）近似算法（1）返回次優解的算法。這種算法經常可以通過啟發式方法得到，例如：貪心法。近似算法必須是多項式時間算法。為量度近似解對優化解的近似程度定義以下術語FS(I)是輸入I的可行解集。Val(I,x):實例I的可行解x的目標函數值opt(I):實例I的優化解的值近似算法（2）設A為一近似算法,令A(I)為輸入I時該算法輸出的可行解極小化和極大化問題度量近似性能的指標rA(I)續式(13.5)定義的RA(m)為最壞情形rA(I)的值,是與輸入I無關的指標:在固定優化值m下求最壞情形的比值式(13.6)定義的SA(n)也是一與輸入獨立的指標Bin-Packing的近似算法怎么裝不同大小、不同形狀的貨物才能使占用的箱子數最少。該問題形式化如下：裝箱問題設S=(s1,…,sn)0<si<=1，1<=i<=n將s1,…,sn

裝入盡可能少的箱子里。假定每個箱子都有容量1。裝箱問題是NP-難度問題搜索算法有指數的復雜度：須試所有可能的S的分劃。裝箱問題：FFD算法（貪心法）將物品按尺寸遞減排序，箱子從左到右排列并盡可能放在前面的箱子里。算法的時間復雜度t(n)=

(n2)算法：裝箱問題輸入:S=(s1,….,sn)，0<si≤1，1≤i≤n.S代表貨物1,...,n的尺寸，每個箱子的容量都是1.0。輸出:bin[i]是放物品i的箱子號,1≤i≤n.為了使算法簡單，在裝箱前，貨物已經按尺寸從大到小排序。裝箱問題的程序binpackFFd(S,n,bin){float[]used=newfloat[n+1];//used[j]是箱子j已經使用的空間

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，每個箱子的容量都是1.0bin[i]=j;used[j]+=si;break;//裝完退出循環j,裝下一個箱子，繼續循環i.}}}近似分析引理13.9:設S為算法的輸入.令opt(S)為優化的裝箱數.令i為第一個被FFD算法裝入第opt(S)+1號箱子的物品,則si<＝1/3

證明:(反證法)

假設si>1/3,則FFD算法在裝到si

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

近似分析FFD算法沒把物品k+1,…,i-1放在前k個箱子內(放不下),這些物品的數目為2(opt-k)盡管優化解的裝箱情況和FFD不同,但前k個物品在優化解中也必須分放在k個箱子里:前k個物品中任2個都不能放在一個箱子內.優化解中物品k+1,…,i-1,放在其余的opt-k個箱子內.因為這些物品的尺寸均>1/3.所以這些箱子中每個箱子都要放2個,盡管放法和FFD不一定相同.因此si

在優化解中無法安排,矛盾.近似分析引理13.10:FFD在前opt(S)箱子裝不下的物品數量至多為opt(S)-1

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

但其中bi為裝在第i個箱子內物品的總量;ti為前opt箱子裝不下的物品的重量;按FFD算法后者不能裝入第i個箱子.所有bi+ti>1.定理13.11RFFD(m)<=(4/3)+(1/3m);SFFD(n)<=3/2近似分析FFD至多有m-1個物品放在extra箱子內,放的物品size<=1/3,所以FFD多用的箱子數不超過更強的結果為RFFD(m)≤11/9+4/m對任意大的m有例子證明RFFD≥11/9,即最壞情形22％的誤差(較優化解多用的箱數)是緊上界(tightbound)BestFit,NextFitHeuristicsBestFit:尺寸s的物品放入滿足條件used[j]+s≤1,且used[j]最大的箱內當物品按尺寸s的非增順序排列時BestFit策略和FFD產生的裝箱方法差不多相同NextFit:物品不排序,所以可用于在線應用;如果下一物品不能放入當前使用的箱子,則使用一個新箱子NextFit至多用2opt(S)個箱子:產生的方案中相鄰的2個箱子裝入的物品尺寸>1.背包和子集和數問題當所有pi=si時，背包問題轉化為子集和數的優化問題算法13.2為上述簡化的背包問題的近似算法sKnapk，類似k－優化的背包問題的貪心算法。定理13.13RsKnapk(m)和SsKnapk(n)均<=1+1/k續定理13.13證明要點：設T是優化解中k個重量最大的物品構成的子集,k-優化算法考慮過先裝這k種物品的情形;設j是優化解中第一個未被貪心法在這種情形加入T中的物品的下標.Opt(I)=m>=k個最重的重量之和+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

圖著色算法13.3for(i=1;i≤n;i++)for(c=1;c≤n;c++){如沒有與vi

相鄰的頂點有著色c,對vi

著色c并break;}Fig.13.11如按先a類頂點后b類頂點著色算法13.3只需2種顏色;如交叉進行則需k種顏色RSC(2)=∞;SSC(n)≥n/4(k=n/2,opt=2)旅行商問題給定一個帶權重的完全圖找具有最小權重的周游路線（通過所有頂點的環）。旅行商問題的近似算法最近鄰居策略NearestTSP(V,E,W)

選擇任一頂點s作為周游路線C的起點

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

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

將邊vs加入C.returnC;時間復雜度t(n)=O(n2)n是頂點的數量續最短鏈路策略:與C中邊不構成環路且不構成與v或w伴隨的第3條邊(無向圖)最小權值邊(v,w)上述兩個算法都不保證產生優化解，而且對其近似程度也不能給出界定理13.22設A是TSP問題的近似算法，如對任何輸入I有rA(I)<=c，則P＝NP從該定理可看出TSP的難度DNAComputerOriginfromsimilaritywithTuring-computingCodes:(0,1)(A,T,G,C)Operator:(and,or,