高等教育《算法設(shè)計(jì)與分析》第06章

第2局部算法設(shè)計(jì)策略

6.1一般方法 6.2背包問題 6.3帶時(shí)限的作業(yè)排序 6.4最正確合并模式 6.5最小代價(jià)生成樹 6.6單源最短路徑 6.7磁帶最優(yōu)存儲 6.8貪心法的根本要素第6章貪心法

最優(yōu)化問題〔optimizationproblems〕是指這樣一類問題，問題給定某些約束條件〔constraint〕，滿足這些約束條件的問題解稱為可行解〔feasiblesolution〕。通常滿足約束條件的解不是惟一的。為了衡量可行解的好壞，問題還給出了某個(gè)數(shù)值函數(shù)，稱為目標(biāo)函數(shù)〔objectivefunction〕，使目標(biāo)函數(shù)取最大〔或最小〕值的可行解稱為最優(yōu)解〔optimalsolution〕。6.1一般方法

貪心法是通過分步?jīng)Q策〔stepwisedecision〕的方法來求解問題的。貪心法每一步上用作決策依據(jù)的選擇準(zhǔn)那么被稱為最優(yōu)量度標(biāo)準(zhǔn)〔optimizationcriterion〕。在根據(jù)最優(yōu)量度標(biāo)準(zhǔn)選擇分量的過程中，還需要使用一個(gè)可行解判定函數(shù)。貪心策略并不是從整體上加以考慮的，它所做出的選擇只是當(dāng)前看似最正確選擇，必須進(jìn)一步證明該算法最終導(dǎo)致問題的一個(gè)整體最優(yōu)解。

貪心技術(shù)(GreedyTechnique)A(1)A(2)…A(n-1)A(n)某一問題的n個(gè)輸入B1(1)B1(2)…B1(m)該問題的一種解〔可行解〕是A的一個(gè)子集滿足一定的條件約束條件Bk(1)Bk(2)…Bk(m)…目標(biāo)函數(shù)取極值最優(yōu)解

【程序6－1】貪心法SolutionType

Greedy(SType

a[],intn){

SolutionTypesolution=;

for(inti=0;i<n;i++){

STypex=Select(a); if(Feasiable(solution,x)) solution=Union(solution,x); } returnsolution;}

7找零錢問題(change-makingproblem)用當(dāng)?shù)孛骖~為d1>d2>…>dm的最少數(shù)量的硬幣找出金額為n的零錢。如d1=25,d2=10,d3=5,d4=1，n=48該問題的一個(gè)解是：1個(gè)25，2個(gè)10，3個(gè)1，且該解是最優(yōu)的。這種方法稱為貪心法，建議通過一系列步驟來構(gòu)造問題的解，每一步對目前構(gòu)造的局部解做一個(gè)擴(kuò)展，直到獲得問題的完全解。必須滿足：可行、局部最優(yōu)、不可取消

8又如：d1=11,d2=5,d3=1,n=15該問題的一個(gè)解是：1個(gè)11，4個(gè)1，該解不是最優(yōu)的。最優(yōu)解：3個(gè)5本質(zhì)上由硬幣面值種類決定〔問題其本身固有的特點(diǎn)〕。

貪心策略最優(yōu)解的證明根本思想設(shè)X={x1,x2,...,xn}為貪心策略得到的解設(shè)Y={y1,y2,...,yn}為該問題的最優(yōu)解很明顯，X≠Y，如果成立，那么不用證明了。證明過程：依次比較X和Y中的每個(gè)元素，如果發(fā)現(xiàn)不一樣，那么用X中的替換Y中相應(yīng)元素，比較完后得到一個(gè)新的解Y’=X此時(shí)，如能證明Y’的最優(yōu)值就是Y的最優(yōu)值或者比Y還好，那么說明X就是最優(yōu)解。

問題對容量為M的背包進(jìn)行最正確裝載的問題。6.2背包問題

6.2.1

問題描述

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

6.2.2貪心法求解

背包問題背包問題的解可以表示成一個(gè)n-元組：X=(x0,x1,,xn－1)，0xi1，0i<n，每個(gè)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)。

背包問題(KnapsackProblem)方案1：按物品價(jià)值降序裝包方案2：按物品重量升序裝包方案3：按物品價(jià)值與重量比值的降序裝包

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

template<classT>classKnapsack{public:

Knapsack(int

mSize,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.2.3

算法正確性定理6－1如果p0/w0p1/w1pn－1/wn－1，那么程序6－2求得的背包問題的解是最優(yōu)解。

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

即xi=10≤i＜j,0≤xj＜1,xi=0j＜i≤n-1

假設(shè)Y是問題的最優(yōu)解：Y=(y0,y1,…,yn-1)且有：●假設(shè)X＝Y(jié)，那么X就是最優(yōu)解。否那么，●X和Y至少在1個(gè)分量上存在不同。設(shè)k是使得yk≠xk的最小下標(biāo)，那么有yk＜xk?？煞忠韵虑闆r說明：a)假設(shè)k<j，那么xk=1。因?yàn)閥k≠xk,從而有yk＜xkb)假設(shè)k=j，由于，且對1≤i＜j，有yi=xi=1,而對j＜i≤n,有xi＝0；故此時(shí)假設(shè)yk＞xk，那么將有，與Y是可行解相矛盾。而yk≠xk,所以yk＜xkc)假設(shè)k＞j，那么，不能成立

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

Z的效益值有：差值＝0

由以上分析得，假設(shè)，那么Y將不是最優(yōu)解；假設(shè)，那么或者Z=X，那么X就是最優(yōu)解；或者Z≠X，那么重復(fù)以上替代過程，或者證明Y不是最優(yōu)解，或者把Y轉(zhuǎn)換成X，從而證明X是最優(yōu)解

最優(yōu)裝載

有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。1.算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。

template<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}

2.貪心選擇性質(zhì) 可以證明最優(yōu)裝載問題具有貪心選擇性質(zhì)。3.最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。算法loading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為O(nlogn)。

活動安排問題活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個(gè)簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。

設(shè)有n個(gè)活動的集合E={1,2,…,n}，其中每個(gè)活動都要求使用同一資源，如演講會場等，而在同一時(shí)間內(nèi)只有一個(gè)活動能使用這一資源。每個(gè)活動i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動i，那么它在半開時(shí)間區(qū)間[si,fi)內(nèi)占用資源。假設(shè)區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，那么稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時(shí)，活動i與活動j相容。

template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}下面給出解活動安排問題的貪心算法GreedySelector:各活動的起始時(shí)間和結(jié)束時(shí)間存儲于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列

由于輸入的活動以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動參加集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動。算法greedySelector的效率極高。當(dāng)輸入的活動已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時(shí)間重排。

例：設(shè)待安排的11個(gè)活動的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314

算法greedySelector的計(jì)算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。

假設(shè)被檢查的活動i的開始時(shí)間Si小于最近選擇的活動j的結(jié)束時(shí)間fi，那么不選擇活動i，否那么選擇活動i參加集合A中。貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。

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

6.3.2貪心法求解例6－2設(shè)有4個(gè)作業(yè)，每個(gè)作業(yè)的時(shí)限為(d0,d1,d2,d3)=(2,1,2,1),收益為(p0,p1,p2,p3)=(100,10,15,27)。

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

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

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

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

證明：設(shè)X=(x0,x1,…,xK)是由貪心算法6-2所得的作業(yè)集合——貪心解，Y=(y0,y1,…,yr)是一個(gè)最優(yōu)解的作業(yè)集合。①假設(shè)Y=X，那么X就是最優(yōu)解；否那么②，那么至少存在兩個(gè)作業(yè)a和b，使得a∈X且,b∈Y且?！矠槭裁础巢⒃O(shè)a是這樣的一個(gè)具有最高效益值的作業(yè)

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

設(shè)α和β分別是X和Y的可行的調(diào)度表。因?yàn)閄和Y都是可行解，故這樣的調(diào)度表一定存在；設(shè)x是既屬于X又屬于Y的一個(gè)作業(yè)，并設(shè)x在調(diào)度表α中的調(diào)度時(shí)刻是[t，t+1]，而在β中的調(diào)度時(shí)刻是[t’，t’+1]。在X和Y中作如下調(diào)整：●假設(shè)t＜t’，那么將α中在[t’，t’+1]時(shí)刻調(diào)度的那個(gè)作業(yè)〔如果有的話〕與x相交換。如果X中在[t’，t’+1]時(shí)刻沒有作業(yè)調(diào)度，那么直接將x移到[t’，t’+1]調(diào)度?！碌恼{(diào)度表也是可行的?！瓁.………………z…………y.………………x………α：β：tt’

●假設(shè)t’＜t，那么在β中作類似的調(diào)換，即將β中在[t，t+1]時(shí)刻調(diào)度的那個(gè)作業(yè)〔如果有的話〕與x相交換。如果Y中在[t，t+1]時(shí)刻沒有作業(yè)調(diào)度，那么直接將x移到[t，t+1]調(diào)度?！瑯?，新的調(diào)度表也是可行的。對X和Y中共有的所有作業(yè)作上述的調(diào)整。設(shè)調(diào)整后得到的調(diào)度表為α’和β’，那么在α’和β’中X和Y中所有的共有作業(yè)將在相同時(shí)間被調(diào)度?！瓂.………………x…………x.………………z………α：β：t’t

設(shè)a在α’中的調(diào)度時(shí)刻是[ta,ta+1]，b是β’中該時(shí)刻調(diào)度的作業(yè)，那么有pa≥pb〔為什么？〕。

在β’中，去掉作業(yè)b，而去調(diào)度作業(yè)a，得到的是作業(yè)集合Y’=〔Y-〕∪{a}的一個(gè)可行的調(diào)度表，且Y’的效益值不小于X的效益值。而Y’中比Y少了一個(gè)與X不同的作業(yè)。重復(fù)上述的轉(zhuǎn)換，可使Y在不減效益值的情況下轉(zhuǎn)換成X。從而X至少有和Y一樣的效益值。所以X也是最優(yōu)解。證畢?！?……….a…………………..………b……………α：β：ta

α=〔…x…z…〕α=〔…z…x…〕β=〔…y…x…〕β=〔…y…x…〕(a)x與z交換前(b)x與z交換后α=〔…y…x…〕α=〔…y…x…〕β=〔…x…z…〕β=〔…z…x…〕(c)x與z交換前(d)x與z交換后圖6-1使相同作業(yè)在相同時(shí)刻被調(diào)度

可行性判定定理6－3X=〔x0,x1,…,xk〕是k個(gè)作業(yè)的集合，=〔0,1,…,k〕是X的一種特定排列，它使得d0≤d1≤…≤dk，其中，dj是作業(yè)j的時(shí)限。X是一個(gè)可行解當(dāng)且僅當(dāng)X中的作業(yè)能夠按次序調(diào)度而不會有作業(yè)超期。

方法一：枚舉法，檢驗(yàn)X中作業(yè)所有可能的排列，對于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能夠在其期限前完成——假設(shè)X中有k個(gè)作業(yè)，那么將要檢查k!個(gè)序列判斷策略：對于一個(gè)給定作業(yè)處理序列α＝i1i2…ik,由于作業(yè)ij完成的最早時(shí)間是j，因此只要判斷出α排列中的每個(gè)作業(yè)的期限有dij≥j，就可得知α是一個(gè)允許的調(diào)度序列，從而X是一可行解。反之，如果α排列中有一個(gè)作業(yè)有dij＜j,那么α將是一個(gè)行不通的調(diào)度序列，因?yàn)橹辽僮鳂I(yè)ij不能在其期限之前完成。方法二：檢查X中作業(yè)的一個(gè)特定序列就可判斷X的可行性：這一特定序列是按照作業(yè)期限的非降次序排列的作業(yè)序列

證明：①如果X中的作業(yè)可以按照α的次序而又不違反任何一個(gè)作業(yè)期限的情況來處理，那么X是一個(gè)可行解②現(xiàn)證假設(shè)X是一個(gè)可行解，α是否代表一個(gè)可行的調(diào)度序列？∵X是可行解∴必存在一可行的調(diào)度序列β＝r1r2…rk，使得drj≥j,1≤j≤k?！锛僭O(shè)α＝β，那么α即是可行的調(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的處理次序不違反任何一個(gè)期限，而γ中位置a及a之前的作業(yè)均與α相同。重復(fù)上述過程，那么可將β轉(zhuǎn)換成α且不違反任何一個(gè)期限，故α是一個(gè)可行的調(diào)度序列故定理得證。

6.3.5作業(yè)排序貪心算法

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

【程序6－4】帶時(shí)限的作業(yè)排序程序int

JS(int*d,int*x,intn){//設(shè)p0p1pn-1

intk=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é)將介紹一種帶時(shí)限作業(yè)排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的時(shí)間從(n2)減少到接近O(n)。

例6－3

設(shè)n=5個(gè)作業(yè)，作業(yè)的時(shí)限為:(d0,d1,d2,d3,d4)=(2,2,1,3,3),收益為:(p0,p1,p2,p3,p4)=(20,15,10,5,1)。

【程序6－5】使用并查集的帶時(shí)限作業(yè)排序int

FJS(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;}

多機(jī)調(diào)度問題

多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺機(jī)器加工處理完成。

這個(gè)問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。

約定，每個(gè)作業(yè)均可在任何一臺機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。

采用最長處理時(shí)間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問題的較好的近似算法。按此策略，當(dāng)n≤m時(shí)，只要將機(jī)器i的[0,ti]時(shí)間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時(shí)間。當(dāng)n>m時(shí)，首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。算法所需的計(jì)算時(shí)間為O(nlogn)。

例如，設(shè)7個(gè)獨(dú)立作業(yè){1,2,3,4,5,6,7}由3臺機(jī)器M1，M2和M3加工處理。各作業(yè)所需的處理時(shí)間分別為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如以下圖所示，所需的加工時(shí)間為17。

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

例6－4設(shè)有5個(gè)有序子文件〔F1,F2,F3,F4,F5〕，其長度分別為〔20，30，30，10，5〕?，F(xiàn)通過兩兩合并將其合并成一個(gè)有序文件。

帶權(quán)外路徑長度是針對擴(kuò)充二叉樹而言的。擴(kuò)充二叉樹〔extendedbinarytree〕中除葉子結(jié)點(diǎn)外，其余結(jié)點(diǎn)都必須有兩個(gè)孩子。擴(kuò)充二叉樹的帶權(quán)外路徑長度〔weightedexternalpathlength〕定義為：

貪心法求解兩路合并最正確模式問題的最優(yōu)量度標(biāo)準(zhǔn)為帶權(quán)外路徑長度最小。

兩路合并最正確模式的貪心算法簡述如下：設(shè)W＝{w0,w1,,wn－1}是n個(gè)有序文件的長度；以每個(gè)權(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個(gè)權(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個(gè)權(quán)值W={w0,w1,,wn－1}作為外結(jié)點(diǎn)的權(quán)值，構(gòu)造兩路合并樹的貪心算法將生成一棵具有最小帶權(quán)外路徑長度的二叉樹。

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

最小代價(jià)生成樹

網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，那么最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。

6.5.2

貪心法求解最優(yōu)量度標(biāo)準(zhǔn)選擇使得迄今為止已入選S中邊的代價(jià)之和增量最小的邊克魯斯卡爾算法的貪心準(zhǔn)那么是：按邊代價(jià)的非減次序考察E中的邊，從中選擇一條代價(jià)最小的邊e=(u,v)。普里姆算法的貪心準(zhǔn)那么是：在保證S所代表的子圖是一棵樹的前提下選擇一條最小代價(jià)的邊e=(u,v)。

最小生成樹性質(zhì)用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。將介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這兩個(gè)算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。

【程序6－7】最小代價(jià)生成樹的貪心算法ESetType

SpanningTree(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;}

Prim(普里姆)算法

【程序6－8】普里姆算法template<classT>struct

ENode{//帶權(quán)圖的邊結(jié)點(diǎn)

int

adjVex; 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)行時(shí)間是O(n2)。

6.5.4

克魯斯卡爾算法

克魯斯卡爾算法從邊的集合E中，按照邊的權(quán)值從小到大的次序依次選取邊加以考察。

template<classT>

struct

eNode{ 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;}克魯斯卡爾算法的時(shí)間復(fù)雜度為O〔eloge〕。

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

定理6－6

普里姆算法和克魯斯卡爾算法都將產(chǎn)生一個(gè)帶權(quán)無向連通圖的最小代價(jià)生成樹。

6.6.1問題描述單源最短路徑問題是：給定帶權(quán)的有向圖G=(V,E)和圖中結(jié)點(diǎn)sV，求從s到其余各結(jié)點(diǎn)的最短路徑，其中，s稱為源點(diǎn)。6.6單源最短路徑

貪心法求解迪杰斯特拉〔Dijkstra〕算法首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點(diǎn)到其它所有結(jié)點(diǎn)之間的最短路徑都已求得為止。

6.6.3迪杰斯特拉算法

【程序6－10】迪杰斯特拉算法template<classT>classMGraph

{public:

MGraph(int

mSize);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,T*&d,int*&path){ intk,i,j; if(s<0||s>n-1)throwOutOfBounds; bool*inS=newbool[n];d=newT[n];path=newint[n];for(i=0;i<n;i++){inS[i]=false;d[i]=a[s][i];if(i!=s&&d[i]<INFTY)path[i]=s;elsepath[i]=-1; }

inS[s]=true;d[s]=0;