計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第15章 近似算法

第15

章

近似算法1問(wèn)題定義

2頂點(diǎn)復(fù)蓋問(wèn)題 5貨郎擔(dān)向題

8集合復(fù)蓋問(wèn)題

16MAX-3-SAT問(wèn)題

25加權(quán)的頂點(diǎn)復(fù)蓋問(wèn)題 29子集和問(wèn)題 33鴻溝定理和不可近似性

462如果一個(gè)問(wèn)題是個(gè)NPC問(wèn)題，很可能不存在多項(xiàng)式的算法，而在實(shí)際工作中人們又經(jīng)常碰到NPC的問(wèn)題而且必須要解決，怎么辦呢？找一個(gè)快速的近似算法(Approximationalgorithm)或者一個(gè)啟發(fā)式算法(Heuristicalgorithm)成為解決問(wèn)題的最重要手段。這兩者的區(qū)別在于前者保證計(jì)算結(jié)果與最佳解之間的差別不超過(guò)一個(gè)范圍，而后者不能定量地給予保證，它的實(shí)際效果往往通過(guò)仿真(simulation)實(shí)驗(yàn)予以證實(shí)。這一章，我們只討論近似算法。NP難的優(yōu)化型問(wèn)題的解一般對(duì)應(yīng)一個(gè)目標(biāo)值C并要求這個(gè)值最大，或最小，或最長(zhǎng)，或最短，等等。我們可以把它們分為兩大類，一類是要求目標(biāo)值C最大，另一類是要求目標(biāo)值C最小，分別稱為最大化(maximization)問(wèn)題和最小化(minimization)問(wèn)題。1. 問(wèn)題定義3

4

5計(jì)算圖G(V,E)的頂點(diǎn)復(fù)蓋的一個(gè)簡(jiǎn)單的近似算法是：任取一條邊，(u,v)

E，把點(diǎn)u和v加入集合S中。把被頂點(diǎn)u和v復(fù)蓋的邊從圖G中刪去。如果圖G中不再有邊，那說(shuō)明所有的邊已被S中點(diǎn)所復(fù)蓋，否則，在剩下的邊中重復(fù)步(1)(2)直到圖中不再有邊為止。Approx-Vertex-Cover(G(V,E))S

；

//集合S初始為空

while

E

selectanedge(u,v)

E

//任選一條邊(u,v)

S

S

{u,v} //把u

和v加入集合S

E

E–{(x,y)|x

{u,v}ory

{u,v}}

//刪除與u

或v關(guān)聯(lián)的邊endwhilereturn

SEnd2.

頂點(diǎn)復(fù)蓋問(wèn)題6例

(a)

圖Gabefdcgh(b)

選(a,e)，S={a,e}。虛線是刪除的邊。abefdcgh(c)

選(c,f)，S={a,e,c,f}。abefdcgh(d)

選(d,h)，S={a,e,c,f,d,h}。abefdcgh(f)

最小復(fù)蓋是5個(gè)點(diǎn)，Sopt={a,b,f,g,d}。abefdcgh(e)

近似解S={a,e,c,f,d,h}。abefdcgh7定理15.1

算法Approx-Vertex-Cover是一個(gè)2-近似算法。證明：當(dāng)算法結(jié)束時(shí)，圖中所有邊都因與集合S中某個(gè)點(diǎn)關(guān)聯(lián)而被刪去，因而S是一個(gè)頂點(diǎn)復(fù)蓋。設(shè)算法一共選了k條邊，那么這個(gè)解S的目標(biāo)值為C

=

2k。再考慮最佳解C*。我們注意到，在近似算法每次選取的邊(u,v)中，任何最佳解必須至少包含頂點(diǎn)u或v。又因?yàn)榻扑惴ㄋx取的邊都有不同的頂點(diǎn)，所以任何最佳解必須包含集合S中的至少k個(gè)頂點(diǎn)。因而有C/C*

2k/k=2。

8我們可證明，對(duì)一般的貨郎擔(dān)問(wèn)題，不存在有常數(shù)倍近似度的近似算法。但是，對(duì)于特殊的一類貨郎擔(dān)問(wèn)題有很好的近似算法。下面先討論這一特殊類貨郎擔(dān)問(wèn)題，然后再討論一般的貨郎擔(dān)問(wèn)題。滿足三角不等式關(guān)系的貨郎擔(dān)問(wèn)題加權(quán)圖G中，如果任意三個(gè)頂點(diǎn)u,v,w

V之間的邊滿足關(guān)系w(w,u)

w(u,v)

+w(v,w)，那么稱這個(gè)圖滿足三角不等式。定義15.4

滿足三角不等式的貨郎擔(dān)問(wèn)題定義如下：給定一個(gè)沒有負(fù)權(quán)值的完全圖G(V,E)和一個(gè)正數(shù)k，假設(shè)圖G滿足三角不等式，判斷G是否含有一條貨郎擔(dān)回路使得它的總權(quán)值小于等于k？定理15.2

滿足三角不等式關(guān)系的貨郎擔(dān)問(wèn)題是個(gè)NP-難問(wèn)題。證明：

我們把一般的貨郎擔(dān)問(wèn)題多項(xiàng)式歸約為這個(gè)滿足三角不等式關(guān)系的貨郎擔(dān)問(wèn)題。(接下頁(yè))3.

貨郎擔(dān)問(wèn)題9證明(繼續(xù)1)：假設(shè)一般的貨郎擔(dān)問(wèn)題的一個(gè)特例是一個(gè)沒有負(fù)權(quán)值的完全圖G(V,E)和正數(shù)k?，F(xiàn)在，我們由此構(gòu)造一個(gè)滿足三角不等式的圖G’(V’,E’)和正數(shù)k’。設(shè)|V|=n，這個(gè)構(gòu)造步驟如下：Construct-Triangle-TSP(G(V,E))G’(V’,E’)

G(V,E) //復(fù)制M

max{w(u,v)|w(u,v)

E} //E中最大的邊的權(quán)值Mforeach(u,v)

E’ w’(u,v)

w(u,v)+Mendfork’

k+nMEnd這顯然是個(gè)多項(xiàng)式算法，并且G’滿足三角不等式，這是因?yàn)椋喝稳DG’三點(diǎn)，u,v,w，我們有：w’(w,u)=w(w,u)+M

M+M

(w(u,v)+M)+(w(v,w)+M)=w’(u,v)+w’(v,w)。(接下頁(yè))10

11有2-近似度的貨郎擔(dān)問(wèn)題的算法2-Approx-Triangle-TSP(G(V,E) //G滿足三角不等式取任一頂點(diǎn)

r

V用Prim算法獲得G的一棵以r為根的最小支撐樹T從r開始，對(duì)T做DFS搜索，并把頂點(diǎn)按發(fā)現(xiàn)時(shí)刻順序排序假設(shè)<v1,v2,…,vn>是DFS得到的頂點(diǎn)序列，其中v1=r輸出貨郎擔(dān)回路:C=<v1,v2,…,vn,v1>End算法2-Approx-Triangle-TSP的近似度為2的證明讓我們沿著下面的路徑走一遍。從點(diǎn)r開始，假設(shè)當(dāng)前的棧頂是點(diǎn)u，如果DFS下一步操作是向堆棧壓入一個(gè)點(diǎn)v，那么我們從u走到v。如果是彈出u，回溯到它父親w，那么我們就從u走到w?？傊覀兊穆窂绞菑漠?dāng)前棧頂走到下一個(gè)棧頂。DFS完成時(shí)，堆棧為空，路徑結(jié)束。(接下頁(yè))12算法2-Approx-Triangle-TSP的近似度為2的證明(繼續(xù)1)考慮T中任一條邊(a,b)，a是b的父親。邊(a,b)被DFS訪問(wèn)兩次。第一次，由點(diǎn)a發(fā)現(xiàn)頂點(diǎn)b，向堆棧壓入b，我們的路徑經(jīng)過(guò)(a,b)一次。第二次，是在彈出點(diǎn)b時(shí)，棧頂又回到點(diǎn)a，我們的路徑又經(jīng)過(guò)邊(b,a)一次。下圖(15-2)顯示，這條路徑正好是沿著T的輪廓線的回路C’。這里，輪廓線是經(jīng)過(guò)T中每條邊的兩側(cè)各一次的一條連續(xù)的回路。從頂點(diǎn)r開始，這條回路經(jīng)過(guò)的頂點(diǎn)序列稱為輪廓線序列。radbcehgf(a)一棵支撐樹Tradbcehgf(b)

輪廓線:<r,a,b,a,c,a,r,d,e,f,e,g,e,h,e,d,r>13算法2-Approx-Triangle-TSP的近似度為2的證明(繼續(xù)2)因?yàn)樗惴ㄝ敵龅捻旤c(diǎn)序列C是按照頂點(diǎn)被壓入堆棧的順序，記錄的頂點(diǎn)序列，所以它是輪廓線序列的一個(gè)子序列。由三角不等式關(guān)系可知，這個(gè)子序列形成的回路C的總長(zhǎng)小于等于輪廓線C’的總長(zhǎng)。又因?yàn)檩喞€C’的總長(zhǎng)正好是樹T中所有邊權(quán)值總和的2倍，我們有W(C)

W(C’)=2W(T)。因?yàn)閳DG的最小貨郎擔(dān)回路C*包含G的一個(gè)支撐樹，它的總權(quán)值大于等于最小支撐樹T的總權(quán)值，所以我們有： W(C)

2W(T)

2W(C*)。因此算法Approx-Triangle-TSP有2-近似度。證畢。顯然，算法Approx-Triangle-TSP的時(shí)間復(fù)雜度是O(n2)。14

15Hamilton-Based-on-A

(繼續(xù))：4 如果W(C)=n，則C是圖G的一條哈密爾頓回路，否則原圖G沒有哈密爾頓回路。End上面這個(gè)算法的正確性解釋如下。如果|C|=n，那么C上每條邊權(quán)值必須等于1。因?yàn)闄?quán)值等于1的邊必定是原圖G中的邊，所以C也是G里的一條哈密爾頓回路。反之，如果|C|>n，那么，C必定含有一條不在原圖G中的邊，因此它的權(quán)值至少是|C|

(n-1)+(

n+1)=(

+1)n>

n。這時(shí)，我們可斷定G’中不存在一條總權(quán)值是n的貨郎擔(dān)回路，否則，這個(gè)實(shí)例的近似度為|C|/n>

，這與算法A的近似度矛盾。所以原圖G沒有哈密爾頓回路。因?yàn)槿绻鸓

NP，哈密爾頓回路問(wèn)題沒有多項(xiàng)式算法，因此算法A不可能存在。定理15.3證畢。

16

4.

集合復(fù)蓋問(wèn)題17

18復(fù)雜度解釋(繼續(xù))又因?yàn)槊窟x一個(gè)集合，至少可以復(fù)蓋U中一個(gè)元素，所以最多只要循環(huán)m次。當(dāng)然，循環(huán)次數(shù)也不會(huì)超過(guò)n次，所以有復(fù)雜度O(mn

Min(m,n))下面定理給出近似度。

19證明(繼續(xù)1)現(xiàn)在，讓我們把每個(gè)集合Si對(duì)應(yīng)的代價(jià)1平分到被它第一次復(fù)蓋的元素上去，也就是被Si復(fù)蓋但未被S1,S2,…,Si-1

復(fù)蓋的元素上去。這樣，每個(gè)元素x

U

都被賦予一個(gè)代價(jià)c(x)，并有c(U)=|C|=h?？匆粋€(gè)例子。假設(shè)有F={S1,S2,S3,S4,S5}，其中，S1={a,b,c},S2={a,d,e},S3={b,e,f},S4={c,d,g},S5={a,d,f}。U

=

{a,b,c,d,e,f,g}。算法依次選取集合以及各元素代價(jià)如下：第1次，選S1={a,b,c},代價(jià)c(a)=c(b)=c(c)=1/3，更新U={d,e,f,g}第2次，選S2={a,d,e},新復(fù)蓋元素有代價(jià)c(d)=c(e)=1/2，U={f,g}第3次，選S3={b,e,f},新復(fù)蓋元素有代價(jià)c(f)=1，U

={g}第4次，選S4={c,d,g},新復(fù)蓋元素有代價(jià)c(g)=1，U

=

。上例中，算法產(chǎn)生的復(fù)蓋是C={S1,S2,S3,S4}。

(接下頁(yè))20

21證明(繼續(xù)

3)讓我們定義一個(gè)集合序列，P0

=S，P1

=S–S1，P2

=S–(S1

S2)，…，Ph

=S-(S1

S2

…

Sh)。集合Pi(1

i

h)中元素是

S中還沒有被

S1

S2

…

Si所復(fù)蓋的元素。注意，這里的

S是最優(yōu)解C*中的一個(gè)集合，而S1，S2，…，Si

是我們算法所選取的集合。記ui

=|Pi|，即Pi

中元素個(gè)數(shù)。因?yàn)樗惴窟x一個(gè)集合

Si只會(huì)減少

S中未被復(fù)蓋的元素。因此有u0

u1

u2

…

uh

=0。不失一般性，可假設(shè)uh

是序列中第一個(gè)0。(接下頁(yè))22

23

24

25

5. MAX-3-SAT問(wèn)題26我們假定

含n個(gè)變量，x1,x2,…,xn,并且每個(gè)變量xi和它的非

xi不同時(shí)出現(xiàn)在一個(gè)子句中，因?yàn)檫@樣的子句可被任何一組賦值滿足，不須考慮。下面給出一個(gè)非常簡(jiǎn)單的隨機(jī)算法來(lái)解這個(gè)MAX-3-SAT問(wèn)題。Randomized-MAX-3-SAT(

)for

i

1to

n v

Randomnumber(0or1) //產(chǎn)生0或1的隨機(jī)數(shù)，各占50%機(jī)率

if

v=1

then

xi

1

xi

0

else

xi

0

xi

1

endifendforEnd顯然，這是個(gè)多項(xiàng)式算法。下面的定理證明它有很好的近似度。27

28

29

6. 加權(quán)的頂點(diǎn)復(fù)蓋問(wèn)題30

31線性規(guī)劃解(繼續(xù)2)：顯然，任一個(gè)0-1整數(shù)規(guī)劃的可行解(包括最佳解)也是變化后實(shí)數(shù)型的線性規(guī)劃的一個(gè)可行解?？尚薪馐侵笣M足約束條件的解。所以，線性規(guī)劃的最佳解可作為0-1整數(shù)規(guī)劃最佳解的一個(gè)下界。下面算法顯示如何用線性規(guī)劃來(lái)得出原問(wèn)題的一個(gè)近似解。Approx-Min-Weight-VC(G,w)C

//頂點(diǎn)復(fù)蓋初始為空求出上述線性規(guī)劃的最佳解

x(v) //x(v)表示向量(x(v1),x(v2),…,x(vn))foreachv

V ifx(v)

1/2 thenC

C

{v} endifendforreturn

CEnd32

33在第14章我們已知子集和問(wèn)題是個(gè)NPC問(wèn)題。這一節(jié)我們討論它的近似解，并通過(guò)它進(jìn)一步理解近似機(jī)制和完全多項(xiàng)式近似機(jī)制的概念和設(shè)計(jì)方法。我們先定義一個(gè)與之關(guān)聯(lián)的優(yōu)化型問(wèn)題。

7. 子集和問(wèn)題34一個(gè)保證最優(yōu)解的指數(shù)型算法設(shè)S={x1,x2,…,xn}，這個(gè)指數(shù)型算法的思路就是窮舉法，它遍歷所有可能的子集及其子集和。從空集開始，先檢查{x1}的子集，然后遍歷{x1,x2}的子集，再遍歷所有{x1,x2,x3}的子集，等等，直至所有{x1,x2,…,xn}的子集。為簡(jiǎn)化記號(hào)，如果x表示一個(gè)整數(shù)，我們用S+x表示把集合S中每個(gè)數(shù)字加上x后的集合，即S+x={s+x|s

S}。為了突出思路，下面的算法只給出子集和的值，而不記錄子集中具體是那幾個(gè)數(shù)。當(dāng)需要實(shí)現(xiàn)算法時(shí)，讀者可自己插入這一工作。在后面的例子中，我們會(huì)介紹如何記錄具體數(shù)字的方法。遍歷過(guò)程中，如發(fā)現(xiàn)有子集和大于目標(biāo)值

t者，則丟棄該子集。算法如下:(見下頁(yè))35Exact-Subset-Sum(S,t)n

|S|L0

{0} //初始，集合L0只含一個(gè)子集，即空集，其和為0for

i

1to

n

Li

Li-1

(Li-1+xi)

//含所有不同的子集和，刪除重復(fù)的和

剔除Li中所有大于t的數(shù)字

//大于t的子集和不可能是解endforreturn

Ln

中最大數(shù)End歸納法可證，Li

包含{x1,x2,…,xi}的所有不大于t的子集和。算法結(jié)束時(shí)，Ln

包含S的所有不大于t的子集和。Ln

中最大值必是最優(yōu)解。因?yàn)長(zhǎng)i+1的元素可能是Li的兩倍，這是指數(shù)型算法。下面例子中，我們?cè)贚i

中數(shù)字x后面加上+號(hào)或者-號(hào)。x+表示x是由Li-1

中某個(gè)數(shù)，加上xi所得；而x-表示x是原Li-1中一個(gè)數(shù)。36例15.3

設(shè)S={1,4,5,7}和t

=14。演示算法Exact-Subset-Sum逐步產(chǎn)生的集合Li

(1

i

4)，并找出最佳解。解：L0

{0}L1

{0-,1+} (1+表示該數(shù)字含x1=1)L2

{0-,1-,4+,5+} (+表示該數(shù)字含x2=4)L3

{0-,1-,4-,5-,6+,9+,10+} (+表示含x3，另外，5+刪除)L4

{0-,1-,4-,5-,6-,9-,10-,7+,8+,11+,12+,13+}

(16+,17+刪除)13是最佳子集和。根據(jù)+、-號(hào)，我們可以把對(duì)應(yīng)子集找到:從L4中13+知該子集含x4=7。

13-7=6。從L3

中

6+知該子集含x3=5。6–5=1。從L2

中1-知該子集不含x2。從L1

中1+知該子集含x1=1。1–1

=0，搜索結(jié)束。子集為{1,5,7}。37子集和問(wèn)題的一個(gè)完全多項(xiàng)式近似機(jī)制改進(jìn)指數(shù)型算法的主要思路是簡(jiǎn)化Li。如果Li中兩個(gè)數(shù)字很接近，則去掉一個(gè)。這可能會(huì)影響解的近似度，但讓它在可控范圍內(nèi)。我們用一個(gè)修整參數(shù)

來(lái)控制，0<

<1。假設(shè)

L含排好序的m個(gè)數(shù)字，y1

y2

…

ym。保留y1，從y2開始，遵循以下規(guī)則：設(shè)當(dāng)前保留的最大數(shù)是x，而下一個(gè)數(shù)是

y，如果y

(1+

)x，則刪除y

(稱y被x修整)，否則保留y。例15.4用修整參數(shù)

=0.1修整序列，(1+

)

=1.1。

L

={10,11,12,15,20,21,22,23,24,29}。解：保留10。11

1.1

10,刪除11。12>1.1

10,保留12。15>1.1

12,保留15。20>1.1

15,保留20。21<1.1

20,刪除21。22

1.1

20,刪除22。23>1.1

20,保留23。24<1.1

23,刪除24。29>1.1

23,保留29。刪除后的集合為L(zhǎng)’={10,12,15,20,23,29}。38給定排好序的序列L={y1,y2,…,ym}，用修整參數(shù)

對(duì)L進(jìn)行修整的過(guò)程可用下面?zhèn)未a實(shí)現(xiàn)。Trim(L,

)m

|L|L’

{y1} //始終保留y1last

y1 //掃描到目前為止，最后一個(gè)被保留的數(shù)字for

i

2to

m

if

yi

>last

(1+

)

then

L’

L’

{yi} //把yi

加到L’中，放在最后

last

yi

endifendforreturn

L’End算法Trim的復(fù)雜度是O(|L|)。39下面是子集和的一個(gè)完全多項(xiàng)式近似機(jī)制Approx-Subset-Sum(S,t,

)n

|S|L0

{0}for

i

1to

n

Li

Li-1

(Li-1+xi) //需要?jiǎng)h除重復(fù)的子集和

把Li中子集和排序

//這一行和上一行可用合并算法同時(shí)完成

Li

Trim(Li,

/2n)

刪除Li

中大于t的子集和endforreturn

Ln

中最大數(shù)z*End下面證明上面的算法是一個(gè)完全多項(xiàng)式近似機(jī)制。我們定義P0={0}，Pi

=Pi-1

(Pi-1+x)

(1

i

n)。注意，Pi

包含了集合{x1,x2,…,xi}

的所有可能的子集和，沒有任何刪除。顯然Li

是Pi

的子集。40

41

42

43

44

45

46以上討論發(fā)現(xiàn)，有些NPC的優(yōu)化型問(wèn)題可以有常數(shù)倍近似度的多項(xiàng)式算法，但是，有些優(yōu)化型問(wèn)題卻不存在有常數(shù)倍近似度的多項(xiàng)式算法。有沒有規(guī)律可循呢。下面要介紹的鴻溝定理可幫助我們作判斷。優(yōu)化型問(wèn)題有兩類，一類是極小問(wèn)題，另一類是極大問(wèn)題。極小問(wèn)題是希望目標(biāo)值達(dá)到最小，而極大問(wèn)題是希望目標(biāo)值達(dá)到最大。例如頂點(diǎn)復(fù)蓋問(wèn)題是個(gè)極小問(wèn)題，而圖的團(tuán)的問(wèn)題是個(gè)極大向題。對(duì)這兩類問(wèn)題，鴻溝定理的描述不同，但是是對(duì)稱的。8. 鴻溝定理和不可近似性47定理15.10(極小問(wèn)題的鴻溝定理)假設(shè)問(wèn)題A是個(gè)已知的判斷型NPC問(wèn)題，而問(wèn)題B是個(gè)極小問(wèn)題。如果問(wèn)題A的任一個(gè)實(shí)例

可在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化為問(wèn)題B的一個(gè)實(shí)例

，并且有:實(shí)例

的解是yes，記為A(

)=1，當(dāng)且僅當(dāng)實(shí)例

有解并且最小目標(biāo)值w

W，這里，

W可以是一個(gè)正常數(shù)，也可以是一個(gè)與n=|

|有關(guān)的正函數(shù);實(shí)例

的解是no，記為A(

)=0，當(dāng)且僅當(dāng)實(shí)例

有解并且最小目標(biāo)值w

kW，這里k>1是一個(gè)正的常數(shù);那么，只要P

NP，就不存在有近似度小于k的問(wèn)題B的多項(xiàng)式算法。讓我們稱這樣的多項(xiàng)式轉(zhuǎn)化為多項(xiàng)式鴻溝歸約。證明：我們注意到，問(wèn)題B的判斷型問(wèn)題可以這樣描述：給定問(wèn)題B的實(shí)例

和期待值W，判斷

是否有目標(biāo)值w

W的解。(接下頁(yè))48證明(繼續(xù)1)：如果存在定理中描述的多項(xiàng)式轉(zhuǎn)化，那么這個(gè)轉(zhuǎn)化滿足的第(1)條就已證明了問(wèn)題B的判斷型問(wèn)題也是個(gè)NPC問(wèn)題。如果這個(gè)轉(zhuǎn)化還滿足(2)，那么，只要P

NP，就不存在有近似度小于k的問(wèn)題B的多項(xiàng)式算法。所以多項(xiàng)式鴻溝歸約要比一般NPC問(wèn)題的多項(xiàng)式歸約要更強(qiáng)。我們用反證法證明，只要P

NP，就不存在有近似度小于k的問(wèn)題B的多項(xiàng)式算法。為此，讓我們假設(shè)有近似度小于k的近似算法B*，它在多項(xiàng)式時(shí)間內(nèi)對(duì)任一實(shí)例

進(jìn)行運(yùn)算后得到一個(gè)目標(biāo)值為Z的解。并滿足Z/w<k，這里，w是最佳解的目標(biāo)值。我們證明這不可能，因?yàn)?，如果是這樣，那么，我們可以得到問(wèn)題A的多項(xiàng)式判定算法如下：(接下頁(yè))49證明(繼續(xù)2)：Algorithm-for-A(

)對(duì)問(wèn)題A的一個(gè)實(shí)例

進(jìn)行多項(xiàng)式鴻溝歸約，得到問(wèn)題B的實(shí)例

用多項(xiàng)式近似算法B*對(duì)實(shí)例

進(jìn)行運(yùn)算后得到一個(gè)目標(biāo)值為Z的解如果Z<

kW，那么輸出A(

)=1(表示yes)，否則A(

)=0(表示no)End這個(gè)判斷算法是正確的。這是因?yàn)?，如果Z

<

kW，那么就有：最小值w

Z

<

kW。所以不可能有w

kW，根據(jù)多項(xiàng)式鴻溝歸約第(2)條，不可能有A(

)=0，所以必然有A(

)=1。反之，如果Z

kW，因?yàn)樗惴˙*的近似度小于k，必有Z/w<k，也就是wk>Z。因此有wk>Z

kW，即w>W。根據(jù)多項(xiàng)式鴻溝歸約的第(1)條，不可能有A(

)=1，所以必定有A(

)=0。這樣一來(lái)，問(wèn)題A便可以在多項(xiàng)式時(shí)間內(nèi)被判定，與P

NP矛盾。

50定理15.11(極大問(wèn)題的鴻溝定理)假設(shè)問(wèn)題A是個(gè)已知的判斷型NPC問(wèn)題，而問(wèn)題B是個(gè)極大問(wèn)題。如果問(wèn)題A的任一個(gè)實(shí)例

可在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化為問(wèn)題B的一個(gè)實(shí)例

，并且有:實(shí)例

的解是yes，即A(

)=1，當(dāng)且僅當(dāng)實(shí)例

有解并且最大目標(biāo)值w

W，實(shí)例

的解是no，即A(

)=0，當(dāng)且僅當(dāng)實(shí)例

有解并且最大目標(biāo)值w

W/k，這里k>1是一個(gè)正的常數(shù)，那么，只要P

NP，就不存在有近似度小于k的問(wèn)題B的多項(xiàng)式算法。這樣的多項(xiàng)式轉(zhuǎn)化稱為多項(xiàng)式鴻溝歸約。證明：留給讀者。

下面讓我們看一個(gè)例子，即任務(wù)均勻分配問(wèn)題。51任務(wù)均勻分配問(wèn)題設(shè)S={t1，t2，…，tn}是n個(gè)任務(wù)的集合，這里，tk(1

k

n)是個(gè)正整數(shù)，它既代表第k個(gè)任務(wù)，也代表該任務(wù)需要的工作量是tk小時(shí)?，F(xiàn)有

m個(gè)工人，而每個(gè)工人能夠干的工作是這n個(gè)任務(wù)的一個(gè)子集，分別用S1,S2,…,Sm代表。假設(shè)每個(gè)任務(wù)至少有一個(gè)工人會(huì)干，而每個(gè)工人也至少會(huì)干其中一個(gè)任務(wù)。問(wèn)題：

把這n個(gè)任務(wù)分配給這m個(gè)工人干并使工作量盡量均勻，具體說(shuō)，就是使得一個(gè)工人能分配到的最多工作量