算法設(shè)計與分析 NP完全問題

1、NP完全問題研究P=NP的問題有兩條基本思路：證明NP類中的某些問題是難解的，從而得到NP瘁。但是要證明這一點幾乎同證明P=NP 一樣困難?？疾霳P類中問題之間的關(guān)系，從中找到一些具有特殊性質(zhì)的、與P類問 題顯著不同的問題。沿著這一路線人們已經(jīng)證明了在NP類中存在被稱為 NP完全的子類，簡稱NPC問題，并由此發(fā)展了一套著名的NP完全理論。本節(jié)簡要先介紹NP完全性理論。為此，首先給出各語言之間的多項式變換 的概念。定義1所謂從一個語言L1 Q ；到另一個語言L2( ;的多項式變換是指 滿足下面兩個條件的函數(shù)f : ; TZ ；，(1)存在計算f的一個多項式時間DTM程序；對于所有的X 6；有：尤

2、 L1當(dāng)且僅當(dāng)fe L；。用L1氐L；表示存在一個從語言L1到語言L；的多項式變換。相應(yīng)地，對于判定問題n ,n，設(shè)e和e是相應(yīng)的編碼策略。若Ln ,e X Ln ,e ，則記為1；1211；n 1 xn ；。也可以從問題的層次來敘述：由判定問題n1到判定問題n；的多項式變換是 滿足下列條件的函數(shù)f : Dn T Dn，f可由一個多項式時間的確定性算法來計算；對于所有的le Dn有：IeDn當(dāng)且僅當(dāng)fe、；。定義2稱一個語言L (判定問題n )為NP完全的(NPC )，如果L e NP (ne NP)，且對于所有別的語言 Le NP (判定問題ne NP )均有 l x l (n x n)。按

3、照定義2,要證明問題n是NP完全的，需要證明所有的NP問題均能夠 經(jīng)多項式變換變成n。這幾乎是很難做到的。如果NP完全問題比較多，我們也 不能對每一個這樣的問題都這樣驗證。為此我們討論一些NPC問題的有用的性 質(zhì)。性質(zhì)1如果L氐L，則L e P意味著Le P。性質(zhì)2如果L x L而且L x L，則L泛L。由性質(zhì)1, 2,不能推出下列結(jié)論，定理2設(shè)n是NP完全的，如果P。NP，則Ue NP P。定理 3 如果 L , L e NP,Lx L，則 Le NPC n L e NPC .定理3是證明NP完全問題的基礎(chǔ)。但這需要一個NPC問題作為源問題Cook 首先給出這樣問題一可滿足性問題?？蓾M足性問

4、題是數(shù)理邏輯中一個重要問題，它定義在布爾變量之上。給定 布爾變量集U = ,u2， ,um，U上的一個真值分配是指一個映射t: U T, F。U上的一個子句C就是由一些布爾變量(或它們的“否”)通過邏輯“或”連接起來的布爾表達(dá)式。若存在對于布爾變量集U的一個真值分配， 使得該子句取值為真，則說該子句被滿足。子句的集合說是可滿足的，如果存在 U的一個真值分配，使得集合中的每個子句的取值均為真?？蓾M足性問題可描述 如下：例 給定布爾變量之集U以及U上子句的一個集合C。問是否存在U的一個真值分配，使得C是可滿足的。Cook定理 可滿足性問題是NP完全問題。從Cook的開創(chuàng)性工作至今，人們已經(jīng)發(fā)現(xiàn)并證

5、明了數(shù)千個NPC問題(如， 0/1背包問題和Hamilton回路問題)，總結(jié)出證明NP完全性的幾種方法，并建 立了如何分析、進而近似求解NP完全問題的方法等一系列理論結(jié)果。以下列出幾個典型的NPC問題：三維匹配問題 3DM(3 Dimensional Matching)例： 給定三個互不相交的、均含有q個元素的集合W，X，Y，取M c W x X x Y。問：M包含一個匹配嗎？即是說，是否存在一個子集Mc M，使得I MI = q，且M中任意兩個三元組都沒有相同的分量。 三元精確覆蓋問題X3C(Exact Cover by 3-sets)例：給定有限集合X, IXI = 3q，以及X的三元子集

6、族C。問：C含有X的一個精確覆蓋嗎？即是說，是否存在一個子族Cc C，使得X的每個元素恰好只出現(xiàn)在C的一個三元子集中。注意到，如果令 =W u X u Y , C = w,尤,ywe W,xe X,y e Y，則三元 匹配問題就轉(zhuǎn)化為三元精確覆蓋問題。又因為三元匹配問題是NP完全問題，所 以，由三元匹配問題是NPC問題，可以知道，三元精確覆蓋問題也是NPC問題。頂點覆蓋問題VC (Vertex Cover)例：給定一個圖G(V,E)和一個正整數(shù)K|V|.問：是否存在G的一個頂點數(shù)不超過K的覆蓋？即是否存在一個頂點子集V/c V,|V/| K，使得對于每一條邊u,v eE，u與v中至少有一個屬于V/.Hamilton 回路問題 HC (Hamiltonian Circuit)例：已知一個圖G(V,E)。問：G含有一個Hamilton回路嗎？ G的Hamilton回路是指包含圖G的所有 頂點的簡單回路，即是G的頂點的一個排序：七勺，匕，其中n=|V|，使 得對所有的 i: 1 i n, ( v ,v eE，( v ,v eE.i i+1n 1劃分問題例 已知一個有限集合A及對于每個a e A的一個權(quán)值s(a) e Z +。問問是否存在A的一個子集4C A，使得s(a) = s(a) ？aeAaeA