匯編語(yǔ)言13章貪心算法-2016

第13章貪心法

引論優(yōu)化問(wèn)題:貪心法常用于解優(yōu)化問(wèn)題。應(yīng)用：（1）貨箱裝船（ContainerLoading)問(wèn)題（2）背包問(wèn)題（3）拓?fù)渑判騿?wèn)題

(4)哈夫曼編碼問(wèn)題（5）最短路徑問(wèn)題（6）最小代價(jià)生成樹(shù)

(7)偶圖覆蓋問(wèn)題13.1優(yōu)化問(wèn)題一個(gè)優(yōu)化問(wèn)題可以描述如下:（1）問(wèn)題的解為一復(fù)雜的結(jié)構(gòu)，例如元組形式

（2）約束條件：(結(jié)構(gòu)性的約束條件)使為true的元組稱為可行解（feasiblesolution）；（3）目標(biāo)函數(shù)

優(yōu)化解即指使目標(biāo)函數(shù)極大化(或極小化)的可行解，對(duì)應(yīng)的目標(biāo)函數(shù)值稱為優(yōu)化值。例:貨箱裝船問(wèn)題設(shè)有n個(gè)集裝箱,集裝箱大小一樣，第i個(gè)集裝箱的重量為wi(1≤i≤n),設(shè)船的載重量為c.試設(shè)計(jì)一裝船的方法使得裝入的集裝箱數(shù)目最多.令代表一種裝法約束條件

目標(biāo)函數(shù)極大化目標(biāo)函數(shù)很多優(yōu)化問(wèn)題是NP－難度問(wèn)題，迄今找不到它們的多項(xiàng)式算法。所以計(jì)算上可行的方法就是求其近似解。貪心法是求近似解的主要途徑。貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。13.2貪心算法貪心算法的基本要素對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

1.貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。2.最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。13.2貪心法的步驟貪心法是一種多步(stage)求解的方法;每步按一種局部?jī)?yōu)化的策略選擇解(元組)的一個(gè)分量;算法以第n步結(jié)束時(shí)構(gòu)造出的對(duì)象(元組)作為問(wèn)題的解.

這種局部?jī)?yōu)化的策略又稱為“貪心標(biāo)準(zhǔn)(greedycriterion).貪心法的主要特點(diǎn)是：不回溯:選定一個(gè)分量后，不重試其它可能。使用局部?jī)?yōu)化策略的主要原因是減小計(jì)算開(kāi)銷.但局部?jī)?yōu)化策略不保證得到精確優(yōu)化解，可能得到的是近似解。

特別是對(duì)NP－難度問(wèn)題。不同的“貪心”策略得到不同的算法。常常采納使目標(biāo)函數(shù)有最大增量的策略為貪心策略，增量是局部性概念。遺傳算法、神經(jīng)網(wǎng)絡(luò)等等都是具有這類貪心性質(zhì)的啟發(fā)式算法。

例：找零錢問(wèn)題假設(shè)有四種硬幣，它們的面值分別為二角五分、一角、五分和一分。現(xiàn)在要找給某顧客六角三分錢。這時(shí)，我們會(huì)不假思索地拿出2個(gè)二角五分的硬幣，1個(gè)一角的硬幣和3個(gè)一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，所拿出的硬幣個(gè)數(shù)是最少的。這里，我們下意識(shí)地使用了這樣的找硬幣算法：首先選出一個(gè)面值不超過(guò)六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出一個(gè)面值不超過(guò)三角八分的最大硬幣，即又一個(gè)二角五分，如此一直做下去。這個(gè)找硬幣的方法實(shí)際上就是貪心算法。顧名思義，貪心算法總是作出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。例：活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動(dòng)i，則它在半開(kāi)時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。即當(dāng)si≥fj或sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容。貪心算法描述下面所給出活動(dòng)安排問(wèn)題的貪心算法greedySelector:publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;intj=1;intcount=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說(shuō)，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用min堆重排。算法復(fù)雜度為(nlogn)例：機(jī)器調(diào)度

現(xiàn)有n個(gè)任務(wù)和足夠多臺(tái)機(jī)器,假定任何時(shí)間一臺(tái)機(jī)器只能執(zhí)行一個(gè)任務(wù).設(shè)任務(wù)i的開(kāi)始時(shí)間為si,完成時(shí)間為fi,si<fi.[si,fi]為處理任務(wù)i的時(shí)間區(qū)間.稱兩個(gè)任務(wù)i,j

重疊是指兩個(gè)任務(wù)的時(shí)間區(qū)間有重疊.例如：區(qū)間[1,4]與區(qū)間[2,5]重疊,而與區(qū)間[4,7]不重疊.可行的任務(wù)分配是指該分配中沒(méi)有將重疊的任務(wù)分配給同一臺(tái)機(jī)器.最優(yōu)分配指占用機(jī)器數(shù)最少的可行分配.圖13-17個(gè)任務(wù)及使用三臺(tái)機(jī)器的調(diào)度a)7個(gè)任務(wù)b)調(diào)度例13.5(續(xù))按任務(wù)起始時(shí)間對(duì)任務(wù)排序并按此順序安排任務(wù).貪心準(zhǔn)則:盡可能使用舊(old)的機(jī)器.定義每臺(tái)用過(guò)的機(jī)器的可用時(shí)間為這臺(tái)機(jī)器上最近執(zhí)行的任務(wù)的完成時(shí)間.如果一個(gè)新任務(wù)的起始時(shí)間≥這些機(jī)器的最小可用時(shí)間則安排該任務(wù)在這臺(tái)機(jī)器上執(zhí)行;否則使用一臺(tái)新機(jī)器.使用min-堆存放每臺(tái)機(jī)器的可用時(shí)間,即此時(shí)間以后可安排新任務(wù).算法的時(shí)間復(fù)雜度為Θ(nlogn)(排序和堆操作).貪心算法并不總能求得問(wèn)題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問(wèn)題、機(jī)器調(diào)度問(wèn)題，上述貪心算法卻總能求得整體最優(yōu)解.以機(jī)器調(diào)度問(wèn)題為例進(jìn)行證明證明:任何可行解使用的機(jī)器數(shù)≥最大重迭任務(wù)數(shù);所以優(yōu)化調(diào)度使用的機(jī)器數(shù)≥最大重迭任務(wù)數(shù).貪心解使用的機(jī)器數(shù)不超過(guò)最大重迭任務(wù)數(shù)：任何時(shí)候當(dāng)算法使用一臺(tái)新機(jī)器時(shí),當(dāng)前這些機(jī)器上的任務(wù)一定是彼此重疊的.貪心算法性能例：最短路算法給定一個(gè)有向圖G,一個(gè)源節(jié)點(diǎn)s,目的節(jié)點(diǎn)d;找從s到d的一條最短路徑.從s開(kāi)始選離s“最近”的下一個(gè)節(jié)點(diǎn)q;再?gòu)膓開(kāi)始找和q相鄰的且不在前面已選擇的路徑上的下一節(jié)點(diǎn);重復(fù)這一過(guò)程直到遇到d節(jié)點(diǎn)或該路徑無(wú)法繼續(xù)延伸.貪心解不是優(yōu)化解:按貪心法找到的1到5的路徑為(1,3,4,2,5).13.3貪心算法的應(yīng)用（1）貨箱裝船（ContainerLoading)問(wèn)題（2）背包問(wèn)題（3）拓?fù)渑判騿?wèn)題

(4)哈夫曼編碼問(wèn)題（5）最短路徑問(wèn)題（6）最小代價(jià)生成樹(shù)

(7)偶圖覆蓋問(wèn)題13.3.1Containerloading目標(biāo)函數(shù)：裝載的集裝箱數(shù)目.極大化目標(biāo)函數(shù).貪心標(biāo)準(zhǔn)：在還沒(méi)裝船的集裝箱中選擇重量最小的集裝箱.按上述策略,重量最小的集裝箱先裝,依此類推.算法：首先按重量從小到大對(duì)集裝箱排序并依次裝入直到超過(guò)船的載重量.定理13.1上述貪心法產(chǎn)生的解是最優(yōu)解,證明如下:設(shè)貨箱裝船問(wèn)題的最優(yōu)解為(y1,…,yn).如最優(yōu)解不含箱子1(y1=0),將箱子1替換優(yōu)化解中某一個(gè)箱子得到一個(gè)新的解.替換是必須的:因?yàn)槿绻渥?還能裝入船中,則(y1,…,yn)不是優(yōu)化的.因?yàn)橄渥?是最輕的,替換后的解仍是可行的.替換后的解裝入的箱子數(shù)等于優(yōu)化的裝箱數(shù),所以它仍是優(yōu)化解.替換后新的優(yōu)化解和貪心解都包含箱子1.反復(fù)替換將得到一個(gè)優(yōu)化解,它等于貪心解.替換次數(shù)是有窮的.13.2.20/1背包問(wèn)題0/1背包問(wèn)題：設(shè)有容量c的背包和n件物品,物品i的重量為wi;假定裝入物品i獲得的效益值為pi,試給出一裝入物品的方法,使獲得的總效益值最大.集裝箱裝載問(wèn)題是0/1背包問(wèn)題的特例：

pi=10/1背包問(wèn)題是NP－難度問(wèn)題,所以任何有多項(xiàng)式復(fù)雜度的算法產(chǎn)生的解都是近似解.13.2.20/1背包問(wèn)題背包問(wèn)題可形式化描述如下:使用0/1數(shù)組(x1,…,xn)表示一個(gè)裝法:

xi=1表示裝物品i,

否則不裝.約束條件：目標(biāo)函數(shù)：,等于裝入物品的總效益值極大化目標(biāo)函數(shù)0/1背包問(wèn)題0/1背包問(wèn)題有多種貪心策略（1）從未裝入的物品中,選出效益值最大的物品裝入.利用這種規(guī)則，效益值最大的物品首先被裝入(假設(shè)有足夠容量),然后是下一個(gè)效益值最大的物品,如此進(jìn)行下去.

注：這種策略不一定能保證得到最優(yōu)解n=3,c=105,w=[100,10,10],p=[20,15,15]

貪心解為：[1,0,0]，效益值為：20但優(yōu)化解為：[0,1,1]，效益值為30(續(xù))(2)從尚未裝入的物品中選擇重量最小的物品.雖然這一貪心法對(duì)于貨箱裝船問(wèn)題能產(chǎn)生最優(yōu)解,但在一般情況下不一定能得到最優(yōu)解例：n=2,c=25,w=[10,20],p=[5,100](3)按密度pi/wi,從未裝的物品中選擇可裝入背包(裝入后不超過(guò)背包容量),且密度值最大的物品.

貪心解為[1,0,0],但優(yōu)化解為[0,1,1]例：c=11,w=(2,4,6,5),p=(6,10,12,9)優(yōu)化解為：x=(1,1,0,1).注：這種策略也不能保證得到最優(yōu)解例：n=3,c=30,w=[20,15,15],p=[40,25,25](續(xù))密度貪心法的偽代碼:(1)將物品按密度從大到小排序

(2)for(i=1;i<n;i++)if(物品i可裝入到背包內(nèi))xi=1(裝入)

elsexi=0(舍棄);算法的時(shí)間復(fù)雜度為O(nlogn)

(續(xù))貪心法往往不能得到精確解，貪心解與最優(yōu)解的誤差用以下比值的百分比來(lái)度量:

|優(yōu)化值-貪心解值|/優(yōu)化值*100%例：n=2,c=y,w=[1,y],p=[10,9y]

對(duì)所有y>1,貪心解的效益值＝10；當(dāng)y>10/9時(shí),優(yōu)化效益值＝9y.不管優(yōu)化值多大,貪心解的值總是10.誤差為(9y-10)/9y=1-(10/9y).對(duì)足夠大的y,誤差可達(dá)到百分之百.例13.9k-優(yōu)化算法k-優(yōu)化算法是上述密度貪心算法的改進(jìn)，改進(jìn)后其誤差可控制在1/(k+1)*100％之內(nèi).例如3-優(yōu)化算法的誤差為25％.k-優(yōu)化算法也要先對(duì)物品按密度從大到小排序;先將一些物品裝入背包,然后對(duì)其余物品用貪心法;預(yù)先裝入的物品數(shù)不超過(guò)k.對(duì)所有物品數(shù)不超過(guò)k的物品子集執(zhí)行上述過(guò)程,并從中找到有最大效益值的解作為k-優(yōu)化算法的解.考慮n=4,w=[2,4,6,7],p=[6,10,12,13],c=11.使用2-優(yōu)化算法如下：

當(dāng)k=0時(shí),同于前述的密度貪心法.因此解為x=[1,1,0,0],效益值為16.例13.9(續(xù)1）k

=1時(shí),最初的子集為{1},{2},{3},{4}.子集{1},{2}產(chǎn)生與k=0時(shí)相同的結(jié)果考慮子集{3},置x3為1,此時(shí)背包剩余容量為5，未裝的物品為1,2,4.使用貪心法,得到的解為x=[1,0,1,0]，效益值為18.從子集{4}開(kāi)始,產(chǎn)生的解為x=[1,0,0,1]，效益值為19.因此，k=0,1時(shí)獲得的最優(yōu)解為[1,0,0,1].

例13.9（續(xù)2）若k=2,除了考慮k<2的子集,還必需考慮子集{1,2},{1,3},{1,4},{2,3},{2,4}和{3,4}.子集{3,4}是不可行的,將其舍棄對(duì)剩下的子集求解分別得到如下結(jié)果：[1,1,0,0],[1,0,1,0],[1,0,0,1],[0,1,1,0]和[0,1,0,1]，最后一個(gè)的效益值為23。K-優(yōu)化解為[0,1,0,1],值為23例13.9結(jié)論k-優(yōu)化方法(k>0)得到的解誤差不超過(guò)

(1/(k+1))*100％當(dāng)k=1時(shí),為50%以內(nèi),即如優(yōu)化值為100,貪心法算出的值不低于50;當(dāng)k=2時(shí),為33.33%以內(nèi).算法的時(shí)間復(fù)雜度隨k

的增大而增加:需要測(cè)試的子集數(shù)目為O(nk

);每一個(gè)子集做貪心法需時(shí)間O(n);因此當(dāng)k>0時(shí)總的時(shí)間開(kāi)銷為O(nk+1

).600種隨機(jī)測(cè)試的統(tǒng)計(jì)結(jié)果13.3.1哈夫曼編碼問(wèn)題哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。例如一個(gè)包含100,000個(gè)字符的文件，各字符出現(xiàn)頻率不同，如下表所示。定長(zhǎng)編碼需要300,000位，而按表中變長(zhǎng)編碼方案，文件的總碼長(zhǎng)為：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000。abcdef頻率(千次)4513121695定長(zhǎng)碼000001010011100101變長(zhǎng)碼010110011111011100前綴碼對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴，這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。平均碼長(zhǎng)定義為：使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。構(gòu)造哈夫曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。具體算法為：（1）根據(jù)n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)成n棵二叉樹(shù)的集合F={T1，T2，…，Tn}，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹(shù)均為空（2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)來(lái)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)結(jié)點(diǎn)的根結(jié)點(diǎn)的權(quán)值之和。（3）在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中。（4）重復(fù)（2）和（3），直到F中只含一棵樹(shù)時(shí)為止。稱這棵樹(shù)為最優(yōu)二叉樹(shù)（或哈夫曼樹(shù)）。

如果約定將每個(gè)結(jié)點(diǎn)的左分支表示字符“0”，右分支表示字符“1”，則可以把從根結(jié)點(diǎn)到某葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串作為該葉子結(jié)點(diǎn)的編碼。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹(shù)T。算法以|C|個(gè)葉結(jié)點(diǎn)開(kāi)始，執(zhí)行|C|－1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹(shù)T。算法說(shuō)明統(tǒng)計(jì)編碼字符集中每一字符c的頻率f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹(shù)。一旦2棵具有最小頻率的樹(shù)合并后，產(chǎn)生一棵新的樹(shù)，其頻率為合并的2棵樹(shù)的頻率之和，并將新樹(shù)插入優(yōu)先隊(duì)列Q。經(jīng)過(guò)n－1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹(shù)，即所要求的樹(shù)T。算法可以用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始化優(yōu)先隊(duì)列需要O(nlogn)計(jì)算時(shí)間，由于最小堆的插入和刪除運(yùn)算均需O(logn)時(shí)間，n－1次的合并總共需要O(nlogn)計(jì)算時(shí)間。因此，關(guān)于n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為O(nlogn)。圖論（Graph）相關(guān)的應(yīng)用問(wèn)題圖的基本知識(shí)定義：一個(gè)有向圖G=(V,E)是由包含頂點(diǎn)和邊的有序點(diǎn)對(duì)組成，其中V是頂點(diǎn)集合，E是邊的集合.在無(wú)向圖中，G=(V,E),邊集合E由無(wú)序點(diǎn)對(duì)組成.在有向圖和無(wú)向圖中，|E|=O(V2)若G是連通圖，則|E|>=|V|-1,即lg(E)=Θ(lgV)鄰接矩陣(adjacencymatrix)鄰接表(adjacencylist)鄰接表的存儲(chǔ)復(fù)雜度為Θ(V+E),

邊稀疏時(shí)適用。13.3.2拓?fù)渑判蛲負(fù)渑判蚨x：任務(wù)的先后順序可用有向圖表示,稱為AOV網(wǎng)絡(luò)(ActivityOnVertex).有向圖的頂點(diǎn)代表任務(wù),有向邊(i,j)表示先后關(guān)系:任務(wù)i完成后才能開(kāi)始任務(wù)j

.根據(jù)上述AOV網(wǎng)絡(luò)我們要對(duì)任務(wù)進(jìn)行排序使得排序序列的先后關(guān)系與AOV網(wǎng)定義的先后關(guān)系一致.根據(jù)任務(wù)的有向圖建立拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判?13.3.2拓?fù)渑判驅(qū)τ邢驁D的所有頂點(diǎn)的所有排列逐個(gè)檢驗(yàn)的方法是不足取的:O(n!)的時(shí)間復(fù)雜度.貪心法從空集開(kāi)始，每步產(chǎn)生拓?fù)渑判蛐蛄兄械囊粋€(gè)頂點(diǎn)w,怎樣選擇頂點(diǎn)w？greedy策略:從當(dāng)前尚不在拓?fù)渑判蛐蛄械捻旤c(diǎn)中選擇一頂點(diǎn)w,其所有先行節(jié)點(diǎn)v都在已產(chǎn)生的拓?fù)湫蛄兄?或無(wú)先行頂點(diǎn))并將其加入到拓?fù)湫蛄兄?

用減節(jié)點(diǎn)入度的方法確定w:入度變成0的頂點(diǎn)為要加到拓?fù)湫蛄兄械捻旤c(diǎn).使用棧的偽代碼(1)計(jì)算每個(gè)頂點(diǎn)的入度(2)將入度為0的頂點(diǎn)入棧(3)While(棧不空){任取一入度為0的頂點(diǎn)放入拓?fù)湫蛄兄?將與其相鄰的頂點(diǎn)的入度減1;如有新的入度為0的頂點(diǎn)出現(xiàn),將其放入棧中;}(4)如有剩余的頂點(diǎn)則該圖有環(huán)路引理13.1如果上述偽代碼表示的算法失敗,則有向圖含有環(huán)路.設(shè)V為算法結(jié)束時(shí)算法輸出的節(jié)點(diǎn)構(gòu)成的集合證明：當(dāng)失敗時(shí)|V|<n,且剩下的頂點(diǎn)不能加入已排好的序列V中.至少有一節(jié)點(diǎn)q1不在V中,和一條邊(q2,q1)且q2不在V中,否則q1可加入V中.同理,有邊(q3,q2）且q3不在V中.若q3=q1

則q1q2q3

是有向圖中的一個(gè)環(huán)路,若q3≠q1，則必存在q4,（q4,q3）是有向圖的邊且q4不在V中.否則q3應(yīng)在V中.若q4為q1,q2,q3

中的任何一個(gè),則該有向圖含有環(huán).因?yàn)橛邢驁D有有限個(gè)節(jié)點(diǎn),重復(fù)上述步驟,一定能找到一個(gè)環(huán)路.

程序13.2拓?fù)渑判虺绦?3.2拓?fù)渑判颍ɡm(xù)1）程序13.2拓?fù)渑判颍ɡm(xù)2）算法13.2的時(shí)間復(fù)雜度Θ(n2):使用鄰接矩陣;Θ(n+e):使用鄰接表;第一個(gè)for循環(huán)，初始化入度數(shù)組需O(n)時(shí)間計(jì)算入度:若使用鄰接矩陣，所用時(shí)間為O(n^2),若使用鄰接表，所用時(shí)間為O(n+e);進(jìn)出棧次數(shù):O(n);使用鄰接矩陣每步修改入度時(shí)間為O(n);使用鄰接表每步修改入度時(shí)間為O(節(jié)點(diǎn)的出度);總的修改入度時(shí)間為O(n^2)或O(n+e):有向圖的所有節(jié)點(diǎn)出度之和等于圖的邊數(shù).13.3.3單源最短路徑任給一有向圖G,它的每條邊都有一個(gè)非負(fù)的權(quán)值a[i][j],路徑的長(zhǎng)度定義為路徑上邊的權(quán)值之和.單源最短路問(wèn)題:給定源節(jié)點(diǎn)s,找出從s到圖中所有其他節(jié)點(diǎn)(稱為目的)的最短路徑(優(yōu)化解)及其長(zhǎng)度(優(yōu)化值)例：網(wǎng)絡(luò)中傳輸數(shù)據(jù)流時(shí),要耗費(fèi)網(wǎng)絡(luò)的帶寬和存儲(chǔ)資源,使用跳數(shù)少的路徑節(jié)省網(wǎng)絡(luò)資源.IP路由使用最短路算法(OSPF),因?yàn)镮P路由表按目的節(jié)點(diǎn)索引(查找),所以,OSPF協(xié)議使用該算法求出網(wǎng)絡(luò)中目的節(jié)點(diǎn)到任一節(jié)點(diǎn)的最短路.Dijkstra’s最短路算法如果鏈路權(quán)值非負(fù),則最短路的子路徑也是最短路,其長(zhǎng)度小于原來(lái)路徑的長(zhǎng)度.所以,長(zhǎng)度較小的最短路容易找到.貪心策略:按最短路長(zhǎng)度從小到大依次求解.Dijkstra’s最短路算法使用上述貪心策略,是圖論算法中應(yīng)用最為廣泛的算法,主要原因是其計(jì)算復(fù)雜度低且容易實(shí)現(xiàn).1.維護(hù)一個(gè)集合S，該集合中源節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路已知，初始時(shí)該集合為空2.從V-S集合中找一節(jié)點(diǎn)v，滿足源節(jié)點(diǎn)到該節(jié)點(diǎn)距離最小3.更新v的鄰節(jié)點(diǎn)的到源節(jié)點(diǎn)的距離值Dijkstra’s最短路算法基本步驟Dijkstra’s算法Dijkstra’s算法分析每個(gè)Extract-min操作的平攤代價(jià)無(wú)權(quán)圖（Unweightedgraphs）假定，對(duì)所有點(diǎn)對(duì)(u,v)∈E,w(u,v)=1,Dijkstra算法能否進(jìn)一步改進(jìn)？可使用FIFO隊(duì)列代替優(yōu)先隊(duì)列廣度優(yōu)先算法如下：廣度優(yōu)先算法例題源節(jié)點(diǎn)到其它所有節(jié)點(diǎn)的最短路若圖G=(V,E)包含負(fù)權(quán)回路，則最短路徑可能不存在。例Bellman-Ford算法：找出源節(jié)點(diǎn)到其它任意節(jié)點(diǎn)的最短路，或確定圖中包含負(fù)值環(huán)路負(fù)權(quán)環(huán)圖(Negative-weightcycles)單源最短路徑非負(fù)權(quán)重Dijkstra算法復(fù)雜度：O(E+VlgV)一般情況下：Bellman-Ford算法復(fù)雜度O(VE)多源最短路徑非負(fù)權(quán)值，Dijkstra算法復(fù)雜度O(VE+V2lgV)一般情況（權(quán)值可能為負(fù)）Bellman-Ford算法為O(V2E)或O(V4)最短路徑問(wèn)題小結(jié)13.3.6最小生成樹(shù)具有n個(gè)頂點(diǎn)的連通的無(wú)向圖G,圖的每條邊e有一非負(fù)權(quán)值c(e),也稱為成本,求有最小成本的生成樹(shù).每個(gè)生成樹(shù)剛好具有n-1條邊，所以問(wèn)題是用某種方法選擇n-1條邊使它們形成G的最小生成樹(shù)。我們采用以下二種不同的貪心策略來(lái)選擇這n-1條邊。這二種貪心策略對(duì)應(yīng)求解最小生成樹(shù)的二個(gè)算法：Kruskal’s算法，Prim’s算法。Kruskal’s算法貪心策略:每次選擇權(quán)值c(e)最小且與以前選擇的邊不構(gòu)成cycle的邊e.上述策略要求按權(quán)值從小到大對(duì)邊排序.圖13.12構(gòu)造最小生成樹(shù)圖13.12構(gòu)造最小生成樹(shù)（續(xù)1）圖13.12構(gòu)造最小生成樹(shù)（續(xù)2）圖13.13Kruskal’s算法的偽代碼算法正確性證明定理:Kruskal’s算法產(chǎn)生一棵最小生成樹(shù).設(shè)T是貪心法產(chǎn)生的解，U是優(yōu)化解設(shè)e是屬于T但不屬于U的成本最小的邊;換言之,T中成本小于c(e)的邊都在U中.設(shè)f是{e}+U產(chǎn)生的環(huán)路上不在T中的一條邊,這樣的f一定存在,否則T將包含一個(gè)環(huán)路.下面用反證法證明c(f)≥c(e):T中成本小于c(e)的邊都在U中,所以f與這些邊不構(gòu)成環(huán)路(這些邊都在U里);如果f的成本小于e的成本,貪心法會(huì)先于e將f加入到T中,矛盾.

（說(shuō)明c(f)不小于c(e)）從U中刪除f并加入e,得到的樹(shù)U’仍是優(yōu)化的.算法實(shí)現(xiàn)－數(shù)據(jù)結(jié)構(gòu)算法執(zhí)行過(guò)程中動(dòng)態(tài)產(chǎn)生的子樹(shù),反復(fù)進(jìn)行union和find操作,使用下面的數(shù)據(jù)結(jié)構(gòu)很有效.UNIN－FIND數(shù)據(jù)結(jié)構(gòu)初始為單個(gè)頂點(diǎn)的集合對(duì)每條邊做2次FIND找到邊的端點(diǎn)所在的集合;如果在同一集合中則舍棄該條邊,否則將2個(gè)集合合并(UNION)算法可在O(n+eloge)找出最小生成樹(shù):

邊排序:O(eloge)initializing:O(n)union-find:O(e)

Prim’s算法設(shè)A為算法執(zhí)行過(guò)程中產(chǎn)生的生成樹(shù)中的節(jié)點(diǎn)集合.初始化A包含圖中任一節(jié)點(diǎn);定義V-A中節(jié)點(diǎn)u到A的距離key(u)為

min{c(u,v)|v∈A,(u,v)∈E}取V-A中key(u)最小的節(jié)點(diǎn)u,并將其加入到A;更新V-A中的節(jié)點(diǎn)到A的距離(key值).重復(fù)執(zhí)行上述步驟.算法實(shí)現(xiàn)時(shí)將V-A中的節(jié)點(diǎn)按key值做成一個(gè)優(yōu)先級(jí)隊(duì)列(堆)Q.每次從V-A中抽取距離最小的節(jié)點(diǎn)u,并修改Q中與u相鄰的節(jié)點(diǎn)的key值(decreasekey).該算法不要求對(duì)邊排序.算法的偽代碼如下:Prim’s算法圖13.5圖13.15Prim’s算法舉例Prim’s算法舉例（續(xù)）Prim’s算法復(fù)雜度分析復(fù)雜度分析

13.3.7偶圖覆蓋問(wèn)題（二分覆蓋）偶圖是一個(gè)無(wú)向圖，它的n個(gè)頂點(diǎn)分為集合A和集合B，且同一集合中的任意兩個(gè)頂點(diǎn)無(wú)邊相連。A的一個(gè)子集A’覆蓋集合BiffB中每一頂點(diǎn)至少和A’中一頂點(diǎn)相連。覆蓋A’的大小指A’中的頂點(diǎn)數(shù)目。在偶圖中尋找最小覆蓋的問(wèn)題稱為偶圖覆蓋(bipartite-cover)問(wèn)題。

例13.10考察如圖13.6所示的具有17個(gè)頂點(diǎn)的二分圖，A={1,2,3,16,17}和B={4,5,6,7,8,9,10,11,12,13,14,15}，子集A’={1,16,17}是B的最小覆蓋：1覆蓋{4,6,7,8,9,13};16覆蓋{5,6,8,12,14,15};17覆蓋{4,9,10,11}圖13.6例13.10所使用的圖集合覆蓋問(wèn)題偶圖覆蓋等價(jià)于集合覆蓋問(wèn)題。集合覆蓋問(wèn)題是NP－難度問(wèn)題。集合覆蓋問(wèn)題：n個(gè)集合的族F＝滿足，設(shè)為F的子族且則稱其為U的一個(gè)覆蓋集合覆蓋問(wèn)題是指找包含的集合數(shù)目最小的覆蓋。

例13.11

令F={S1,

…,S5

}，U={4,5,...,15}，S1={4,6,7,8,9,13}，S2={4,5,6,8}，

S3={8,10,12,14,15}，S4={5,6,8,12,14,15}，S5={4,9,10,11}。S’={S1,S4,S5}是一個(gè)大小為3的覆蓋，沒(méi)有更小的覆蓋，S’即為最小覆蓋。這個(gè)集合覆蓋問(wèn)題可變換為圖13.6的偶圖，即用頂點(diǎn)1，2，3，16和17分別表示集合S1，S2，S3，S4和S5，頂點(diǎn)j

表示集合U中的元素j，4≤j≤15。兩個(gè)問(wèn)題等價(jià)，都是NP－難度問(wèn)題偶圖覆蓋問(wèn)題的貪心解貪心策略：選擇覆蓋B中那些尚未被覆蓋的頂點(diǎn)數(shù)最多的A的節(jié)點(diǎn)對(duì)圖13.6應(yīng)用上述貪心法，得到

A'＝{1,16,17}，算法描述見(jiàn)圖13.7圖13.7貪心啟發(fā)式算法的偽代碼實(shí)現(xiàn)問(wèn)題設(shè),為i覆蓋的B中尚未被覆蓋的頂點(diǎn)數(shù)。為動(dòng)態(tài)變化的量。需設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)對(duì)其進(jìn)行維護(hù)。要求：取最大的頂點(diǎn)i

相應(yīng)修改余下頂點(diǎn)的New值

(見(jiàn)13.8的偽代碼)

圖13.8圖13.7的細(xì)化例13.13以圖13.6為例，初始：

New=[6,4,5,6,4]，選頂點(diǎn)16，c={16}16覆蓋B中(5,6,8,12,14,15);5,6,8與A中2相連所以New(2)修改為4-3=1;New(16)為0;

New(1)為6-2=4;New(3)為1;New(17)為4選頂點(diǎn)1,頂點(diǎn)4被覆蓋,4與2有邊相連所以New(2)值減1；6已被覆蓋;7被覆蓋,New(7)減1使用二維數(shù)組存儲(chǔ)New的值更新New的時(shí)間為O(e)，其中e為二分圖中邊的數(shù)目。若使用鄰接矩陣，則需要花O(n2)的時(shí)間來(lái)尋找圖中的邊若用鄰接鏈表，則需要O(n+e)的時(shí)間

逐步選擇頂點(diǎn)所需時(shí)間為O(SizeofA),其中SizeofA=|A|。A的所有頂點(diǎn)都有可能被選擇，因此，所需步驟書為O