算法設(shè)計與分析04貪心算法

第六章

貪心算法

主要內(nèi)容:6.1一般方法6.2背包問題6.3帶時限的作業(yè)排序6.4最佳歸并模式6.5最小生成樹

6.7多機(jī)調(diào)度問題6.6單源點(diǎn)最短路徑引言找零錢問題貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。最優(yōu)化問題（optimizationproblems）是指這樣一類問題，問題給定某些約束條件（constraint），滿足這些約束條件的問題解稱為可行解（feasiblesolution）。通常滿足約束條件的解不是惟一的。為了衡量可行解的好壞，問題還給出了某個數(shù)值函數(shù)，稱為目標(biāo)函數(shù)（objectivefunction），使目標(biāo)函數(shù)取最大（或最?。┲档目尚薪夥Q為最優(yōu)解（optimalsolution）。貪心法是通過分步?jīng)Q策（stepwisedecision）的方法來求解問題的。貪心法每一步上用作決策依據(jù)的選擇準(zhǔn)則被稱為最優(yōu)量度標(biāo)準(zhǔn)（optimizationcriterion）。在根據(jù)最優(yōu)量度標(biāo)準(zhǔn)選擇分量的過程中，還需要使用一個可行解判定函數(shù)。貪心策略并不是從整體上加以考慮的，它所做出的選擇只是當(dāng)前看似最佳選擇，必須進(jìn)一步證明該算法最終導(dǎo)致問題的一個整體最優(yōu)解。Greedy算法的基本思想求解最優(yōu)化問題的算法包含一系列步驟每一步都有一組選擇作出在當(dāng)前看來最好的選擇希望通過作出局部優(yōu)化選擇達(dá)到全局優(yōu)化選擇Greedy算法不一定總產(chǎn)生優(yōu)化解Greedy算法是否產(chǎn)生優(yōu)化解，需嚴(yán)格證明Greedy算法產(chǎn)生優(yōu)化解的條件Greedy-choice-propertyOptimalsubstructureGreedy算法的基本概念Greedy選擇性

Greedy選擇性

若一個優(yōu)化問題的全局優(yōu)化解可以通過

局部優(yōu)化選擇得到，則該問題稱為具有

Greedy選擇性.一個問題是否具有Greedy選擇性需證明

若一個優(yōu)化問題的優(yōu)化解包含它的

子問題的優(yōu)化解，則稱其具有優(yōu)化

子結(jié)構(gòu)優(yōu)化子結(jié)構(gòu)

與動態(tài)規(guī)劃方法的比較動態(tài)規(guī)劃方法可用的條件優(yōu)化子結(jié)構(gòu)子問題重疊性子問題空間小Greedy方法可用的條件優(yōu)化子結(jié)構(gòu)Greedy選擇性可用Greedy方法時，動態(tài)規(guī)劃方法可能不適用可用動態(tài)規(guī)劃方法時，Greedy方法可能不適用證明算法所求解的問題具有優(yōu)化子結(jié)構(gòu)證明算法所求解的問題具有Greedy選擇性證明算法確實(shí)按照Greedy選擇性進(jìn)行局部優(yōu)化選擇Greedy算法正確性證明方法【程序6－1】貪心法SolutionTypeGreedy(STypea[],intn){ SolutionTypesolution=; for(inti=0;i<n;i++){ STypex=Select(a); if(Feasiable(solution,x)) solution=Union(solution,x); } returnsolution;}6.2背包問題

6.2.1

問題描述

已知一個載重為M的背包和n件物品，第i件物品的重量為wi，如果將第i件物品全部裝入背包，將有收益pi，這里，wi>0，pi>0，0i<n。所謂背包問題是指求一種最佳裝載方案，使得收益最大。所以，背包問題是現(xiàn)實(shí)世界一個常見的最優(yōu)化問題。兩類背包問題:如果每一件物品不能分割，只能作為整體或者裝入背包，或者不裝入，稱為

0/1背包問題；如果物品是可以分割的，也就是允許將其中的一部分裝入背包為一般背包問題或簡稱背包問題。

6.2.2貪心法求解

背包問題

背包問題的解可以表示成一個n-元組：X=(x0,x1,,xn－1)，0xi1，0i<n，每個xi是第i件物品裝入背包中的部分。

判定可行解的約束條件是：

背包問題的最優(yōu)解必須使下列目標(biāo)函數(shù)取最大值：例6－1

設(shè)有載重能力M=20的背包，3件物品的重量為:（w0,w1,w2）=(18,15,10)，物品裝入背包的收益為：（p0,p1,p2）=(25,24,15)。2.貪心策略求解

度量標(biāo)準(zhǔn)的選擇：三種不同的選擇1）以目標(biāo)函數(shù)作為度量

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

該度量標(biāo)準(zhǔn)下的處理規(guī)則是：●按效益值的非增次序?qū)⑽锲芬患胤湃氲奖嘲?；●如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿背包：如果該物品的一部分不滿足獲得最大效益增量的度量標(biāo)準(zhǔn)，則在剩下的物品種選擇可以獲得最大效益增量的其它物品，將它或其一部分裝入背包。

如：若ΔM=2,背包外還剩兩件物品i,j，且有(pi＝4，wi＝4)和(pj＝3，wj＝2)，則下一步應(yīng)選擇j而非i放入背包：pi/2=2＜pj＝3實(shí)例分析（例3.1)∵p1＞p2＞p3∴首先將物品1放入背包，此時x1＝1，背包獲得p1＝25的效益增量，同時背包容量減少w1＝18個單位，剩余空間ΔM=2。

其次考慮物品2和3。就ΔM=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

最后，背包裝滿，

ΔM=0，物品3不裝包，即x3＝0

。

背包最終可以獲得效益值＝x1p1＋x2p2＋x3p3

＝28.2(次優(yōu)解,非問題的最優(yōu)解)2）以容量作為度量標(biāo)準(zhǔn)

以目標(biāo)函數(shù)作為度量標(biāo)準(zhǔn)所存在的問題：盡管背包的效益值每次得到了最大的增加，但背包容量也過快地被消耗掉了，從而不能裝入“更多”的物品。

改進(jìn)：讓背包容量盡可能慢地消耗，從而可以盡量裝入“較多”的物品。

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

該度量標(biāo)準(zhǔn)下的處理規(guī)則：●按物品重量的非降次序?qū)⑽锲费b入到背包；●如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿背包；實(shí)例分析（例3.1)∵w3＜w2＜w1∴首先將物品3放入背包，此時x3＝1，背包容量減少w3＝10個單位，還剩余空間ΔM=10。同時，背包獲得p3＝15的效益增量。

其次考慮物品2。就ΔM=10而言有，也只能選擇物品2的一部分裝入背包。下一步將放入物品2的10/15裝包，即

x2＝10/15＝2/3

最后，背包裝滿ΔM=0，物品1將不能裝入背包，故

x1＝0

。

背包最終可以獲得效益值＝x1p1＋x2p2＋x3p3

＝31(次優(yōu)解,非問題的最優(yōu)解)

存在的問題：效益值沒有得到“最大程度”的增加3）最優(yōu)的度量標(biāo)準(zhǔn)

影響背包效益值得因素：

背包的容量M

放入背包中的物品的重量及其可能帶來的效益值

可能的策略是：在背包效益值的增長速率和背包容量消耗速率之間取得平衡，即每次裝入的物品應(yīng)使它所占用的每一單位容量能獲得當(dāng)前最大的單位效益。

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

故，新的量度標(biāo)準(zhǔn)是：每次裝入要使累計效益值與所用容量的比值有最多的增加（首次裝入）和最小的減小（其后的裝入）。

此時，將按照物品的單位效益值：pi/wi比值的非增次序考慮。實(shí)例分析（例3.1)∵p1/w1＜p3/w3＜p2/w2∴首先，將物品2放入背包，此時x2＝1，背包容量減少w2＝15

個單位，還剩余空間ΔM=5。同時，背包獲得p2＝24的

效益增量。

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

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

。即

x3＝5/10＝1/2

最后，背包裝滿ΔM=0，物品1將不能裝入背包，故x1＝0

。

最終可以獲得的背包效益值＝x1p1＋x2p2＋x3p3

＝31.5(最優(yōu)解)3.背包問題的貪心求解算法算法4.2背包問題的貪心算法procedureGREEDY－KNAPSACK(P,W,M,X,n)//P(1:n)和W(1:n)分別含有按P(i)/W(i)≥P(i＋1)/W(i＋1)排序的n

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

向量//realP(1:n),W(1:n),X(1:n),M,cu;integerI,nX←0//將解向量初始化為0//cu←M//cu是背包的剩余容量//fori←1tondoifW(i)>cuthenexitendifX(i)←1cu←cu-W(i)repeatifi≤nthenX(i)←cu/W(i)endifendGREEDY-KNAPSACK4.最優(yōu)解的證明

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

最優(yōu)解的含義：在滿足約束條件的情況下，使目標(biāo)函數(shù)取極（大或?。┲档目尚薪狻?/p>

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

證明的基本思想：

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

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

●如果這兩個解不同，就設(shè)法去找兩者開始不同的第一個分量位置i，然后設(shè)法用貪心解的這個xi去替換最優(yōu)解對應(yīng)的分量

，并證明最優(yōu)解在分量代換前后總的效益值沒有任何變化(且不違反約束條件)。

●然后比較二者。若還不同，則反復(fù)進(jìn)行代換，直到代換后產(chǎn)生的“最優(yōu)解”與貪心解完全一樣。

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

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

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

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

定理6.1如果p1/w1≥p2/w2≥…≥pn/wn,則算法GREEDY-KNAPSACK對于給定的背包問題實(shí)例生成一個最優(yōu)解。證明：

設(shè)X=(x1,x2,…,xn)是GREEDY-KNAPSACK所生成的貪心解。①如果所有的xi都等于1,則顯然X就是問題的最優(yōu)解。否則，②設(shè)j是使xi≠1的最小下標(biāo)。由算法的執(zhí)行過程可知，xi=11≤i＜j,0≤xj＜1xi=0j＜i≤n

假設(shè)Y是問題的最優(yōu)解：Y=(y1,y2,…,yn)

且有：●若X＝Y(jié)，則X就是最優(yōu)解。否則，●X和Y至少在1個分量上存在不同。

設(shè)k是使得yk≠xk的最小下標(biāo)，則有yk＜xk?？煞忠韵虑闆r說明：a)若k<j，則xk=1。因?yàn)閥k≠xk,從而有yk＜xkb)若k=j，由于

，且對1≤i＜j，有yi=xi=1,而對j＜i≤n,有xi＝0；故此時若yk＞xk，則將有

，與Y是可行解相矛盾。而yk≠xk,所以yk＜xkc)若k＞j，則

，不能成立

在Y中作以下調(diào)整：將yk增加到xk，因?yàn)閥k＜xk,為保持解的可行性，必須從(yk+1,…,yn)中減去同樣多的量。設(shè)調(diào)整后的解為Z=(z1,z2,…,zn)，其中zi＝xi，1≤i≤k，且有：Z的效益值有：差值＝0由以上分析得，若

，則Y將不是最優(yōu)解；若

，則或者Z=X，則X就是最優(yōu)解；或者Z≠X，則重復(fù)以上替代過程，或者證明Y不是最優(yōu)解，或者把Y轉(zhuǎn)換成X，從而證明X是最優(yōu)解

【程序6－2】背包問題的貪心算法

template<classT>classKnapsack{public: Knapsack(intmSize,floatcap,float*wei,T*prof);voidGreedyKnapsack(float*x);……private:floatm,*w;T*p;intn;};template<classT>voidKnapsack<T>::GreedyKnapsack(float*x){//前置條件：w[i]已按p[i]/w[i]的非增次序排列floatu=m;for(inti=0;i<n;i++)x[i]=0; for(i=0;i<n;i++){ if(w[i]>u)break; x[i]=1.0; u=u-w[i]; } if(i<=n)x[i]=u/w[i];}

6.3帶時限的作業(yè)排序

6.3.1

問題描述設(shè)有一個單機(jī)系統(tǒng)、無其它資源限制且每個作業(yè)運(yùn)行相等時間，不妨假定每個作業(yè)運(yùn)行1個單位時間?，F(xiàn)有n個作業(yè)，每個作業(yè)都有一個截止期限di>0，di為整數(shù)。如果作業(yè)能夠在截止期限之內(nèi)完成，可獲得pi>0的收益。問題要求得到一種作業(yè)調(diào)度方案，該方案給出作業(yè)的一個子集和該作業(yè)子集的一種排列，使得若按照這種排列次序調(diào)度作業(yè)運(yùn)行，該子集中的每個作業(yè)都能如期完成，并且能夠獲得最大收益。也就是說這種作業(yè)調(diào)度是最優(yōu)的。

6.3.2貪心法求解

例6－2

設(shè)有4個作業(yè)，每個作業(yè)的時限為(d0,d1,d2,d3)=(2,1,2,1),收益為(p0,p1,p2,p3)=(100,10,15,27)。

6.3帶有限期的作業(yè)排序1.問題描述

假定在一臺資源無約束的機(jī)器上處理n個作業(yè)，每個作業(yè)均可在單位時間內(nèi)完成；同時每個作業(yè)i都有一個截至期限di>0,當(dāng)且僅當(dāng)作業(yè)i在其截至期限以前被完成時，則獲得pi>0的效益。

問題：求這n個作業(yè)的一個子集J，其中的所有作業(yè)都可在其截至期限內(nèi)完成。——J是問題的一個可行解。

可行解J中的

所有作業(yè)的效益之和是

，具有最大效益值之和的可行解是該問題的最優(yōu)解。分析：

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

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

如果所有的作業(yè)都能在其期限之內(nèi)完成則顯然可以獲得當(dāng)前最大效益值；

否則，將有作業(yè)無法完成——決策應(yīng)該執(zhí)行哪些作業(yè)，以獲得最大可能的效益值。例6.2n=4，(p1，p2，p3，p4)＝(100,10,15,20)(d1，d2，d3，d4)＝(2,1,2,1)。

可行解如下表所示：

問題的最優(yōu)解是⑦。所允許的處理次序是：先處理作業(yè)4再處理作業(yè)1?？尚薪馓幚眄樞蛐б嬷耽伲?）1100②（2）210③（3）315④（4）420⑤（1,2）2,1110⑥（1,3）1,3或3,1115⑦（1,4）4,1120⑧（2,3）2,325⑨（3,4）4,335t1t2d2,d4d1,d31.帶有限期的作業(yè)排序算法1)度量標(biāo)準(zhǔn)的選擇

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

作為量度。

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

一個可行解的限制條件下讓

得到最大增加的

作業(yè)。

處理規(guī)則：●按pi的非增次序來考慮這些作業(yè)；●同時因受作業(yè)期限的限制，必須為作業(yè)安排合理的處理順序。例：例6.2求解

①首先令J=Φ,p1＜p4＜p3＜p2 ②作業(yè)1具有當(dāng)前的最大效益值，且{1}是可行解，所以作業(yè)1計入J（一般情況下，假定至少有一個時間單元）。

③在剩下的作業(yè)中，作業(yè)4具有最大效益值，且{1,4}也是可行解，故作業(yè)4計入J，即J={1,4}；

④考慮{1,3,4}和{1,2,4}均不能構(gòu)成新的可行解，作業(yè)3和2將被舍棄。

故，最后的J={1,4}，加工順序是：4，1。

最終效益值＝120（問題的最優(yōu)解）2)作業(yè)排序算法的概略描述

算法6.3procedureGREEDY-JOB(D,J,n)//作業(yè)按p1≥p2≥…≥pn的次序輸入，它們的期限值D(i)≥1,1≤i≤n,n≥1。J是在它們的截止期限前完成的作業(yè)的集合//J←{1}//用作業(yè)序號代表作業(yè)//fori←2tondoifJ∪{i}的所有作業(yè)能在它們的截止期限前完成thenJ←J∪{i}endifrepeatendGREEDY-JOB2.最優(yōu)解證明定理6.2算法6.3對于作業(yè)排序問題的解是問題的一個最優(yōu)解證明：

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

I是一個最優(yōu)解的作業(yè)集合。①若I=J，則J就是最優(yōu)解；否則②，則至少存在兩個作業(yè)a和b，使得a∈J且,b∈I且

。（為什么）

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

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

設(shè)SJ和SI分別是J和I的可行的調(diào)度表。因?yàn)镴和I都是可行解，故這樣的調(diào)度表一定存在；

設(shè)i是既屬于J又屬于I地一個作業(yè)，并設(shè)i在調(diào)度表SJ中的調(diào)度時刻是[t，t+1]，而在SI中的調(diào)度時刻是[t’，t’+1]。

在SJ和SI中作如下調(diào)整：

●若t＜t’，則將SJ中在[t’，t’+1]時刻調(diào)度的那個作業(yè)（如果有的話）與i相交換。如果J中在[t’，t’+1]時刻沒有作業(yè)調(diào)度，則直接將i移到[t’，t’+1]調(diào)度?！碌恼{(diào)度表也是可行的?！璱.………………k…………h(huán).………………i………SJ：SI：tt’●若t’＜t，則在SI中作類似的調(diào)換，即將SI中在[t，t+1]時刻調(diào)度的那個作業(yè)（如果有的話）與i相交換。如果I中在[t，t+1]時刻沒有作業(yè)調(diào)度，則直接將i移到[t，t+1]調(diào)度?！瑯?，新的調(diào)度表也是可行的。

對J和I中共有的所有作業(yè)作上述的調(diào)整。設(shè)調(diào)整后得到的調(diào)度表為S’J和S’I，則在S’J和S’I中J和I中所有的共有作業(yè)將在相同時間被調(diào)度。……k.………………i…………i.………………h(huán)………SJ：SI：t’t

設(shè)a在S’J中的調(diào)度時刻是[ta,ta+1]，b是S’I中該時刻調(diào)度的作業(yè)，則有pa≥pb（為什么？）。

在S’I中，去掉作業(yè)b，而去調(diào)度作業(yè)a，得到的是作業(yè)集合I’=（I-）∪{a}的

一個可行的調(diào)度表，且I’的效益值不小于I的效益值。而I’中比I少了一個與J不同的作業(yè)。

重復(fù)上述的轉(zhuǎn)換，可使I在不減效益值的情況下轉(zhuǎn)換成J。從而J至少有和I一樣的效益值。所以J也是最優(yōu)解。

證畢?！?……….a…………………..………b……………SJ：SI：ta3.如何判斷J的可行性方法一：枚舉法，檢驗(yàn)J中作業(yè)所有可能的排列，對于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能夠在其期限前完成

——若J中有k個作業(yè)，則將要檢查k!個序列判斷策略：

對于一個給定作業(yè)處理序列σ＝i1i2…ik,由于作業(yè)ij完成的最早時間是j，因此只要判斷出σ排列中的每個作業(yè)的期限有dij≥j，就可得知σ是一個允許的調(diào)度序列，從而J是一可行解。

反之，如果σ排列中有一個作業(yè)有dij＜j,則σ將是一個行不通的調(diào)度序列，因?yàn)橹辽僮鳂I(yè)ij不能在其期限之前完成。方法二：檢查J中作業(yè)的一個特定序列就可判斷J的可行性：

這一特定序列是按照作業(yè)期限的非降次序排列的作業(yè)序列定理6.3設(shè)J是k個作業(yè)的集合，σ＝i1i2…ik是J中作業(yè)的一種排列，它使得di1≤di2≤…≤dik。則J是一個可行解，當(dāng)且僅當(dāng)J中的作業(yè)可以按照σ的次序而又不違反任何一個期限的情況來處理。證明：

①如果J中的作業(yè)可以按照σ的次序而又不違反任何一個作業(yè)期限的情況來處理，則J是一個可行解②現(xiàn)證若J是一個可行解，

σ是否代表一個可行的調(diào)度序列？

∵J是可行解∴必存在一可行的調(diào)度序列σ’＝r1r2…rk，使得drj≥j,1≤j≤k。

★

若σ＝σ’，則σ即是可行的調(diào)度序列。否則，

★

σ≠σ’，令a是使得ra≠ia的最小下標(biāo)（如下圖）σ＝i1i2…

ia

…

…

ic

…

ikσ’＝r1r2…

ra

…

rb

…rk設(shè)rb=ia。則有：

b＞a且

dra≥drb

故，在σ’中調(diào)換ra與rb，所得的新序列σ’’＝s1s2…sk的處理次序不違反任何一個期限，而σ’’中位置a及a之前的作業(yè)均與σ相同。

重復(fù)上述過程，則可將σ’轉(zhuǎn)換成σ且不違反任何一個期限，故σ是一個可行的調(diào)度序列

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

對當(dāng)前正在考慮的作業(yè)j，按限期大小采用一種“插入排序”的方式，嘗試將其“插入”到一個按限期從小到大順序構(gòu)造的作業(yè)調(diào)度序列中，以此判斷是否能夠?qū)⒆鳂I(yè)j合并到當(dāng)前部分解J中：

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

?否則，舍棄該作業(yè)。具體如下：

假設(shè)n個作業(yè)已經(jīng)按照效益值從大到小的次序，即p1≥p2≥…≥pn的順序排列好，每個作業(yè)可以在單位時間內(nèi)完成，并具有相應(yīng)的時間期限di；且至少有一個單位時間可以執(zhí)行作業(yè)

首先，將作業(yè)1計入部分解J中，此時J是可行的；

然后，依次考慮作業(yè)2到n。假設(shè)已經(jīng)處理了i-1個作業(yè)，其中有k個作業(yè)計入了部分解J中：J(1),J(2),…,J(k)，且有D(J(1))≤D(J(2))≤…≤D(J(k))

對當(dāng)前正在考慮的作業(yè)i,將D(i)依次和D(J(k)),D(J(k-1)),…，D(J(1))相比較。若1）找到位置q：使得

★D(i)＜D(J(l))，q＜l≤k，且

★D(J(q))＜D(i)★q＜D(i)

此時，若D(J(l))＞l,q＜l≤k,即q位置之后的所有作業(yè)均可

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

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

業(yè)i插入到位置q＋1處，從而得到一個包含k+1個作業(yè)的新的可行解。2）若找不到這樣的位置q，作業(yè)i將被舍棄。

對i之后的其它作業(yè)重復(fù)上述過程，直到n個作業(yè)處理完畢。

最后J中所包含的作業(yè)集合是此時算法的貪心解，根據(jù)定理3.2,也是問題的最優(yōu)解。算法6.4帶有限期和效益的單位時間的作業(yè)排序貪心算法procedureJS(D,J,n,k)//n≥1。作業(yè)已按p1≥p2≥…≥pn的順序排序。D(1),…,D(n)是期限值,J(i)是最優(yōu)解中的第i個作

業(yè)，1≤i≤k。終止時，D(J(i))≤D(J(i＋1))，1≤i＜k//integerD(0:n),J(0:n),i,k,n,rD(0)←J(0)←0//初始化//k←1;J(1)←1//計入作業(yè)1//fori←2tondo//按p的非增次序考慮作業(yè)i。找i的插入位置并檢查可行性//r←kwhileD(J(r))＞D(i)andD(J(r))≠rdo//D(J(r))≥r//r←r-1//這樣的r有D(J(r))＞r//repeatIfD(J(r))≤D(i)andD(i)＞rthen//把i插入到J中//fori←ktor+1by-1doJ(i+1)←J(i)//將插入點(diǎn)的作業(yè)后移一位//repeatJ(r+1)←i;k←k+1//將i計入J中//endifrepeatendJS另一退出條件是D(J(r))＞D(i)而D(J(r))=r

計算時間分析fori←2tondo

將循環(huán)n-1次－－－－－－－－－－－－－①r←kwhileD(J(r))＞D(i)andD(J(r))≠rdo至多循環(huán)k次，k是當(dāng)前計入J中的作業(yè)數(shù)

1≤k≤n-1

－－－－－－－－－②r←r-1repeatIfD(J(r))≤D(i)andD(i)＞rthenfori←ktor+1by-1do循環(huán)k-r次，r是插入點(diǎn)之前的位置

最壞情況下循環(huán)k次，插入到最頭部－－③J(i+1)←J(i)repeatJ(r+1)←I;k←k+1endifrepeat設(shè)s是最終計入J中的作業(yè)數(shù)，則算法JS所需要的總時間是O(sn)。s≤n，故最壞情況：TJS=О(n2)，特例情況：pi=di=n-i+1,1≤i≤n最好情況：TJS=О(n)，特例情況：pi=n-i+1,di=i,1≤i≤n6.一種“更快”的作業(yè)排序問題

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

對于作業(yè)i，若還沒有給i分配處理時間，則分配給它時間片[α-1,α]，其中α是盡量取大且[α-1,α]為空的時間片。

即：盡量推遲作業(yè)i的處理時間。這樣在安排作業(yè)處理次序時不必每有一個作業(yè)加入就需移動J中已有的作業(yè)。

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

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

使用不相交集合的

UNION和FIND算法（見數(shù)據(jù)結(jié)構(gòu)相關(guān)章節(jié)），可以將JS的計算時間降低到數(shù)量級接近О(n)。

（略）【程序6－3】帶時限作業(yè)排序的貪心算法

voidGreedyJob(intd[],SetX,intn){//前置條件：p0p1,…,pn-1

X={0};for(inti=1;i<n;i++)if(集合X{i}中作業(yè)都能在給定時限內(nèi)完成)X=X{i};}

6.3.3

算法正確性

定理6－2

程序6－2的貪心算法對于帶時限作業(yè)排序問題將得到最優(yōu)解。

6.3.4

可行性判定

定理6－3

X=（x0,x1,…,xk）是k個作業(yè)的集合，=（0,1,…,k）是X的一種特定排列，它使得，其中，是作業(yè)j的時限。X是一個可行解當(dāng)且僅當(dāng)X中的作業(yè)能夠按次序調(diào)度而不會有作業(yè)超期。6.3.5作業(yè)排序貪心算法

定理6－3提供了一種高效的可行解判定方法。使得在按最優(yōu)量度標(biāo)準(zhǔn)，即按作業(yè)收益的非增次序選擇下一個作業(yè)后，可以有效地判定是否可將該作業(yè)加入已生成的部分解向量X。

【程序6－4】帶時限的作業(yè)排序程序intJS(int*d,int*x,intn){//設(shè)p0p1pn-1intk=0;x[0]=0;for(intj=1;j<n;j++){intr=k;while(r>=0&&d[x[r]]>d[j]&&d[x[r]]>r+1)r--;if((r<0||d[x[r]]<=d[j])&&d[j]>r+1){ for(inti=k;i>=r+1;i--)x[i+1]=x[i];x[r+1]=j;k++;}}returnk;}6.3.6一種改進(jìn)算法本小節(jié)將介紹一種帶時限作業(yè)排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的時間從(n2)減少到接近O(n)。例6－3

設(shè)n=5個作業(yè)，作業(yè)的時限為:(d0,d1,d2,d3,d4)=(2,2,1,3,3),收益為:(p0,p1,p2,p3,p4)=(20,15,10,5,1)?！境绦?－5】使用并查集的帶時限作業(yè)排序

intFJS(int*d,int*x,intn){UFSets(n);intb,k=-1,*f=newint[n+1];for(inti=0;i<=n;i++)f[i]=i;

for(i=0;i<n;i++){if(n<d[i])b=n;elseb=d[i]; intr=s.Find(b);if(f[r]){x[++k]=i;intt=s.Find(f[r]-1);s.Union(t,r);f[r]=f[t];}}delete[]f;returnk;}6.4最佳合并模式6.4.1問題描述

兩路合并外排序算法通過反復(fù)執(zhí)行將兩個有序子文件合并成一個有序文件的操作，最終將n個長度不等的有序子文件合并成一個有序文件。合并n個有序子文件成為一個有序文件的合并過程可以有多種方式，稱為合并模式。在整個合并過程中，需從外存讀寫的記錄數(shù)最少的合并方案稱為最佳合并模式（optimalmergepattern）。

例6－4

設(shè)有5個有序子文件（F1,F2,F3,F4,F5），其長度分別為（20，30，30，10，5）?，F(xiàn)通過兩兩合并將其合并成一個有序文件。帶權(quán)外路徑長度是針對擴(kuò)充二叉樹而言的。擴(kuò)充二叉樹（extendedbinarytree）中除葉子結(jié)點(diǎn)外，其余結(jié)點(diǎn)都必須有兩個孩子。擴(kuò)充二叉樹的帶權(quán)外路徑長度（weightedexternalpathlength）定義為：6.4.2

貪心法求解

兩路合并最佳模式問題的最優(yōu)量度標(biāo)準(zhǔn)為帶權(quán)外路徑長度最小。兩路合并最佳模式的貪心算法簡述如下：設(shè)W＝{w0,w1,,wn－1}是n個有序文件的長度；以每個權(quán)值作為根結(jié)點(diǎn)值，構(gòu)造n棵只有根的二叉樹；選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹，作為左右子樹構(gòu)造一棵新二叉樹，新樹根的權(quán)值是兩棵子樹根的權(quán)值之和；重復(fù)第2步，直到合并成一棵二叉樹為止。【程序6－6】兩路合并最佳模式的貪心算法template<classT>structHNode{//優(yōu)先權(quán)隊(duì)列中的元素的類型 operatorT()const{returnweight;}BTNode<T>*ptr;Tweight;};template<classT>BTNode<T>*CreateHfmTree(T*w,intn){//w為一維數(shù)組保存n個權(quán)值 PrioQueue<HNode<T>>pq(2*n-1); BTNode<T>*p;HNode<T>a,b; for(inti=0;i<n;i++){ p=newBTNode<T>(w[i]); a.ptr=p;a.weight=w[i]; pq.Append(a); }

for(i=1;i<n;i++){ pq.Serve(a);pq.Serve(b);a.weight+=b.weight; p=newBTNode<T>(a.weight,a.ptr,b.ptr); a.ptr=p; pq.Append(a); } pq.Serve(a); returna.ptr;}6.4.3算法正確性

定理6－4

設(shè)有n個權(quán)值W={w0,w1,,wn－1}作為外結(jié)點(diǎn)的權(quán)值，構(gòu)造兩路合并樹的貪心算法將生成一棵具有最小帶權(quán)外路徑長度的二叉樹。

6.5

最小代價生成樹6.5.1

問題描述問題一個無向連通圖的生成樹是一個極小連通子圖，它包括圖中全部結(jié)點(diǎn)，并且有盡可能少的邊。一棵生成樹的代價是樹中各條邊上的代價之和。一個網(wǎng)絡(luò)的各生成樹中，具有最小代價的生成樹稱為該網(wǎng)絡(luò)的最小代價生成樹（minimum-costspanningtree）。6.5.2

貪心法求解

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

選擇使得迄今為止已入選S中邊的代價之和增量最小的邊

克魯斯卡爾算法的貪心準(zhǔn)則是：按邊代價的非減次序考察E中的邊，從中選擇一條代價最小的邊e=(u,v)。

普里姆算法的貪心準(zhǔn)則是：在保證S所代表的子圖是一棵樹的前提下選擇一條最小代價的邊e=(u,v)?！境绦?－7】最小代價生成樹的貪心算法ESetTypeSpanningTree(ESetTypeE,intn){//G=(V,E)為無向圖

ESetTypeS=;intu,v,k=0;ETypee;while(k<n-1&&E中尚有未檢查的邊){e＝select(E);if(Se不包含回路){S=Se;k++;}}returnS;}6.5.3

普里姆算法

【程序6－8】普里姆算法

template<classT>structENode{//帶權(quán)圖的邊結(jié)點(diǎn) intadjVex; Tw;ENode*nextArc;};template<classT>classGraph{public: Graph(intmSize);voidPrim();……protected:voidPrim(intk,int*nearest,T*lowcost);……ENode<T>**a;intn;};template<classT>voidGraph<T>::Prim(ints){//公有成員函數(shù) int*nearest=newint[n],*lowcost=newint[n]; Prim(s,nearest,lowcost); for(intj=0;j<n;j++)cout<<"("<<nearest[j]<<",“<<j<<","<<lowcost[j]<<")"; cout<<endl;delete[]nearest;delete[]lowcost;}template<classT>voidGraph<T>::Prim(intk,int*nearest,T*lowcost){//私有成員函數(shù)bool*mark=newbool[n]; ENode<T>*p;if(k<0||k>n-1)throwOutofBounds;for(inti=0;i<n;i++){nearest[i]=-1;mark[i]=false;lowcost[i]=INFTY;}lowcost[k]=0;nearest[k]=k;mark[k]=true;

for(i=1;i<n;i++){for(p=a[k];p;p=p->nextArc){ intj=p->adjVex; if((!mark[j])&&(lowcost[j]>p->w)){ lowcost[j]=p->w;nearest[j]=k;}}Tmin=INFTY;for(intj=0;j<n;j++)if((!mark[j])&&(lowcost[j]<min)){ min=lowcost[j];k=j;}mark[k]=true;}}普里姆算法的運(yùn)行時間是O(n2)。6.5.4

克魯斯卡爾算法克魯斯卡爾算法從邊的集合E中，按照邊的權(quán)值從小到大的次序依次選取邊加以考察。template<classT>structeNode{ operatorT()const{returnw;} intu,v; Tw;};

【程序6－9】克魯斯卡爾算法

template<classT>voidGraph<T>::Kruskal( PrioQueue<eNode<T>>&pq){ eNode<T>x; UFSets(n); intu,v,k=0;

while(k<n-1&&!pq.IsEmpty()){ pq.Serve(x); u=s.Find(x.u);v=s.Find(x.v); if(u!=v){ s.Union(u,v); k++;cout<<"("<<x.u<<",“<<x.v<<","<<x.w<<")"; } }cout<<endl;if(k<n-2)throwNonConnected;}克魯斯卡爾算法的時間復(fù)雜度為O（elog

e）。

6.5.5算法正確性定理6－5

設(shè)圖G=（V，E）是一個帶權(quán)連通圖，U是V的一個真子集。若邊(u,v)E是所有uU,vV-U的邊中權(quán)值最小者，那么一定存在G的一棵最小代價生成樹T=(V,S)，(u,v)S。這一性質(zhì)稱為MST（minimumspanningtree）性質(zhì)。定理6－6

普里姆算法和克魯斯卡爾算法都將產(chǎn)生一個帶權(quán)無向連通圖的最小代價生成樹。6.6單源最短路徑6.6.1問題描述單源最短路徑問題是：給定帶權(quán)的有向圖G=(V,E)和圖中結(jié)點(diǎn)sV，求從s到其余各結(jié)點(diǎn)的最短路徑，其中，s稱為源點(diǎn)。

6.6.2貪心法求解迪杰斯特拉（Dijkstra）

算法

首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點(diǎn)到其它所有結(jié)點(diǎn)之間的最短路徑都已求得為止。

6.6.3迪杰斯特拉算法

【程序6－10】迪杰斯特拉算法template<classT>classMGraph{public:MGraph(intmSize);voidDijkstra(ints,T*&d,int*&path);

……

private:intChoose(int*d,bool*s);……T**a;intn;};template<classT>intMGraph<T>::Choose(int*d,bool*s){inti,minpos;Tmin;min=INFTY;minpos=-1;for(i=1;i<n;i++)if(d[i]<min&&!s[i]){min=d[i];minpos=i;}returnminpos;}template<classT>voidMGraph<T>::Dijkstra(ints,