計(jì)算機(jī)算法設(shè)計(jì)與實(shí)現(xiàn)王曉東主編第三版PPT第9章NP完全性理論與近似算法

1、1 第9章 NP完全性理論與近似算法2學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)理解RAM，RASP和圖靈機(jī)計(jì)算模型理解非確定性圖靈機(jī)的概念理解P類與NP類語(yǔ)言的概念 理解NP完全問(wèn)題的概念理解近似算法的性能比及多項(xiàng)式時(shí)間近似格式的概念通過(guò)范例學(xué)習(xí)NP完全問(wèn)題的近似算法（1）頂點(diǎn)覆蓋問(wèn)題；（2）旅行售貨員問(wèn)題；（3）集合覆蓋問(wèn)題；（4）子集和問(wèn)題。39.19.1 計(jì)算模型計(jì)算模型n在進(jìn)行問(wèn)題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問(wèn)題所用的計(jì)算模型，包括定義該計(jì)算模型中所用的基本運(yùn)算。n建立計(jì)算模型的目的是為了使問(wèn)題的計(jì)算復(fù)雜性分析有一個(gè)共同的客觀尺度。n3個(gè)基本計(jì)算模型：n隨機(jī)存取機(jī)RAM(Random Access

2、Machine)；n隨機(jī)存取存儲(chǔ)程序機(jī)RASP(Random Access Stored Program Machine)n圖靈機(jī)(Turing Machine)。n這3個(gè)計(jì)算模型在計(jì)算能力上是等價(jià)的，但在計(jì)算速度上是不同的。49.1.1 隨機(jī)存取機(jī)RAM1、RAMRAM的結(jié)構(gòu)的結(jié)構(gòu)59.1.1 隨機(jī)存取機(jī)RAM2、RAMRAM程序程序 一個(gè)RAM程序定義了從輸入帶到輸出帶的一個(gè)映射?？梢詫?duì)這種映射關(guān)系作2種不同的解釋。解釋一：把解釋一：把RAMRAM程序看成是計(jì)算一個(gè)函數(shù)程序看成是計(jì)算一個(gè)函數(shù)若一個(gè)RAM程序P總是從輸入帶前n個(gè)方格中讀入n個(gè)整數(shù)x1，x2，xn，并且在輸出帶的第一個(gè)方格上輸

3、出一個(gè)整數(shù)y后停機(jī)，那么就說(shuō)程序P計(jì)算了函數(shù)f(xf(x1 1，x x2 2，x xn n)=y )=y 解釋二：把解釋二：把RAMRAM程序當(dāng)作一個(gè)語(yǔ)言接受器。程序當(dāng)作一個(gè)語(yǔ)言接受器。將字符串S=a1a2an放在輸入帶上。在輸入帶的第一個(gè)方格中放入符號(hào)a1，第二個(gè)方格中放入符號(hào)a2，第n個(gè)方格中放入符號(hào)an。然后在第n+1個(gè)方格中放入0，作為輸入串的結(jié)束標(biāo)志符。如果一個(gè)RAM程序P讀了字符串S及結(jié)束標(biāo)志符0后，在輸出帶的第一格輸出一個(gè)1并停機(jī)，就說(shuō)程序P接受字符串S。 69.1.1 隨機(jī)存取機(jī)RAM3、 RAMRAM程序的耗費(fèi)標(biāo)準(zhǔn)程序的耗費(fèi)標(biāo)準(zhǔn)標(biāo)準(zhǔn)一：均勻耗費(fèi)標(biāo)準(zhǔn)標(biāo)準(zhǔn)一：均勻耗費(fèi)標(biāo)準(zhǔn)在均勻耗

4、費(fèi)標(biāo)準(zhǔn)下，每條RAM指令需要一個(gè)單位時(shí)間；每個(gè)寄存器占用一個(gè)單位空間。以后除特別注明，RAM程序的復(fù)雜性將按照均勻耗費(fèi)標(biāo)準(zhǔn)衡量。 標(biāo)準(zhǔn)二：對(duì)數(shù)耗費(fèi)標(biāo)準(zhǔn)標(biāo)準(zhǔn)二：對(duì)數(shù)耗費(fèi)標(biāo)準(zhǔn)對(duì)數(shù)耗費(fèi)標(biāo)準(zhǔn)是基于這樣的假定，即執(zhí)行一條指令的耗費(fèi)與以二進(jìn)制表示的指令的操作數(shù)長(zhǎng)度成比例。在RAM計(jì)算模型下，假定一個(gè)寄存器可存放一個(gè)任意大小的整數(shù)。因此若設(shè)l(i)是整數(shù)i所占的二進(jìn)制位數(shù)，則 001|log)(iiiil79.1.2 隨機(jī)存取存儲(chǔ)程序機(jī)RASP1、RASPRASP的結(jié)構(gòu)的結(jié)構(gòu)RASP的整體結(jié)構(gòu)類似于RAM，所不同的是RASP的程序是存儲(chǔ)在寄存器中的。每條RASP指令占據(jù)2個(gè)連續(xù)的寄存器。第一個(gè)寄存器存放操作

5、碼的編碼，第二個(gè)寄存器存放地址。RASP指令用整數(shù)進(jìn)行編碼。 2、RASPRASP程序程序的復(fù)雜性的復(fù)雜性不管是在均勻耗費(fèi)標(biāo)準(zhǔn)下，還是在對(duì)數(shù)耗費(fèi)標(biāo)準(zhǔn)下，RAM程序和RASP程序的復(fù)雜性只差一個(gè)常數(shù)因子。在一個(gè)計(jì)算模型下T(n)時(shí)間內(nèi)完成的輸入-輸出映射可在另一個(gè)計(jì)算模型下模擬，并在kT(n)時(shí)間內(nèi)完成。其中k是一個(gè)常數(shù)因子?？臻g復(fù)雜性的情況也是類似的。 89.1.3 圖靈機(jī)99.1.3 圖靈機(jī) 根據(jù)有限狀態(tài)控制器的當(dāng)前狀態(tài)及每個(gè)讀寫頭讀到的帶符號(hào)，圖靈機(jī)的一個(gè)計(jì)算步可實(shí)現(xiàn)下面3個(gè)操作之一或全部。 (1)改變有限狀態(tài)控制器中的狀態(tài)。 (2)清除當(dāng)前讀寫頭下的方格中原有帶符號(hào)并寫上新的帶符號(hào)。 (

6、3)獨(dú)立地將任何一個(gè)或所有讀寫頭，向左移動(dòng)一個(gè)方格(L)或向右移動(dòng)一個(gè)方格(R)或停在當(dāng)前單元不動(dòng)(S)。 k帶圖靈機(jī)可形式化地描述為一個(gè)7元組(Q，T，I，b，q0，qf)，其中:(1)Q是有限個(gè)狀態(tài)的集合。 (2)T是有限個(gè)帶符號(hào)的集合。(3)I是輸入符號(hào)的集合，IT。(4)b是唯一的空白符，bT-I。(5)q0是初始狀態(tài)。 (6)qf是終止(或接受)狀態(tài)。(7)是移動(dòng)函數(shù)。它是從QTk的某一子集映射到Q (TL，R，S)k的函數(shù)。 109.1.3 圖靈機(jī)圖靈機(jī)M的時(shí)間復(fù)雜性T(n)是它處理所有長(zhǎng)度為n的輸入所需的最大計(jì)算步數(shù)。如果對(duì)某個(gè)長(zhǎng)度為n的輸入，圖靈機(jī)不停機(jī)，T(n)對(duì)這個(gè)n值無(wú)定

7、義。 圖靈機(jī)的空間復(fù)雜性S(n)是它處理所有長(zhǎng)度為n的輸入時(shí)，在k條帶上所使用過(guò)的方格數(shù)的總和。如果某個(gè)讀寫頭無(wú)限地向右移動(dòng)而不停機(jī)，S(n)也無(wú)定義。 與RAM模型類似，圖靈機(jī)既可作為語(yǔ)言接受器，也可作為計(jì)算函數(shù)的裝置。 119.2 P類與NP類問(wèn)題n一般地說(shuō)，將可由多項(xiàng)式時(shí)間算法求解的問(wèn)題看作是易處理的問(wèn)題，而將需要超多項(xiàng)式時(shí)間才能求解的問(wèn)題看作是難處理的問(wèn)題。n有許多問(wèn)題，從表面上看似乎并不比排序或圖的搜索等問(wèn)題更困難，然而至今人們還沒(méi)有找到解決這些問(wèn)題的多項(xiàng)式時(shí)間算法，也沒(méi)有人能夠證明這些問(wèn)題需要超多項(xiàng)式時(shí)間下界。n在圖靈機(jī)計(jì)算模型下，這類問(wèn)題的計(jì)算復(fù)雜性至今未知。n為了研究這類問(wèn)題的

8、計(jì)算復(fù)雜性，人們提出了另一個(gè)能力更強(qiáng)的計(jì)算模型，即非確定性圖靈機(jī)計(jì)算模型，簡(jiǎn)記為NDTM(Nondeterministic Turing Machine)。n在非確定性圖靈機(jī)計(jì)算模型下，許多問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)求解。129.2.1 非確定性圖靈機(jī)非確定性圖靈機(jī)非確定性圖靈機(jī)（ NDTMNDTM ）：一個(gè)k帶的非確定性圖靈機(jī)M是一個(gè)7元組：(Q，T，I，b，q0，qf)。與確定性圖靈機(jī)不同的是非確定性圖靈機(jī)允許移動(dòng)函數(shù)具有不確定性具有不確定性，即對(duì)于QTk中的每一個(gè)值(q;x1,x2,xk)，當(dāng)它屬于的定義域時(shí)，Q(TL，R，S)k中有唯一的一個(gè)子集子集(q;x1,x2,xk)與之對(duì)應(yīng)?？梢栽?/p>

9、(q;x1,x2,xk)中隨意選定一個(gè)值作為它的函數(shù)值。在圖靈機(jī)計(jì)算模型中，移動(dòng)函數(shù)是單值的是單值的，即對(duì)于QTk中的每一個(gè)值，當(dāng)它屬于的定義域時(shí)，Q(TL，R，S)k中只有唯一的值與之對(duì)應(yīng)，稱這種圖靈機(jī)為確定性圖靈機(jī)確定性圖靈機(jī)，簡(jiǎn)記為DTMDTM(Deterministic Turing Machine)。 139.2.2 P類與NP類語(yǔ)言 P類和NP類語(yǔ)言的定義： P=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)多項(xiàng)式時(shí)間內(nèi)被一臺(tái)DTMDTM所接受的語(yǔ)言 NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDTMNDTM所接受的語(yǔ)言由于一臺(tái)確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時(shí)間內(nèi)被

10、確定性圖靈機(jī)接受的語(yǔ)言也可在多項(xiàng)式時(shí)間內(nèi)被非確定性圖靈機(jī)接受。故P P NP NP。 149.2.2 P類與NP類語(yǔ)言 NPNP類語(yǔ)言舉例類語(yǔ)言舉例無(wú)向圖的團(tuán)問(wèn)題無(wú)向圖的團(tuán)問(wèn)題。 該問(wèn)題的輸入是一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖G=(V，E)和一個(gè)整數(shù)k。要求判定圖G是否包含一個(gè)k頂點(diǎn)的完全子完全子圖圖( (團(tuán)團(tuán)) )，即判定是否存在VV，|V|=k，且對(duì)于所有的u，vV，有(u，v)E。 若用鄰接矩陣表示圖G，用二進(jìn)制串表示整數(shù)k，則團(tuán)問(wèn)題的一個(gè)實(shí)例可以用長(zhǎng)度為 的二進(jìn)位串表示。因此，團(tuán)問(wèn)題可表示為語(yǔ)言： CLIQUE=w#v|w，v0，1*，以w為鄰接矩陣的圖G有一個(gè)k頂點(diǎn)的團(tuán)，其中v是k的二進(jìn)制表示

11、。 1log2kn159.2.2 P類與NP類語(yǔ)言 接受該語(yǔ)言CLIQUE的非確定性算法非確定性算法：用非確定性選擇指令選出包含k個(gè)頂點(diǎn)的候選頂點(diǎn)子集V，然后確定性地檢查該子集是否是團(tuán)問(wèn)題的一個(gè)解。算法分為3個(gè)階段： 算法的第一階段將輸入串w#v分解，并計(jì)算出n= ，以及用v表示的整數(shù)k。若輸入不具有形式w#v或|w|不是一個(gè)平方數(shù)就拒絕該輸入。顯而易見(jiàn)，第一階段可 在時(shí)間內(nèi)完成。| w)(2nO 在算法的第二階段中，非確定性地選擇V的一個(gè)k元子集VV。 算法的第三階段是確定性地檢查V的團(tuán)性質(zhì)。若V是一個(gè)團(tuán)則接受輸入，否則拒絕輸入。這顯然可以在 時(shí)間內(nèi)完成。因此，整個(gè)算法的時(shí)間復(fù)雜性為 。)(

12、4nO)(4nO非確定性算法在多項(xiàng)式時(shí)間內(nèi)接受語(yǔ)言CLIQUE，故CLIQUENP。 169.2.3 多項(xiàng)式時(shí)間驗(yàn)證 VP=L|L*，為一有限字符集，存在一個(gè)多項(xiàng)式p和一個(gè)多項(xiàng)式時(shí)間驗(yàn)證算法A(X，Y)使得對(duì)任意X*，XL當(dāng)且僅當(dāng)存在Y*，|Y|p(|X|)且A(X，Y)=1。 多項(xiàng)式時(shí)間可驗(yàn)證語(yǔ)言類VP可定義為： 定理定理9-19-1：VP=NP。 例如(哈密頓回路問(wèn)題哈密頓回路問(wèn)題)：一個(gè)無(wú)向圖G含有哈密頓回路嗎? 無(wú)向圖G的哈密頓回路是通過(guò)G的每個(gè)頂點(diǎn)恰好一次的簡(jiǎn)單回路。可用語(yǔ)言HAM-CYCLE 定義該問(wèn)題如下：HAM-CYCLE=G|G含有哈密頓回路 179.3 NP完全問(wèn)題nPNP

13、。n直觀上看，P類問(wèn)題是確定性計(jì)算模型下的易解問(wèn)題類，而NP類問(wèn)題是非確定性計(jì)算模型下的易驗(yàn)證問(wèn)題類。n大多數(shù)的計(jì)算機(jī)科學(xué)家認(rèn)為NP類中包含了不屬于P類的語(yǔ)言，即PNP。nNP完全問(wèn)題有一種令人驚奇的性質(zhì)，即如果一個(gè)NP完全問(wèn)題能在多項(xiàng)式時(shí)間內(nèi)得到解決，那么NP中的每一個(gè)問(wèn)題都可以在多項(xiàng)式時(shí)間內(nèi)求解，即P=NP。n目前還沒(méi)有一個(gè)NP完全問(wèn)題有多項(xiàng)式時(shí)間算法。189.3.1 多項(xiàng)式時(shí)間變換 定義：定義：語(yǔ)言L是NP完全的當(dāng)且僅當(dāng) (1)LNP； (2)對(duì)于所有LNP有L p L。 如果有一個(gè)語(yǔ)言L滿足上述性質(zhì)(2)，但不一定滿足性質(zhì)(1)，則稱該語(yǔ)言是NPNP難難的。所有NP完全語(yǔ)言構(gòu)成的語(yǔ)言類

14、稱為NPNP完全完全語(yǔ)言類語(yǔ)言類，記為NPCNPC。 設(shè) ， 是2個(gè)語(yǔ)言。所謂語(yǔ)言 能在多項(xiàng)式時(shí)間內(nèi)變換為語(yǔ)言 (簡(jiǎn)記為 p )是指存在映身f: ，且f滿足： (1)有一個(gè)計(jì)算f的多項(xiàng)式時(shí)間確定性圖靈機(jī)； (2)對(duì)于所有x ，x ，當(dāng)且僅當(dāng)f(x) 。 *11L*22L1L2L1L2L*2*11L2L*1199.3.1 多項(xiàng)式時(shí)間變換 定理定理9-29-2：設(shè)L是NP完全的，則 (1)LP當(dāng)且僅當(dāng)PNP； (2)若Lp ，且 NP，則 是NP完全的。 1L1L1L定理的定理的(2)(2)可用來(lái)可用來(lái)證明問(wèn)題的證明問(wèn)題的NPNP完全完全性。但前提是：要性。但前提是：要有第一個(gè)有第一個(gè)NPNP完全

15、問(wèn)完全問(wèn)題題L L。209. 3.2 一些典型的NP完全問(wèn)題部分NP完全問(wèn)題樹21 迄今為止，所有的NP完全問(wèn)題都還沒(méi)有多項(xiàng)式時(shí)間算法。對(duì)于這類問(wèn)題，通?？刹扇∫韵聨追N解題策略。(1)只對(duì)問(wèn)題的特殊實(shí)例求解(2)用動(dòng)態(tài)規(guī)劃法或分支限界法求解 (3)用概率算法求解 (4)只求近似解(5)用啟發(fā)式方法求解 9.4 NP完全問(wèn)題的近似算法229.4.1 近似算法的性能 若一個(gè)最優(yōu)化問(wèn)題的最優(yōu)值為c*，求解該問(wèn)題的一個(gè)近似算法求得的近似最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值為c，則將該近似算法的性能比近似算法的性能比定義為= 。在通常情況下，該性能比是問(wèn)題輸入規(guī)模n的一個(gè)函數(shù)(n)，即 (n)。cccc*,*maxc

16、ccc*,*max該近似算法的相對(duì)誤差近似算法的相對(duì)誤差定義為= 。若對(duì)問(wèn)題的輸入規(guī)模n，有一函數(shù)(n)使得 (n)，則稱(n)為該近似算法的相對(duì)誤差界近似算法的相對(duì)誤差界。近似算法的性能比(n)與相對(duì)誤差界(n)之間顯然有如下關(guān)系：(n)(n)(n)-1(n)-1。 *ccc *ccc 239.4.2 頂點(diǎn)覆蓋問(wèn)題的近似算法 問(wèn)題描述：無(wú)向圖G=(V,E)的頂點(diǎn)覆蓋是它的頂點(diǎn)集V的一個(gè)子集VV，使得若(u,v)是G的一條邊，則vV或uV。頂點(diǎn)覆蓋V的大小是它所包含的頂點(diǎn)個(gè)數(shù)|V|。 VertexSet approxVertexCoverapproxVertexCover ( Graph g

17、) cset=； e1=g.e； while (e1 != ) 從e1中任取一條邊(u,v)； cset=csetu,v； 從e1中刪去與u和v相關(guān)聯(lián)的所有邊； return c CsetCset用來(lái)存儲(chǔ)頂點(diǎn)用來(lái)存儲(chǔ)頂點(diǎn)覆蓋中的各頂點(diǎn)。初覆蓋中的各頂點(diǎn)。初始為空，不斷從邊集始為空，不斷從邊集e1e1中選取一邊中選取一邊( (u,v)u,v)，將邊的端點(diǎn)加入將邊的端點(diǎn)加入csetcset中，并將中，并將e1e1中已被中已被u u和和v v覆蓋的邊刪去，覆蓋的邊刪去，直至直至csetcset已覆蓋所有已覆蓋所有邊。即邊。即e1e1為空。為空。 249.4.2 頂點(diǎn)覆蓋問(wèn)題的近似算法 圖圖( (a)

18、a)(e)(e)說(shuō)明說(shuō)明了算法的運(yùn)行過(guò)程了算法的運(yùn)行過(guò)程及結(jié)果。及結(jié)果。( (e)e)表示表示算法產(chǎn)生的近似最算法產(chǎn)生的近似最優(yōu)頂點(diǎn)覆蓋優(yōu)頂點(diǎn)覆蓋csetcset，它由頂點(diǎn)它由頂點(diǎn)b,c,d,e,f,gb,c,d,e,f,g所組所組成。成。( (f)f)是圖是圖G G的一的一個(gè)最小頂點(diǎn)覆蓋，個(gè)最小頂點(diǎn)覆蓋，它只含有它只含有3 3個(gè)頂點(diǎn)：個(gè)頂點(diǎn)：b,db,d和和e e。 算法approxVertexCoverapproxVertexCover的性能比為2。 259.4.3 旅行售貨員問(wèn)題近似算法 問(wèn)題描述：給定一個(gè)完全無(wú)向圖G=(V,E)，其每一邊(u,v)E有一非負(fù)整數(shù)費(fèi)用c(u,v)。要找出

19、G的最小費(fèi)用哈密頓回路。 比如，費(fèi)用函數(shù)c往往具有三角不等式性質(zhì)三角不等式性質(zhì)，即對(duì)任意的3個(gè)頂點(diǎn)u,v,wV，有：c(u,w)c(u,v)+c(v,w)。當(dāng)圖G中的頂點(diǎn)就是平面上的點(diǎn)，任意2頂點(diǎn)間的費(fèi)用就是這2點(diǎn)間的歐氏距離時(shí)，費(fèi)用函數(shù)c就具有三角不等式性質(zhì)。 旅行售貨員問(wèn)題的一些特殊性質(zhì)特殊性質(zhì)：261 滿足三角不等式的旅行售貨員問(wèn)題滿足三角不等式的旅行售貨員問(wèn)題 對(duì)于給定的無(wú)向圖G，可以利用找圖圖G G的最小生成樹的最小生成樹的算法設(shè)計(jì)找近似最優(yōu)的旅行售貨員回路的算法。 void approxTSPapproxTSP (Graph g) (1)選擇g的任一頂點(diǎn)r； (2)用Prim算法找

20、出帶權(quán)圖g的一棵以r為根的最小生成樹T； (3)前序遍歷樹T得到的頂點(diǎn)表L； (4)將r加到表L的末尾，按表L中頂點(diǎn)次序組成回路H，作為計(jì)算結(jié)果返回； 當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，算法找出的旅行售貨員回路的費(fèi)用不會(huì)超過(guò)最優(yōu)旅行售貨員回路費(fèi)用的2倍。 27( (b)b)表示找到的最小生成表示找到的最小生成樹樹T T；( (c)c)表示對(duì)表示對(duì)T T作前序作前序遍歷的次序；遍歷的次序；(d)(d)表示表示L L產(chǎn)產(chǎn)生的哈密頓回路生的哈密頓回路H H；(e)(e)是是G G的一個(gè)最小費(fèi)用旅的一個(gè)最小費(fèi)用旅行售貨員回路。行售貨員回路。 282 一般一般的的旅行售貨員問(wèn)題旅行售貨員問(wèn)題 在費(fèi)用函數(shù)不一定

21、滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問(wèn)題的多項(xiàng)式時(shí)間近似算法，除非P=NPP=NP。換句話說(shuō)，若PNP，則對(duì)任意常數(shù)1，不存在性能比為的解旅行售貨員問(wèn)題的多項(xiàng)式時(shí)間近似算法。 299.4.4 集合覆蓋問(wèn)題的近似算法 問(wèn)題描述：給定一個(gè)完全無(wú)向圖G=(V,E)，其每一邊(u,v)E有一非負(fù)整數(shù)費(fèi)用c(u,v)。要找出G的最小費(fèi)用哈密頓回路。 集合覆蓋問(wèn)題的一個(gè)實(shí)例X,F由一個(gè)有限集X及X的一個(gè)子集族F組成。子集族F覆蓋了有限集X。也就是說(shuō)X中每一元素至少屬于F中的一個(gè)子集，即X= 。對(duì)于F中的一個(gè)子集CF，若C中的X的子集覆蓋了X，即X= ，則稱C覆蓋了X。集合覆蓋問(wèn)題就是

22、要找出F中覆蓋X的最小子集C*，使得 |C*|=min|C|CF且C覆蓋X FSSCSS309.4.4 集合覆蓋問(wèn)題的近似算法集合覆蓋問(wèn)題舉例：用用1212個(gè)黑點(diǎn)表示集個(gè)黑點(diǎn)表示集合合X X。F=S1,S2,S3,S4,SF=S1,S2,S3,S4,S5,S6,5,S6,，如圖所示。如圖所示。容易看出，對(duì)于這容易看出，對(duì)于這個(gè)例子，最小集合個(gè)例子，最小集合覆蓋為：覆蓋為：C=S3,S4,S5,C=S3,S4,S5,。 319.4.4 集合覆蓋問(wèn)題的近似算法集合覆蓋問(wèn)題近似算法貪心算法 算法的循環(huán)體最多算法的循環(huán)體最多執(zhí)行執(zhí)行min|X|min|X|，|F|F|次。次。而循環(huán)體內(nèi)的計(jì)算顯然而循環(huán)

23、體內(nèi)的計(jì)算顯然可在可在O(|X|F|)O(|X|F|)時(shí)間內(nèi)完時(shí)間內(nèi)完成。因此，算法的計(jì)算成。因此，算法的計(jì)算時(shí)間為時(shí)間為O(|X|F|min|X|O(|X|F|min|X|，|F|)|F|)。由此即知，該算由此即知，該算法是一個(gè)多項(xiàng)式時(shí)間算法是一個(gè)多項(xiàng)式時(shí)間算法。法。 Set greedySetCovergreedySetCover (X,F) U=X； C=； while (U !=) 選擇F中使|SU|最大的子集S； U=U-S； C=CS； return C； 329.4.5 子集和問(wèn)題的近似算法 問(wèn)題描述：設(shè)子集和問(wèn)題的一個(gè)實(shí)例為S,t。其中，S=x1，x2，xn是一個(gè)正整數(shù)的集合，t是一個(gè)正整數(shù)。子集和問(wèn)題判定是否存在S的一個(gè)子集S1，使得 。txSx 1331 子集和問(wèn)題的指數(shù)時(shí)間算法int exactSubsetSumexactSubsetSum (S,t) int n=|S|； L0=0； for (int i=1；i=n；i+) Li=mergeLists(Li-1,Li-1+Si)； 刪去Li中超過(guò)t的元素； return max