【計(jì)算機(jī)算法基礎(chǔ)】貪心方法

第三章貪心方法

3.1一般方法

1.問(wèn)題的一般特征

問(wèn)題有n個(gè)輸入，問(wèn)題的解是由這n個(gè)輸入的某個(gè)子集組成，這個(gè)子

集必須滿足某些事先給定的條件。

-約束條件：子集必須滿足的條件；

-可行解：滿足約束條件的子集；可行解可能不唯一；

■目標(biāo)函數(shù)：用來(lái)衡量可行解優(yōu)劣的標(biāo)準(zhǔn)，一般以函數(shù)的形式給出；

■最優(yōu)解：能夠使目標(biāo)函數(shù)取極值（極大或極小）的可行解。

分類：根據(jù)描述問(wèn)題約束條件和目標(biāo)函數(shù)的數(shù)學(xué)模型的特性和問(wèn)題的

求解方法的不同，可分為：線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)

劃等。

——最優(yōu)化問(wèn)題求解

貪心方法：一種改進(jìn)的分級(jí)的處理方法，可對(duì)滿足上述特征的某些問(wèn)

題方便地求解。

2.貪心方法的一般策略

問(wèn)題的一般特征：?jiǎn)栴}的解是由n個(gè)輸入的、滿足某些事先給定的

條件的子集組成。

1)一般方法

根據(jù)題意，選取一種度量標(biāo)準(zhǔn)。然后按照這種度量標(biāo)準(zhǔn)對(duì)n個(gè)輸入

排序，并按序一次輸入一個(gè)量。

如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一

起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中。否則，將當(dāng)前

輸入合并到部分解中從而得到包含當(dāng)前輸入的新的部分解。

這一處理過(guò)程一直持續(xù)到n個(gè)輸入都被考慮完畢，則記入最優(yōu)解集

合中的輸入子集構(gòu)成這種量度意義下的問(wèn)題的最優(yōu)解

貪心方法:這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)處理方法

稱為貪心方法

注：

＞貪心解=最優(yōu)解

＞直接將目標(biāo)函數(shù)作為量度標(biāo)準(zhǔn)也不一定能夠得到問(wèn)題的最優(yōu)解

＞使用貪心策略求解的關(guān)鍵是選取能夠得到問(wèn)題最優(yōu)解的量度標(biāo)準(zhǔn)。

3,貪心方法的抽象化控制描述

procedureGREEDY(A,n)

〃A(1:n)包含n個(gè)輸入〃

solution一①〃將解向量solution初始化為空〃

fori<—1tondo

x—SELECT(A)〃按照度量標(biāo)準(zhǔn)，從A中選擇一個(gè)輸入，

其值賦予x并將之從A中刪除〃

ifFEASIBLE(solution,x)then〃判定x是否可以包含在當(dāng)前解向量

中，即是否能共同構(gòu)成可行解〃

solution<—UNION(solution,x)〃將x和當(dāng)前的解向量合并成

新的解向量，并修改目標(biāo)函數(shù)〃

endif

repeat

return

endGREEDY

3.2背包問(wèn)題

1.問(wèn)題的描述

已知FI種物品具有重量四儼2,…,Wj和效益值（PiR,…,PJ，及一個(gè)

可容納M重量的背包；設(shè)當(dāng)物品i全部或一部分X放入背包將得到Pi為的效

益，這里，OWX,<1,Pi>0o

問(wèn)題：采用怎樣的裝包方法才能使裝入背包的物品的總效益最大？

分析：

①裝入背包的總重量不能超過(guò)M

②如果所有物品的總重量不超過(guò)M,即則把所有的物

品都裝入背包中將獲得最大可能的效益值

③如果物品的總重量超過(guò)了M,則將有物品不能（部分/全部）裝

入背包中。由于OWxiWl,所以可以把物品的一部分裝入背包，故最終

背包中可剛好裝入重量為M的若干物品（整體或一部分）。這種情況下，

如果背包沒(méi)有被裝滿，則顯然不能獲得最大的效益值。

目標(biāo)：使裝入背包的物品的總效益達(dá)到最大。

問(wèn)題的形式描述

目標(biāo)函數(shù):

EPiJ

\<i<n

約束條件:

Zwixi-M

\<i<n

0<x,<1,p.>0,w.>0,1<z<n

可行解：滿足上述約束條件的任一(Xi，X2，…,XJ都是問(wèn)題

的一個(gè)可行解——可行解可能為多個(gè)。

(x1,x2,...,Xn)稱為問(wèn)題的一個(gè)解向量

最優(yōu)解：能夠使目標(biāo)函數(shù)取最大值的可行解是問(wèn)題的最優(yōu)解

——最優(yōu)解也可能為多個(gè)。

例3.1背包問(wèn)題的實(shí)例

設(shè)，n=3,M=20,

。

(Pi，p21p3)=(25,24,15),(W15W2,W3)=(18,15,10)

可能的可行解如下:

x

(X15X2JX3)SPii

①(1/2,1/3,1/4)16.524.25〃沒(méi)有裝滿背包〃

②(1,2/15,0)2028.2

③(0,2/3,1)2031

④(0,1,1/2)2031.5

2.貪心策略求解

度量標(biāo)準(zhǔn)的選擇：三種不同的選擇

D以目標(biāo)函數(shù)作為度量

即，每裝入一件物品，就使背包獲得最大可能的效益增量。

該度量標(biāo)準(zhǔn)下的處理規(guī)則是：

?按效益值的非增次序?qū)⑽锲芬患胤湃氲奖嘲?/p>

?如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿背包：如

果該物品的一部分不滿足獲得最大效益增量的度量標(biāo)準(zhǔn)，則在剩下的物

品種選擇可以獲得最大效益增量的其它物品，將它或其一部分裝入背包。

如：若AM=2,背包外還剩兩件物品i,j,且有0=4,Wj=4)和(9

=3,Wj=2),則下一步應(yīng)選擇j而非i放入背包：

p/2=2<Pj=3

實(shí)例分析（例3.1）

???p1>p2>p3

???首先將物品1放入背包，此時(shí)％=1,背包獲得Pi=25的效益增量，同時(shí)

背包容量減少w1=18個(gè)單位，剩余空間AM二2。

其次考慮物品2和3。就AM=2而言有，只能選擇物品2或3的一部分裝入

背包。

物品2：若X2=2/15,則p2X2=16/5=3.1

物品3：若X3=2/10,則P3X3=3

為使背包的效益有最大的增量，應(yīng)選擇物品2的2/15裝包，即

X2=2/15

最后，背包裝滿，AM=0,物品3不裝包，即X3=0o

背包最終可以獲得效益值=x1p1+x2p2+x3p3

=28.2（次優(yōu)解，非問(wèn)題的最優(yōu)解）

2）以容量作為度量標(biāo)準(zhǔn)

以目標(biāo)函數(shù)作為度量標(biāo)準(zhǔn)所存在的問(wèn)題：盡管背包的效

益值每次得到了最大的增加，但背包容量也過(guò)快地被消耗掉

了，從而不能裝入“更多”的物品。

改進(jìn)：讓背包容量盡可能慢地消耗，從而可以盡量裝入

“較多”的物品。

即，新的標(biāo)準(zhǔn)是：以容量作為度量

該度量標(biāo)準(zhǔn)下的處理規(guī)則：

?按物品重量的非降次序?qū)⑽锲费b入到背包；

?如果正在考慮的物品放不進(jìn)去，則只取其一部分裝

滿背包；

實(shí)例分析（例3.1）

*.*w3<w2<w1

???首先將物品3放入背包，此時(shí)X3=1,背包容量減少W3=10個(gè)單

位，還剩余空間AM=10。同時(shí)，背包獲得P3=15的效益增量。

其次考慮物品2。就AM=10而言有，也只能選擇物品2的一部分

裝入背包。下一步將放入物品2的10/15裝包，即

X2=10/15=2/3

最后，背包裝滿AM=0,物品1將不能裝入背包，故x[=0。

背包最終可以獲得效益值=x1p1+x2P2+X3p3

=31（次優(yōu)解，非問(wèn)題的最優(yōu)解）

存在的問(wèn)題：效益值沒(méi)有得到“最大程度”的增加

3）最優(yōu)的度量標(biāo)準(zhǔn)

影響背包效益值得因素：

■背包的容量M

-放入背包中的物品的重量及其可能帶來(lái)的效益值

可能的策略是：在背包效益值的增長(zhǎng)速率和背包容量消耗速率之間

取得平衡，即每次裝入的物品應(yīng)使它所占用的每一單位容量能獲得當(dāng)前

最大的單位效益。

在這種策略下的量度是：已裝入的物品的累計(jì)效益值與所用容量之

比。

故，新的量度標(biāo)準(zhǔn)是：每次裝入要使累計(jì)效益值與所用容量的比值

有最多的增加（首次裝入）和最小的減小（其后的裝入）。

此時(shí)，將按照物品的單位效益值：Pj/Wj比值的非增次序考慮。

實(shí)例分析（例3.1）

Pi/w1<p3/w3<p2/w2

???首先，將物品2放入背包，此時(shí)X2=1,背包容量減少W2=15

個(gè)單位，還剩余空間AM=5。同時(shí)，背包獲得P2=24的

效益增量。

其次，在剩下的物品1和3中，應(yīng)選擇物品3,且就AM=5而言有,

只能放入物品3的一部分到背包中。即

x3=5/10=1/2

最后，背包裝滿AM=0,物品1將不能裝入背包，故x[=00

最終可以獲得的背包效益值=Pi+x2P2+X3p3

=31.5（最優(yōu)解）

3.背包問(wèn)題的貪心求解算法

算法3.2背包問(wèn)題的貪心算法

procedureGREEDY-KNAPSACK(P,W,M,X,n)

〃P(1:n)和W(1:n)分別含有按P(i)/W(gP(i+1)/W(i+1)排序的n

件物品的效益值和重量。M是背包的容量大小，而X(1:n)是解

向量〃

realP(1:n),W(1:n),X(1:n),M,cu;

integerl,n

x—o〃將解向量初始化為0〃

cu<—M〃cu是背包的剩余容量〃

fori<-1tondo

ifW(i)>cuthenexitendif

X(i)I

cu<—cu-W(i)

repeat

ifi<nthenX(i)<—cu/W(i)endif

endGREEDY-KNAPSACK

4.最優(yōu)解的證明

即證明：由第三種策略所得到的貪心解是問(wèn)題的最優(yōu)解。

最優(yōu)解的含義：在滿足約束條件的情況下，使目標(biāo)函數(shù)取極（大或

?。┲档目尚薪狻?/p>

貪心解是可行解，故只需證明：貪心解可使目標(biāo)函數(shù)取得極值。

證明的基本思想：

將此貪心解與（假設(shè)中的）任一最優(yōu)解相比較。

?如果這兩個(gè)解相同，則顯然貪心解就是最優(yōu)解。

?如果這兩個(gè)解不同，就設(shè)法去找兩者開(kāi)始不同的第一個(gè)分量位置i,

然后設(shè)法用貪心解的這個(gè)為去替換最優(yōu)解對(duì)應(yīng)的分量，并證明最優(yōu)

解在分量代換前后總的效益值沒(méi)有任何變化（且不違反約束條件）。

?然后比較二者。若還不同，則反復(fù)進(jìn)行代換，直到代換后產(chǎn)生的

“最

優(yōu)解”與貪心解完全一樣。

?在上述代換中，最優(yōu)解的效益值沒(méi)有任何損失，從而證明貪心解的

效益值與代換前后最優(yōu)解的效益值相同。即，貪心解如同最優(yōu)解一

樣可取得目標(biāo)函數(shù)的最大/最小值。

從而得證：該貪心解即是問(wèn)題的最優(yōu)解。

定理3.1如果p「wep2/w2>..>pjwn，則算法GREEDY-

KNAPSACK對(duì)于給定的背包問(wèn)題實(shí)例生成一個(gè)最優(yōu)解。

證明：

設(shè)X=(x］，x2,xj是GREEDY-KNAPSACK所生成的貪心

解。

①如果所有的為都等于1,則顯然X就是問(wèn)題的最優(yōu)解。否則，

②設(shè)j是使為人的最小下標(biāo)。由算法的執(zhí)行過(guò)程可知，

?Xj=11<i<j,

?0<Xj<1

?Xj=Oj<i<n

假設(shè)Y是問(wèn)題的最優(yōu)解：Y=（yl5y2,...,yn）且有：

2w，=M

?若X=Y,則X就是最優(yōu)解。否則，

?X和Y至少在1個(gè)分量上存在不同。

設(shè)k是使得y^Xk的最小下標(biāo)，則有yk<Xk?？煞忠韵虑?/p>

況說(shuō)明：

a）若kvj,則Xk=1。因?yàn)閄Q從而有yk<xk

b）若k=j,由于=M，且對(duì)14iVj,有％=毛=1,而對(duì)j

〈區(qū)n,有為=0；故此時(shí)若y/Xk，貝1J將有與丫是可

行解相矛盾。而y/Xk，所以yk<Xk

c）若k>j,則z叼%>M,不能成立

在Y中作以下調(diào)整：將丫卜增加到Xk，因?yàn)閥k<Xk，為保持解的可行性，

必須從d+力…,yj中減去同樣多的量。設(shè)調(diào)整后的解為Z=(Z1，Z2,…，ZJ,

其中Zj=Xj,1<i<k,且有：匯叫(匕-々)="(2--)

k<i<n

z的效益值有：

ZPA=E巴匕+（。-九）卬*?！?卬&-一￡（乂一苒）叫/匕

l=k<i<>n

NN0，匕+［（-yQ"一Z（匕一N,）R,/明

\<i<nk.<i<n

=EPM

差值=0

由以上分析得，

■若ZPKi>ZPly,,貝LlY將不是最優(yōu)解；

1

■若2PK*=z？匕，則或者Z=X,貝JX就是最優(yōu)解；

■或者ZHX,則重復(fù)以上替代過(guò)程，或者證明Y不是最優(yōu)

解，或者把Y轉(zhuǎn)換成X,從而證明X是最優(yōu)解

3.3帶有限期的作業(yè)排序

1.問(wèn)題描述

假定在一臺(tái)資源無(wú)約束的機(jī)器上處理n個(gè)作業(yè)，每個(gè)作業(yè)

均可在單位時(shí)間內(nèi)完成；同時(shí)每個(gè)作業(yè)諸B有一個(gè)截至期限d/O,

當(dāng)且僅當(dāng)作業(yè)i在其截至期限以前被完成時(shí)，則獲得R>0的效益。

問(wèn)題：求這n個(gè)作業(yè)的一個(gè)子集J,其中的所有作業(yè)都可

在其截至期限內(nèi)完成。——J是問(wèn)題的一個(gè)可行解。

可行解J中的所有作業(yè)的效益之和是，具有最大效

益值之和的可行解是該問(wèn)題的最優(yōu)解。ZP,

ZGJ

分析:

目標(biāo)函數(shù)：ZP,

ieJ

約束條件：所有的作業(yè)都應(yīng)在其期限之前完成

>如果所有的作業(yè)都能在其期限之內(nèi)完成則顯然可以獲得

當(dāng)前最大效益值；

>否則，將有作業(yè)無(wú)法完成—決策應(yīng)該執(zhí)行哪些作業(yè)，以

獲得最大可能的效益值。

例3.2n=4,(Pi，p2,p3,p4)=(100,10,15,20)

(drd2,d3,d4)=(2,1,2,1)o

可行解如下表所示：

可行解處理順序效益值

①

②(1)1100%

(2)210

③d,d

④(3)31524

(4)420

⑤di，d

(1,2)1103

⑥2,1

(1,3)1,3或3,1115

⑦

(1,4)4,1120

⑧

(2,3)2,325

⑨

(3,4)4,335

問(wèn)題的最優(yōu)解是⑦。所允許的處理次序是：先處理作業(yè)4

再處理作業(yè)1。

1.帶有限期的作業(yè)排序算法

1）度量標(biāo)準(zhǔn)的選擇

以目標(biāo)函數(shù)Zp,作為量度。

ZGJ

量度標(biāo)準(zhǔn)：下一個(gè)要計(jì)入的作業(yè)將是使得在滿足所產(chǎn)生的J是

一個(gè)可行解的限制條件下讓Ep,得到最大增加的

iwJ

作業(yè)。

處理規(guī)則：■按Pi的非增次序來(lái)考慮這些作業(yè)；

?同時(shí)因受作業(yè)期限的限制，必須為作業(yè)安排合理

的處理順序。

例：例3.2求解

①首先令J=RP1<P4<P3<P2

②作業(yè)1具有當(dāng)前前最大效益值，且｛1｝是可行解，所以作

業(yè)1計(jì)入J（一般情況下，假定至少有一個(gè)時(shí)間單元）。

③在剩下的作業(yè)中，作業(yè)4具有最大效益值，且｛1,4｝也是

可行解，故作業(yè)4計(jì)入J,即J=｛1,4｝；

④考慮｛1,3,4｝和｛1,2,4｝均不能構(gòu)成新的可行解，作業(yè)3和2

將被舍棄。

故，最后的J=｛1,4｝,加工順序是：4,1o

最終效益值=120（問(wèn)題的最優(yōu)解）

2)作業(yè)排序算法的概略描述

算法3.3

procedureGREEDY-JOB(D,J,n)

//作業(yè)按PAP22…NPn的次序輸入，它們的期限值D(廬1,

1<i<n,n>1oJ是在它們的截止期限前完成的作業(yè)的集合〃

J―{1}〃用作業(yè)序號(hào)代表作業(yè)〃

fori—2tondo

ifJU{i}的所有作業(yè)能在它們的截止期限前完成

thenJ-JU{i}

endif

repeat

endGREEDY-JOB

2.最優(yōu)解證明

定理3.2算法3.3對(duì)于作業(yè)排序問(wèn)題的解是問(wèn)題的一個(gè)最優(yōu)解

證明：

設(shè)J是由算法3.3所得的作業(yè)集合—貪心解，

I是一個(gè)最優(yōu)解的作業(yè)集合。

①若l=J,貝IJJ就是最優(yōu)解；否則

②I手J,則至少存在兩個(gè)作業(yè)a和b,使得a^J

且ae/,b曰且人七/。（為什么）

并設(shè)a是這樣的一個(gè)具有最高效益值的作業(yè)

（由算法的處理規(guī)則可得：對(duì)于在I中而不在J中的作業(yè)所有b,有：pa>pb）

設(shè)Sj和S1分別是J和I的可行的調(diào)度表。因?yàn)镴和I都是可行

解，故這樣的調(diào)度表一定存在；

設(shè)i是既屬于J又屬于I地一個(gè)作業(yè)，并設(shè)i在調(diào)度表Sj中的

調(diào)度時(shí)刻是［t,t+1］,而在S|中的調(diào)度時(shí)刻是［t'，

在Sj和S1中作如下調(diào)整：

?若t<t',則將Sj中在［t'，t'+1］時(shí)刻調(diào)度的那個(gè)作業(yè)

（如果有的話）與i相交換。如果J中在％f+1］時(shí)刻沒(méi)有作

業(yè)調(diào)度，則直接將i移到［匕f+1］調(diào)度。——新的調(diào)度表也是

可行的。一?、

Sj：……I...........k……

6：I…?..........］………一

tt'

?若t'vt,則在S1中作類似的調(diào)換，即將SI中在［t,t+1］時(shí)刻

調(diào)度的那個(gè)作業(yè)（如果有的話）與湘交換。如果I中在［t,

t+1］時(shí)刻沒(méi)有作業(yè)調(diào)度，則直接將i移到［t,t+1］調(diào)度。——同

樣，新的調(diào)度表也是可行的。

Sj：…………

S|：……...........h.....

----1-------------1-------

ft

對(duì)J和I中共有的所有作業(yè)作上述的調(diào)整。設(shè)調(diào)整后得到

的調(diào)度表為S'j和S'l，則在S'j和S'l中J和I中所有的共有作業(yè)將

在相同時(shí)間被調(diào)度。

設(shè)a在S'j中的調(diào)度時(shí)刻是％,ta+1],b是SI中該時(shí)刻調(diào)度

的作業(yè)，則有Pa^Pb（為什么？）。

Sj：...................a...................

品..........?..........一

ta

在S'l中，去掉作業(yè)b,而去調(diào)度作業(yè)a,得到的是作業(yè)集

合kd-）u{a}的一個(gè)可行的調(diào)度表,且F的效益值不小

于I的效益值。而I'中比I少了一個(gè)與J不同的作業(yè)。

重復(fù)上述的轉(zhuǎn)換，可使I在不減效益值的情況下轉(zhuǎn)換成J。

從而J至少有和I一樣的效益值。所以J也是最優(yōu)解。

證畢。

3.如何判斷J的可行性

方法一：枚舉法，檢驗(yàn)J中作業(yè)所有可能的排列，對(duì)于任一種次序排

列的作業(yè)序列，判斷這些作業(yè)是否能夠在其期限前完成

——若J中有k個(gè)作業(yè)，則將要檢查k!個(gè)序列

判斷策略：

對(duì)于一個(gè)給定作業(yè)處理序列o=i-2…ik，由于作業(yè)匕完成的最早

時(shí)間是j,因此只要判斷出o排列中的每個(gè)作業(yè)的期限有djj2j,就

可得知o是一個(gè)允許的調(diào)度序列，從而J是一可行解。

反之，如果o排列中有一個(gè)作業(yè)有djjVj,則。將是一個(gè)行不通

的調(diào)度序列，因?yàn)橹辽僮鳂I(yè)勾不能在其期限之前完成。

方法二：檢查J中作業(yè)的一個(gè)特定序列就可判斷J的可行性：

這一特定序列是按照作業(yè)期限的非降次序排列的作業(yè)序列

定理3.3設(shè)J是k個(gè)作業(yè)的集合，。=可2…ik是J中作業(yè)的一種排

列,它使得功了加工…4ik。則

J是一個(gè)可行解，當(dāng)且僅當(dāng)J中的作業(yè)可以按照o

的次序而又不違反任何一個(gè)期限的情況來(lái)處理。

證明：

①如果J中的作業(yè)可以按照。的次序而又不違反任何一個(gè)

作業(yè)期限的情況來(lái)處理，貝IJJ是一個(gè)可行解

②現(xiàn)證若J是一個(gè)可行解，。是否代表一個(gè)可行的調(diào)度序

列？

?/J是可行解

???必存在一可行的調(diào)度序列。'=切2..小，使得備詞，

1<j<ko

★若。=。'，則。即是可行的調(diào)度序列。否則，

★c#o',令a是使得1丸的最小下標(biāo)（如下圖）

設(shè)L=ia。則有：

b>a且dra>drb

故，在o'中調(diào)換q與％,所得的新序列?！?SR2…Sk的處理次

序不違反任何一個(gè)期限，而中位置a及a之前的作業(yè)均與。相同。

重復(fù)上述過(guò)程，則可將。'轉(zhuǎn)換成。且不違反任何一個(gè)期限，

故。是一個(gè)可行的調(diào)度序列

故定理得證。

4.帶有限期的作業(yè)排序算法的實(shí)現(xiàn)

對(duì)當(dāng)前正在考慮的作業(yè)j,按限期大小采用一種“插入排序”的方式,

嘗試將其“插入”到一個(gè)按限期從小到大順序構(gòu)造的作業(yè)調(diào)度序列中，

以此判斷是否能夠?qū)⒆鳂I(yè)j合并到當(dāng)前部分解J中：

▼如果有合適的插入位置，則插入到序列中，形成新的可行解序列。

▼否則，舍棄該作業(yè)。

具體如下：

假設(shè)n個(gè)作業(yè)已經(jīng)按照效益值從大到小的次序，即PAP2N…NPn的順

序排列好，每個(gè)作業(yè)可以在單位時(shí)間內(nèi)完成，并具有相應(yīng)的時(shí)間期限加

且至少有一個(gè)單位時(shí)間可以執(zhí)行作業(yè)

首先,將作業(yè)1計(jì)入部分解J中，止匕時(shí)J是可行的；

然后，依次考慮作業(yè)2到n。假設(shè)已經(jīng)處理了i-1個(gè)作業(yè)，其中有k個(gè)作

業(yè)計(jì)入了部分解J中：J(1),J(2),…,J(k),且有

D(J(1))<D(J(2))<..<D(J(k))

對(duì)當(dāng)前正在考慮的作業(yè)i,將D(i)依次和D(J(k)),D(J(k-1)),…，D(J(1))相

比較。若

1)找到位置q：使得

★D(i)<D(J(1)),q<l<k,且

★D(J(q))<D(i)

★q<D(i)

此時(shí),若D(J⑴)>1,qVlWk,即q位置之后的所有作業(yè)均可

推遲一個(gè)單位時(shí)間執(zhí)行，而又不違反各自的執(zhí)行期限。

執(zhí)行“移位”處理：將q位置之后的所有作業(yè)后移一位，將作

業(yè)i插入到位置q+1處，從而得到一個(gè)包含k+1個(gè)作業(yè)的新的可行解。

2)若找不到這樣的位置q,作業(yè)i將被舍棄。

對(duì)i之后的其它作業(yè)重復(fù)上述過(guò)程，直到n個(gè)作業(yè)處理完畢。最后J中所包含的

作業(yè)集合是此時(shí)算法的貪心解，根據(jù)定理3.2,也是問(wèn)題的最優(yōu)解。

算法3.4帶有限期和效益的單位時(shí)間的作業(yè)排序貪心算法

procedureJS(D,J,n,k)

//n>1o作業(yè)已按3邛2?…邛n的順序排序。D(1),...,D(n)是期限值,J(i)是最優(yōu)解中的第i個(gè)作

業(yè)，1<i<ko終止時(shí)，D(J(i))<D(J(i+1)),1<i<k//

integerD(0:n),J(0:n),i,k,n,r

D(0)-J(0)-0〃初始化〃

k—1;J⑴-1〃計(jì)入作業(yè)1〃

fori<-2tondo〃按p的非增次序考慮作業(yè)i。找i的插入位置并檢查可行性〃

r<-k「另一退出條件是

whileD(J(r))>D(i)andD(J(r))Nrdo//D(j(r))>r//

r—r-1〃這樣的r有D(J(r))>r//D(J(r))>D(i)而

repeatD(J(r))=r

IfD(J(r))<D(i)andD(i)>rthen〃把i插入到J中〃

fori<—ktor+1by-1do

J(i+1)-J(i)〃將插入點(diǎn)的作業(yè)后移一位〃

repeat

J(r+1)<-i;k<-k+1〃將i計(jì)入J中〃

endif

repeat

endJS

計(jì)算時(shí)間分析

fori<—2tondo今將循環(huán)n-1次-------------------------------------①

r<—k

whileD(J(r))>D(i)andD(J(r))#do9至多循環(huán)k次，

k是當(dāng)前計(jì)入J中的作業(yè)數(shù)

1-T--------------------------②

r<—r-1

repeat

IfD(J(r))<D(i)andD(i)>rthen

fori*-ktor+1by-1do力循環(huán)k-r次，r是插入點(diǎn)之前的位置

最壞情況下循環(huán)k次，插入到最頭部一一③

J(i+1)-J(i)

repeat

J(r+1)—l;k-k+1

endif

repeat

設(shè)s是最終計(jì)入J中的作業(yè)數(shù)，則算法JS所需要的總時(shí)間是O(sn)。sWn,故

2

最壞情況:TJS=0(n),特例情況：Pi二d『n-i+1,IWiWn

最好情況：TJS=0(n),特例情況：Pi=n-i+l,d『i,IWiWn

6.一種“更快”的作業(yè)排序問(wèn)題

判定作業(yè)i可行的另一種方法：

對(duì)于作業(yè)i,若還沒(méi)有給i分配處理時(shí)間，則分配給它時(shí)間片

［。-1,可，其中。是盡量取大且為空的時(shí)間片。

即：盡量推遲作業(yè)i的處理時(shí)間。這樣在安排作業(yè)處理次序時(shí)

不必每有一個(gè)作業(yè)加入就需移動(dòng)J中已有的作業(yè)。

如果不存在這樣的時(shí)間片，作業(yè)i被舍棄。

（如何按照該方法改進(jìn)算法？）

使用不相交集合的UNION和FIND算法（見(jiàn)1.4.3節(jié)），可以

將JS的計(jì)算時(shí)間降低到數(shù)量級(jí)接近0（n）。

（略）

3.4最優(yōu)歸并模式

1.問(wèn)題的描述

1)兩個(gè)文件的歸并問(wèn)題

兩個(gè)已知文件的一次歸并所需的計(jì)算時(shí)間=0(兩個(gè)文件的元素總數(shù))

例：

n個(gè)記錄的文件——

+-----k(n+m)個(gè)記錄的文件

m個(gè)記錄的文件——0(n+m)

2)多個(gè)文件的歸并

已知n個(gè)文件，將它們歸并成一個(gè)單一的文件

例：假定文件X1，X2,X3,X4,采用兩兩歸并的方式，可能的歸并模

式有：

①

XI+X2=YI+X3=Y2+X4=Y3

②X1+X2=

+一Y3

X3+X4=Y2

二路歸并模式：每次僅作兩個(gè)文件的歸并；當(dāng)有多個(gè)文件

時(shí)，采用兩兩歸并的模式，最終得到一個(gè)完整的記錄文件。

二元?dú)w并樹(shù)：二路歸并模式的歸并過(guò)程可以用一個(gè)二元樹(shù)

的形式描述，稱之為二元?dú)w并樹(shù)。

歸并樹(shù)的構(gòu)造

X（60）

?外結(jié)點(diǎn)：n個(gè)原始文件

?內(nèi)結(jié)點(diǎn)：一次歸并后得到的文件

（50）10X?在兩路歸并模式下，每個(gè)內(nèi)結(jié)點(diǎn)

3剛好有兩個(gè)兒子，代表把它的兩個(gè)

兒子表示的文件歸并成其本身所代

表的文件

X30

120X2

號(hào)數(shù)字代表文件葭

/又

★不同的歸并順序所需的計(jì)算時(shí)間是不同的。

例3.5已知Xi%%是分別為30、20、10個(gè)記錄長(zhǎng)度的已分類文件。

將這3個(gè)文件歸并成長(zhǎng)度為60的文件。可能的歸并過(guò)程和相應(yīng)的記錄移動(dòng)

次數(shù)如下：

X1-]__________.

X2,移動(dòng)5。次------------總移動(dòng)次數(shù)：110次

X,移動(dòng)60次

X3

X2移動(dòng)30次總移動(dòng)次數(shù)：90次

X1

問(wèn)題：采用怎樣的歸并順序才能使歸并過(guò)程中元素的移

動(dòng)次數(shù)最小（或執(zhí)行的速度最快）

2.貪心求解

1）度量標(biāo)準(zhǔn)的選擇

★任意兩個(gè)文件的歸并所需的元素移動(dòng)次數(shù)與這兩個(gè)文件的長(zhǎng)度

之和成正比；

★度量：目標(biāo)函數(shù)（元素移動(dòng)數(shù)之和）；

★度量標(biāo)準(zhǔn)：每次歸并使目標(biāo)函數(shù)有最小的增加；

★處理規(guī)則：每次選擇長(zhǎng)度最小的兩個(gè)文件進(jìn)行歸并。

F4F3

(F1JF2JF3JF4JF5)=(20,30,10,5,30)

2）目標(biāo)函數(shù)的定義

目標(biāo)：元素移動(dòng)的次數(shù)最少

分析：為得到歸并樹(shù)根結(jié)點(diǎn)表示的歸并文件，外部結(jié)點(diǎn)中每個(gè)

文件的記錄需要移動(dòng)的次數(shù)=該外部結(jié)點(diǎn)到根的距離，即根到該外

部結(jié)點(diǎn)路徑的長(zhǎng)度。如，

則中所有記錄在整個(gè)歸并過(guò)程中移動(dòng)的總量=|FJ3

帶權(quán)外部路徑長(zhǎng)度：記4是由根到代表文件寫的外部結(jié)點(diǎn)的距

離，q是4的長(zhǎng)度，則這棵樹(shù)所代表的歸并過(guò)程中元素移動(dòng)總量是:

，稱為這棵樹(shù)的帶權(quán)外部路徑長(zhǎng)度

l<i<n

最優(yōu)的二路歸并模式：與一棵具有最小帶權(quán)外部路徑長(zhǎng)度的二

元?dú)w并樹(shù)相對(duì)應(yīng)。

算法3.6生成二元?dú)w并樹(shù)的算法

procedureTREE(L,n)

〃L是n個(gè)單結(jié)點(diǎn)的二元樹(shù)表〃

fori^1ton-1do

callGETNODE(T)〃構(gòu)造一顆新樹(shù)T〃

LCHILD(T)-LEAST(L)〃從表L中選當(dāng)前根WEIGHT最小的樹(shù)，

并從中刪除〃

RCHILD(T)-LEAST(L)

WEIGHT(T)^WEIGHT(LCHILD(T))+WEIGHT(RCHILD(T))

callINSERT(L,T)〃將歸并的樹(shù)T加入到表L中〃

repeat

return(LEAST(L))〃此時(shí)，L中的樹(shù)即為歸并的結(jié)果〃

endTREE

例3.6已知六個(gè)初始文件，長(zhǎng)度分別為：2,3,5,7,9,13。

采用算法TREE,各階段的工作狀態(tài)如圖所示：

迭代L

0百⑸回萬(wàn)百而

in

co寸

時(shí)間分析

1)循環(huán)體：n-1次

2)L以有序序列表示

LEAST(L):O⑴

INSERT(LJ):0(n)

總時(shí)間:0(n2)

3)L以min-堆表示

LEAST(L):O(logn)

INSERT(LJ):O(logn)

總時(shí)間:O(nlogn)

3.最優(yōu)解的證明

定理3.4若L最初包含個(gè)單結(jié)點(diǎn)的樹(shù)，這些樹(shù)有WEIGHT值為

（q1,q2,...,qn）,則算法TREE對(duì)于具有這些長(zhǎng)度的n個(gè)文件生成一棵最優(yōu)的

二元?dú)w并樹(shù)。

證明：歸納法證明

①當(dāng)n=1時(shí)，返回一棵沒(méi)有內(nèi)部結(jié)點(diǎn)的樹(shù)。定理得證。

②假定算法對(duì)所有的9/2,…,qm），14mVn,生成一棵最優(yōu)二元?dú)w

并樹(shù)。

③對(duì)于Q假定＜qn，則和q2將是在for循環(huán)的第一次迭代中

首先選出的具有最小WEIGHT值的兩棵樹(shù)（的WEIGHT值）；如圖所示,

設(shè)T是由這樣的兩棵樹(shù)構(gòu)成的子樹(shù):

qiq2

■設(shè)「是一棵對(duì)于（q/2,…,q/的最優(yōu)二元?dú)w并樹(shù)。

■設(shè)P是T'中距離根最遠(yuǎn)的一個(gè)內(nèi)部結(jié)點(diǎn)。

若P的兩棵子樹(shù)不是q1和q2，則用q1和q2代換P當(dāng)前的子樹(shù)而

不會(huì)增加T'的帶權(quán)外部路徑長(zhǎng)度。

故，T應(yīng)是最優(yōu)歸并樹(shù)中的子樹(shù)。

則在T中用一個(gè)權(quán)值為q1+q2的外部結(jié)點(diǎn)代換T,得到的是一

棵關(guān)于&+q2,…,qJ最優(yōu)歸并樹(shù)丁'。

而由歸納假設(shè)，在用權(quán)值為q1+q2的外部結(jié)點(diǎn)代換了T之后，

過(guò)程TREE將針對(duì)（q1+q2,…,qj得到一棵最優(yōu)歸并樹(shù)。將T帶入該

樹(shù)，根據(jù)以上討論，將得到關(guān)于…,qj的最優(yōu)歸并樹(shù)。

故，TREE生成一棵關(guān)于…,q/的最優(yōu)歸并樹(shù)。

F(T)=F(T”)+qi+q2

則，

Fmin(T)=min(F(T))

=min(F(T”)+q1+q2)

=min(F(T"))++q?

=Fmin(T")++q2

5.k路歸并模式

>每次同時(shí)歸并k個(gè)文件。

>k元?dú)w并樹(shù)：可能需要增加“虛”結(jié)點(diǎn)，以補(bǔ)充不足的外

首B結(jié)點(diǎn)o

★如果一棵樹(shù)的所有內(nèi)部結(jié)點(diǎn)的度都為k,則外部結(jié)點(diǎn)

數(shù)n滿足nmod(k-1)=1

★對(duì)于滿足nmod(k—1)=1的整數(shù)n,存在一棵具有n

個(gè)外部結(jié)點(diǎn)的k元樹(shù)T,且T中所有結(jié)點(diǎn)的度為k。

至多需要增加k-2個(gè)外部結(jié)點(diǎn)。

>k路最優(yōu)歸并模式的貪心規(guī)則：每一步選取k個(gè)具有最小

長(zhǎng)度的文件歸并。

3.5最小生成樹(shù)

1.問(wèn)題的描述

生成樹(shù)：設(shè)G=(V,E)是一個(gè)無(wú)向連通圖。如果G的生

成子圖T=(V,E)是一棵樹(shù)，則稱T是G的一棵

生成樹(shù)(spanningtree).

最小生成樹(shù):帶有成本的圖的生成樹(shù)問(wèn)題

2.貪心策略

度量標(biāo)準(zhǔn)：選擇能使迄今為止所計(jì)入的邊的成本和有最小

增加的那條邊。

?Prim算法

?Kruskal算法

3.Prim算法

策略：使得迄今所選擇的邊的集合A構(gòu)成一棵樹(shù)；則將要計(jì)入到A中

的下一條邊(u,v),應(yīng)是E中一條當(dāng)前不在A中且使得AU{(u,v)}也是一棵

樹(shù)的最小成本邊。

邊成本

(1,2)10

(2,6)25

(3,6)15

(6,4)20

10

邊成本

(3,5)35

V(Tp)={123,4,5,6}

E(Tp)={(1,2),(2,6),(3,5),(4,6),(3,6)}

算法3.7Prim最小生成樹(shù)算法

procedurePRIM(E,COST,nJTJmincost)

//E是G的邊集。。。$丁("可是11結(jié)點(diǎn)圖6的成本鄰接矩陣，矩陣元素COST。,j)

是一個(gè)正實(shí)數(shù)，如果不存在邊(i,j),則為+8。計(jì)算一棵最小生成樹(shù)并把它作

為一個(gè)集合存放到數(shù)組T(1：n-1,2)中(T(i,1),T(i,2))是最小成本生成樹(shù)的一條邊。

最小成本生成樹(shù)的總成本最后賦給mincost〃

realCOST(n,n),mincost

integerNEAR(n),n,i,k,I,T(1:n-1,2)

(k,I)一具有最小成本的邊

mincost<—COST(k,l)

(T(I,1),T(I,2))~(k,l)

fori<-1tondo〃將NEAR置初值〃

ifCOST(i,l)<COST(i,k)thenNEAR(i)-I

elseNEAR⑴—k

endif

repeat

NEAR(k)―NEAR。)-0

fori^2ton-1do〃找T的其余n-2條邊〃

設(shè)j是NEAR(j)K0且COST(j,NEAR(j))最小的下標(biāo)

(T(i,1),T(i,2))~(j,NEAR(j))

mincost-mincost+COST(j,NEAR(j))

NEAR。)-0

fork—1tondo〃修改NEAR〃

ifNEAR(k)#0andCOST(k,NEAR(k))>COST(kJ)

thenNEAR(k)-j

endif

repeat

repeat

ifmincost>0°thenprint(fnospanningtree')endif

endPRIM

計(jì)算復(fù)雜性：0（H2）

4.Kruskal算法

（連通）圖的邊按成本的非降次序排列，下一條計(jì)入生成樹(shù)T中的邊

是還沒(méi)有計(jì)入的邊中具有最小成本、且和T中現(xiàn)有的邊不會(huì)構(gòu)成環(huán)路的邊。

①②③④⑤⑥

邊成本

(1,2)10

(3,6)15

(4,6)20

(2,6)25

4

6

10

邊成本

(3,5)35

V(TQ={123,4,5,6}

E(TK)={(1,2),(2,6),(3,5),(4,6),(3,6)}

算法3.9Kruskal算法

procedureKRUSKAL(E,COST,N,T,mincost)

〃G有n個(gè)結(jié)點(diǎn)，E是G的邊集。(：。$丁(11?是邊(11田的成本。T是最小成本生成

樹(shù)的邊集，mincost是它而版本〃

realmincost,COST(1:n,1:n);integerPARENT(1:n),T(1:n-1,2),n

以邊成本為元素構(gòu)造一個(gè)min堆

PARENT-1〃每個(gè)結(jié)點(diǎn)都在不同的集合中〃

i—mincost—0

whilei<n-1and堆非空do

從堆中刪去最小成本邊(u,v)并重新構(gòu)造堆

j—FIND(u);k-FIND(v)

if(j#k)theni<—i+1

T(i,1)-u;T(i,2)<-v

mincost—mincost+COST(u,v)

callUNION(j,k)

endif

repeat

ifiHn-1thenprint('nospanningtree')endif

return

endKRUSKAL

注：

?邊集以min-堆的形式保存，一條當(dāng)前最小成本邊可以在

O(loge)的時(shí)間內(nèi)找到;

?當(dāng)且僅當(dāng)圖G是不連通的，iWn-l；此時(shí)算法具有最壞

的執(zhí)行時(shí)間；

?算法的計(jì)算時(shí)間是O(eloge)

實(shí)驗(yàn)內(nèi)容

-單源最短路徑算法的完善和實(shí)現(xiàn)

-書上的單源最短路徑算法僅求出了從單源點(diǎn)到其它所有結(jié)點(diǎn)的最

短路徑長(zhǎng)度。在此基礎(chǔ)上，擴(kuò)充算法功能，使得新算法在找出這

些最短路徑長(zhǎng)度的同時(shí)，也能求出路徑上的結(jié)點(diǎn)序列。

要求：

-給出新算法的描述

■用C語(yǔ)言編寫該算法的程序

-用書上的實(shí)例（或自行設(shè)計(jì)測(cè)試數(shù)據(jù)）測(cè)試程序，輸出測(cè)試結(jié)果。

基本形式如下：

startendlengthnodeslist

Vi20ViV

v22

Vi30V1V4

v4

Vi80ViV2V3V5V6

v6

交實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)內(nèi)容、算法描述、程序設(shè)計(jì)、結(jié)果測(cè)試及分析等

3.6單源最短路徑

1.問(wèn)題描述

■最短路徑問(wèn)題：

?每對(duì)結(jié)點(diǎn)之間的路徑問(wèn)題

?特定線路下的最短路徑問(wèn)題

?單源最短路徑問(wèn)題等

■單源最短路徑問(wèn)題

已知一個(gè)n結(jié)點(diǎn)有向圖G=(V,E)和邊的權(quán)函數(shù)c(e),

求由G中某指定結(jié)點(diǎn)V。到其它各結(jié)點(diǎn)的最短路徑。

假定邊的權(quán)值為正。

■例3.10如圖所示。設(shè)V。是起始點(diǎn)，求V。到其它

各結(jié)點(diǎn)的最短路徑。

路徑長(zhǎng)度

⑴V0V210

(2)v0v2v325

(3)v0v2v3v145

⑷v0v445

注：路徑按照長(zhǎng)度的非降次序給出

2.貪心策略求解

1）度量標(biāo)準(zhǔn)

量度的選擇：迄今已生成的所有路徑長(zhǎng)度之和——為使之達(dá)

到最小，其中任意一條路徑都應(yīng)具有“最小”長(zhǎng)度：

假定已經(jīng)構(gòu)造了i條這樣的最短路徑，則下一條要構(gòu)造的路徑

應(yīng)是下一條最短的路徑。

處理規(guī)則：按照路徑長(zhǎng)度的非降次序依次生成從結(jié)點(diǎn)V。到

其它各結(jié)點(diǎn)的最短路徑。

例：

問(wèn)題：如何對(duì)尚未生成的路

v0^v2

徑長(zhǎng)度進(jìn)行排序，以確定其

v—>v—>v

023中最短者？

VQ-N2->Vg-

Voi

2）貪心算法

全設(shè)S是已經(jīng)對(duì)其生成了最短路徑的結(jié)點(diǎn)集合（包括v。）。

金對(duì)于當(dāng)前不在S中的結(jié)點(diǎn)w,記DIST（w）是從V。開(kāi)始，

只經(jīng)過(guò)S中的結(jié)點(diǎn)而在w結(jié)束的那條最短路徑的長(zhǎng)度。

O

則有,

wS

①如果下一條最短路徑是到結(jié)點(diǎn)u,則這條路徑是從結(jié)點(diǎn)V。出發(fā)，

在u處終止，且只經(jīng)過(guò)那些在S中的結(jié)點(diǎn)，即由V。至u的這條最短路徑上

的所有中間結(jié)點(diǎn)都是S中的結(jié)點(diǎn)，證明如下：

設(shè)w是這條路徑上的任意中間結(jié)點(diǎn)，則從V。到u的路徑也包含了一

條從V。到W的路徑，且其長(zhǎng)度小于從V。到U的路徑長(zhǎng)度。

Vo,Sps2,???,w,???,sm_pu

t

均在s中

根據(jù)生成規(guī)則：最短路徑是按照路徑長(zhǎng)度的非降次序生成的，因

此從V。到W的最短路徑應(yīng)該已經(jīng)生成。從而W也應(yīng)該在S中。

故,不存在不在s中的中間結(jié)點(diǎn)。

②所生成的下一條路徑的終點(diǎn)u必定是所有不在S內(nèi)的結(jié)點(diǎn)中具有

最小DIST(u)值的結(jié)點(diǎn)。

③如果選出了這樣結(jié)點(diǎn)U并生成了從V。到U的最短路徑之后，結(jié)點(diǎn)U將成為

S中的一個(gè)成員。此時(shí)，那些從V。出發(fā)，只經(jīng)過(guò)S中的結(jié)點(diǎn)并且在S外的結(jié)

點(diǎn)w處結(jié)束的最短路徑長(zhǎng)度可能會(huì)減小——DIST(w)的值變?。?/p>

這些長(zhǎng)度發(fā)生改變的路徑，必定是一條從％出發(fā)，經(jīng)過(guò)u然后到w的

更短的路徑。

★根據(jù)DIST(w)的定義，DIST(w)所表示的最短路徑上，所有中間

結(jié)點(diǎn)都在S中；故只考慮<u,w>￡E和右的情況

★對(duì)于從V。至w,且經(jīng)過(guò)最后一個(gè)中間結(jié)點(diǎn)為u的最短路徑，有：

DIST(w)=DIST(u)+c(u,w)

★隨著u的加入，DIST(w)調(diào)整為

DIST(w)=min(DIST(w),DIST(u)+c(u,w))

算法3.10生成最短路徑的貪心算法

procedureSHORTEST-PATHS(v,COST,DIST,n)

〃G是一個(gè)n結(jié)點(diǎn)有向圖，它由其成本鄰接矩陣COST(n,n)表示。DIST(j)被置

從結(jié)點(diǎn)v到結(jié)點(diǎn)j的最短路徑長(zhǎng)度，這里10"。DIST(v)被置成零〃

booleanS(1:n);realCOST(1:n,1:n),DIST(1:n)

integeru5v,n3num,i,w

fori—1tondo//將集合S初始化為空〃

S(i)<-0;DIST(i)-COST(vj)〃若<v,zE,則DIST(i)=8〃

repeat