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

第15

章

近似算法1問題定義

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

8集合復(fù)蓋問題

16MAX-3-SAT問題

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

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

4

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

E，把點u和v加入集合S中。把被頂點u和v復(fù)蓋的邊從圖G中刪去。如果圖G中不再有邊，那說明所有的邊已被S中點所復(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.

頂點復(fù)蓋問題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個點，Sopt={a,b,f,g,d}。abefdcgh(e)

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

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

=

2k。再考慮最佳解C*。我們注意到，在近似算法每次選取的邊(u,v)中，任何最佳解必須至少包含頂點u或v。又因為近似算法所選取的邊都有不同的頂點，所以任何最佳解必須包含集合S中的至少k個頂點。因而有C/C*

2k/k=2。

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

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

w(u,v)

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

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

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

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

貨郎擔(dān)問題9證明(繼續(xù)1)：假設(shè)一般的貨郎擔(dān)問題的一個特例是一個沒有負權(quán)值的完全圖G(V,E)和正數(shù)k?，F(xiàn)在，我們由此構(gòu)造一個滿足三角不等式的圖G’(V’,E’)和正數(shù)k’。設(shè)|V|=n，這個構(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’滿足三角不等式，這是因為：任取圖G’三點，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)。(接下頁)10

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

r

V用Prim算法獲得G的一棵以r為根的最小支撐樹T從r開始，對T做DFS搜索，并把頂點按發(fā)現(xiàn)時刻順序排序假設(shè)<v1,v2,…,vn>是DFS得到的頂點序列，其中v1=r輸出貨郎擔(dān)回路:C=<v1,v2,…,vn,v1>End算法2-Approx-Triangle-TSP的近似度為2的證明讓我們沿著下面的路徑走一遍。從點r開始，假設(shè)當(dāng)前的棧頂是點u，如果DFS下一步操作是向堆棧壓入一個點v，那么我們從u走到v。如果是彈出u，回溯到它父親w，那么我們就從u走到w。總之，我們的路徑是從當(dāng)前棧頂走到下一個棧頂。DFS完成時，堆棧為空，路徑結(jié)束。(接下頁)12算法2-Approx-Triangle-TSP的近似度為2的證明(繼續(xù)1)考慮T中任一條邊(a,b)，a是b的父親。邊(a,b)被DFS訪問兩次。第一次，由點a發(fā)現(xiàn)頂點b，向堆棧壓入b，我們的路徑經(jīng)過(a,b)一次。第二次，是在彈出點b時，棧頂又回到點a，我們的路徑又經(jīng)過邊(b,a)一次。下圖(15-2)顯示，這條路徑正好是沿著T的輪廓線的回路C’。這里，輪廓線是經(jīng)過T中每條邊的兩側(cè)各一次的一條連續(xù)的回路。從頂點r開始，這條回路經(jīng)過的頂點序列稱為輪廓線序列。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)因為算法輸出的頂點序列C是按照頂點被壓入堆棧的順序，記錄的頂點序列，所以它是輪廓線序列的一個子序列。由三角不等式關(guān)系可知，這個子序列形成的回路C的總長小于等于輪廓線C’的總長。又因為輪廓線C’的總長正好是樹T中所有邊權(quán)值總和的2倍，我們有W(C)

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

2W(T)

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

15Hamilton-Based-on-A

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

(n-1)+(

n+1)=(

+1)n>

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

，這與算法A的近似度矛盾。所以原圖G沒有哈密爾頓回路。因為如果P

NP，哈密爾頓回路問題沒有多項式算法，因此算法A不可能存在。定理15.3證畢。

16

4.

集合復(fù)蓋問題17

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

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

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

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

U

都被賦予一個代價c(x)，并有c(U)=|C|=h。看一個例子。假設(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}。算法依次選取集合以及各元素代價如下：第1次，選S1={a,b,c},代價c(a)=c(b)=c(c)=1/3，更新U={d,e,f,g}第2次，選S2={a,d,e},新復(fù)蓋元素有代價c(d)=c(e)=1/2，U={f,g}第3次，選S3={b,e,f},新復(fù)蓋元素有代價c(f)=1，U

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

=

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

(接下頁)20

21證明(繼續(xù)

3)讓我們定義一個集合序列，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*中的一個集合，而S1，S2，…，Si

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

=|Pi|，即Pi

中元素個數(shù)。因為算法每選一個集合

Si只會減少

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

u1

u2

…

uh

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

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

23

24

25

5. MAX-3-SAT問題26我們假定

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

xi不同時出現(xiàn)在一個子句中，因為這樣的子句可被任何一組賦值滿足，不須考慮。下面給出一個非常簡單的隨機算法來解這個MAX-3-SAT問題。Randomized-MAX-3-SAT(

)for

i

1to

n v

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

if

v=1

then

xi

1

xi

0

else

xi

0

xi

1

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

28

29

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

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

//頂點復(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章我們已知子集和問題是個NPC問題。這一節(jié)我們討論它的近似解，并通過它進一步理解近似機制和完全多項式近似機制的概念和設(shè)計方法。我們先定義一個與之關(guān)聯(lián)的優(yōu)化型問題。

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

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

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

|S|L0

{0} //初始，集合L0只含一個子集，即空集，其和為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é)束時，Ln

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

中最大值必是最優(yōu)解。因為Li+1的元素可能是Li的兩倍，這是指數(shù)型算法。下面例子中，我們在Li

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

中某個數(shù)，加上xi所得；而x-表示x是原Li-1中一個數(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ù)+、-號，我們可以把對應(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子集和問題的一個完全多項式近似機制改進指數(shù)型算法的主要思路是簡化Li。如果Li中兩個數(shù)字很接近，則去掉一個。這可能會影響解的近似度，但讓它在可控范圍內(nèi)。我們用一個修整參數(shù)

來控制，0<

<1。假設(shè)

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

y2

…

ym。保留y1，從y2開始，遵循以下規(guī)則：設(shè)當(dāng)前保留的最大數(shù)是x，而下一個數(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’={10,12,15,20,23,29}。38給定排好序的序列L={y1,y2,…,ym}，用修整參數(shù)

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

)m

|L|L’

{y1} //始終保留y1last

y1 //掃描到目前為止，最后一個被保留的數(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下面是子集和的一個完全多項式近似機制Approx-Subset-Sum(S,t,

)n

|S|L0

{0}for

i

1to

n

Li

Li-1

(Li-1+xi) //需要刪除重復(fù)的子集和

把Li中子集和排序

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

Li

Trim(Li,

/2n)

刪除Li

中大于t的子集和endforreturn

Ln

中最大數(shù)z*End下面證明上面的算法是一個完全多項式近似機制。我們定義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)化型問題可以有常數(shù)倍近似度的多項式算法，但是，有些優(yōu)化型問題卻不存在有常數(shù)倍近似度的多項式算法。有沒有規(guī)律可循呢。下面要介紹的鴻溝定理可幫助我們作判斷。優(yōu)化型問題有兩類，一類是極小問題，另一類是極大問題。極小問題是希望目標值達到最小，而極大問題是希望目標值達到最大。例如頂點復(fù)蓋問題是個極小問題，而圖的團的問題是個極大向題。對這兩類問題，鴻溝定理的描述不同，但是是對稱的。8. 鴻溝定理和不可近似性47定理15.10(極小問題的鴻溝定理)假設(shè)問題A是個已知的判斷型NPC問題，而問題B是個極小問題。如果問題A的任一個實例

可在多項式時間內(nèi)轉(zhuǎn)化為問題B的一個實例

，并且有:實例

的解是yes，記為A(

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

有解并且最小目標值w

W，這里，

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

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

的解是no，記為A(

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

有解并且最小目標值w

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

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

和期待值W，判斷

是否有目標值w

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

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

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

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

)對問題A的一個實例

進行多項式鴻溝歸約，得到問題B的實例

用多項式近似算法B*對實例

進行運算后得到一個目標值為Z的解如果Z<

kW，那么輸出A(

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

)=0(表示no)End這個判斷算法是正確的。這是因為，如果Z

<

kW，那么就有：最小值w

Z

<

kW。所以不可能有w

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

)=0，所以必然有A(

)=1。反之，如果Z

kW，因為算法B*的近似度小于k，必有Z/w<k，也就是wk>Z。因此有wk>Z

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

)=1，所以必定有A(

)=0。這樣一來，問題A便可以在多項式時間內(nèi)被判定，與P

NP矛盾。

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

可在多項式時間內(nèi)轉(zhuǎn)化為問題B的一個實例

，并且有:實例

的解是yes，即A(

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

有解并且最大目標值w

W，實例

的解是no，即A(

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

有解并且最大目標值w

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

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

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

k

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

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

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