np完整性理論ppt課件-資料下載頁(yè)
2025-05-05 18:18本頁(yè)面
【正文】 完全問(wèn)題樹 32 合取范式的可滿足性問(wèn)題 （ CNFSAT） 要證明 CNFSAT∈NPC ， 只要證明在 Cook定理中定義的布爾表達(dá)式 A， … ， G或者已是合取范式，或者有的雖然不是合取范式，但可以用布爾代數(shù)中的變換方法將它們化成合取范式，而且合取范式的長(zhǎng)度與原表達(dá)式的長(zhǎng)度只差一個(gè)常數(shù)因子。 問(wèn)題描述： 給定一個(gè)合取范式 α ， 判定它是否可滿足。 如果一個(gè)布爾表達(dá)式是一些因子和之積，則稱之為合取范式，簡(jiǎn)稱 CNF(Conjunctive Normal Form)。 這里的因子是變量 或 。例如： 就是一個(gè)合取范式，而 就不是合取范式。 xx ))()(( 3213221 xxxxxxx ????321 xxx ?33 3元合取范式的可滿足性問(wèn)題 （ 3SAT） 證明思路： 3SAT∈NP 是顯而易見的。為了證明 3SAT∈NPC ，只要證明 CNFSAT∝ p 3SAT， 即合取范式的可滿足性問(wèn)題可在多項(xiàng)式時(shí)間內(nèi)變換為 3SAT。 問(wèn)題描述： 給定一個(gè) 3元 合取范式 α ， 判定它是否可滿足。 34 團(tuán)問(wèn)題 CLIQUE 證明思路： 已經(jīng)知道 CLIQUE∈NP 。 通過(guò) 3SAT∝ pCLIQUE來(lái)證明 CLIQUE是 NP難的，從而證明團(tuán)問(wèn)題是 NP完全的。 問(wèn)題描述： 給定一個(gè)無(wú)向圖 G=(V， E)和一個(gè)正整數(shù) k， 判定圖 G是否包含一個(gè) k團(tuán)，即是否存在， V’?V，|V’|=k， 且對(duì)任意 u， w∈V ’有 (u， w)∈E 。 35 頂點(diǎn)覆蓋問(wèn)題 （ VERTEXCOVER） 證明思路： 首先， VERTEXCOVER∈NP 。 因?yàn)閷?duì)于給定的圖 G和正整數(shù) k以及一個(gè) “ 證書 ” V’， 驗(yàn)證 |V’|=k， 然后對(duì)每條邊 (u， v)∈E ，檢查是否有 u∈V ’或 v∈V ’， 顯然可在多項(xiàng)式時(shí)間內(nèi)完成。 其次，通過(guò) CLIQUE∝ pVERTEXCOVER來(lái)證明頂點(diǎn)覆蓋問(wèn)題是 NP難的。 問(wèn)題描述： 給定一個(gè)無(wú)向圖 G=(V， E)和一個(gè)正整數(shù) k， 判定是否存在 V’?V， |V’|=k， 使得對(duì)于任意 (u， v)∈E 有 u∈V ’或v∈V ’。 如果存在這樣的 V’， 就稱 V’為圖 G的一個(gè)大小為 k頂點(diǎn)覆蓋。 36 子集和問(wèn)題 （ SUBSETSUM） 問(wèn)題描述： 給定整數(shù)集合 S和一個(gè)整數(shù) t， 判定是否存在 S的一個(gè)子集 S’?S， 使得 S’中整數(shù)的和為 t。 例如，若 S={1， 4，16， 64， 256， 1040， 1041， 1093， 1284， 1344}且 t=3754， 則子集 S’={1， 16， 64， 256， 1040， 1093， 1284}是一個(gè)解。 證明思路： 首先，對(duì)于子集和問(wèn)題的一個(gè)實(shí)例 S， t， 給定一個(gè) “ 證書 ” S’， 要驗(yàn)證 t= 是否成立，顯然可在多項(xiàng)式時(shí)間內(nèi)完成。因此， SUBSETSUM∈NP ； 其次，證明 VERTEXCOVER∝ pSUBSETSUM。 ?? 39。Si i37 哈密頓回路問(wèn)題 （ HAMCYCLE） 證明思路： 首先，已知哈密頓回路問(wèn)題是一個(gè) NP類問(wèn)題。 其次，通過(guò)證明 3SAT∝ pHAMCYCLE， 得出： HAMCYCLE∈NPC 。 問(wèn)題描述： 給定無(wú)向圖 G=(V， E)， 判定其是否含有一哈密頓回路。 38 旅行售貨員問(wèn)題 TSP 首先，給定 TSP的一個(gè)實(shí)例 (G， c， k)， 和一個(gè)由 n個(gè)頂點(diǎn)組成的頂點(diǎn)序列。驗(yàn)證算法要驗(yàn)證這 n個(gè)頂點(diǎn)組成的序列是圖 G的一條回路，且經(jīng)過(guò)每個(gè)頂點(diǎn)一次。另外，將每條邊的費(fèi)用加起來(lái)，并驗(yàn)證所得的和不超過(guò) k。 這個(gè)過(guò)程顯然可在多項(xiàng)式時(shí)間內(nèi)完成，即 TSP∈NP 。 其次，旅行售貨員問(wèn)題與哈密頓回路問(wèn)題有著密切的聯(lián)系。哈密頓回路問(wèn)題可在多項(xiàng)式時(shí)間內(nèi)變換為旅行售貨員問(wèn)題。即HAMCYCLE∝ pTSP。 從而，旅行售貨員問(wèn)題是 NP難的。 因此， TSP∈NPC 。 問(wèn)題描述： 給定一個(gè)無(wú)向完全圖 G=(V， E)及定義在 V?V上的一個(gè)費(fèi)用函數(shù) c和一個(gè)整數(shù) k， 判定 G是否存在經(jīng)過(guò) V中各頂點(diǎn)恰好一次的回路，使得該回路的費(fèi)用不超過(guò) k。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1