NP-完全問題(NP

《NP-完全問題(NP》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、NP-完全問題(NPCompleteProblem)ThinkingaboutAlgorithmsAbstractly宮秀軍天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院gongxj@tju.edu.cn主要內(nèi)容NP-完全問題：一些典型的例子NP-完全問題：相關(guān)定義近似算法兩種新的計(jì)算模型NP-Complete:涵義N-NondeterministicDeterministicalgorithm:Givenaparticularinput,itwillalwaysproducethesamecorrectoutputNon-deterministic

2、algorithm:withoneormorechoicepointswheremultipledifferentcontinuationsarepossible,withoutanyspecificationofwhichonewillbetakenP-Polynomial(time)ComputablePolynomialtimeisassumedthelowestcomplexityCompleteReducible輸入/輸出算法復(fù)雜性變換/封閉性NP-C:典型的問題（1）問題1圖著色問題判定問題：是否存在不超過k種顏色的著色方

3、案?優(yōu)化問題：求圖的最小著色數(shù)和著色方案問題2作業(yè)調(diào)度問題判定問題：是否存在罰款額不超過k的作業(yè)調(diào)度?優(yōu)化問題：求最小罰款額調(diào)度NP-C:典型的問題（2）問題3Binpacking問題：假設(shè)有n種物品，它們的尺寸分別為s1,…,sn，0

4、數(shù)等于C的子集?優(yōu)化問題：求≤C的最大子集和數(shù).可歸約為背包問題:pi=wi.NP-C:典型的問題（3）問題6CNF(合取范式)-可滿足問題(SAT)判定問題：是否存在真假賦值使得該CNF為真.合取范式例:問題7Hamiltonian回路判定問題問題8TSP(旅行商)問題判定問題：任意給定一整數(shù)k，是否存在一長(zhǎng)度不超過k的Hamiltonian回路？?jī)?yōu)化問題NP-C:典型的問題（4）問題9:節(jié)點(diǎn)覆蓋:無(wú)向圖中的每一條邊都被某些節(jié)點(diǎn)關(guān)聯(lián)判定問題：給定無(wú)向圖G和正整數(shù)k,是否存在一k節(jié)點(diǎn)覆蓋.優(yōu)化問題：最小節(jié)點(diǎn)覆蓋問題10:給定一無(wú)向圖G

5、,k-獨(dú)立集;最大獨(dú)立集.問題11:給定一無(wú)向圖G,k-集團(tuán);最大集團(tuán).問題10和11可互相轉(zhuǎn)化:邊互補(bǔ)圖目標(biāo)函數(shù)取整數(shù)值時(shí),優(yōu)化值問題和判定問題等價(jià)我們可用二分查找從判定問題解得到優(yōu)化值的問題的解類P與類NP（ClassP&ClassNP）類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)式界的算法,則稱該

6、問題有多項(xiàng)式界.類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)式界.類NPNon-deterministic--不確定的算法：對(duì)給定輸入字符串w,1.Guessing不確定地寫一個(gè)稱為”certificate”(guessed解)的字符串c.c實(shí)際上是可行解的一種表示;例如,表示背包問題的n元組,表示圖的字

7、符串或鄰接矩陣.2.checking使用一確定的有多項(xiàng)式界的算法驗(yàn)證c是否為問題的答案.如果是給出yes,反之,不回答.Polynomial--多項(xiàng)式界:寫c和驗(yàn)證的時(shí)間為O(q(

8、w

9、)),q()為某一多項(xiàng)式,w為輸入長(zhǎng)度.不確定的算法:偽代碼VoidnondetA(Stringinput)Strings=genCertif();booleancheckOK=verifyA(input,s)if(checkOK)Output“yes“returnchecOK為false時(shí)不作反應(yīng).類NP：幾點(diǎn)說明“不確定”指:對(duì)同一輸入w,算法使用

10、任意多個(gè)不同的c,進(jìn)行驗(yàn)證.對(duì)不同c的這些計(jì)算,可以看作是同時(shí)進(jìn)行的.一個(gè)不確定算法解決判定問題指:對(duì)輸入w,如果它有解,不確定算法一定會(huì)寫出一個(gè)c,使得驗(yàn)證階段能通過,并返回一個(gè)yes回答.如果一個(gè)判定問題有不確定的多