第4章第7節(jié)拓?fù)渑判蚺c關(guān)鍵路徑(C++版)

1、第七節(jié)第七節(jié) 拓?fù)渑判蚺c關(guān)鍵路徑拓?fù)渑判蚺c關(guān)鍵路徑引入AOV網(wǎng) 在日常生活中，一項大的工程可以看作是由若干個子工程（這些子工程稱為“活動” ）組成的集合，這些子工程（活動）之間必定存在一些先后關(guān)系，即某些子工程（活動）必須在其它一些子工程（活動）完成之后才能開始，我們可以用有向圖來形象地表示這些子工程（活動）之間的先后關(guān)系，子工程（活動）為頂點(diǎn)，子工程（活動）之間的先后關(guān)系為有向邊，這種有向圖稱為“頂點(diǎn)活動網(wǎng)絡(luò)” ，又稱“AOV網(wǎng)” 。123567894引入在AOV網(wǎng)中，有向邊代表子工程（活動）的先后關(guān)系，我們把一條有向邊起點(diǎn)的活動成為終點(diǎn)活動的前驅(qū)活動，同理終點(diǎn)的活動稱為起點(diǎn)活動的后繼活動。

2、而只有當(dāng)一個活動全部的前驅(qū)全部都完成之后，這個活動才能進(jìn)行。例如在上圖中，只有當(dāng)工程1完成之后，工程2、3、4、5、6才能開始進(jìn)行。只有當(dāng)2、3、4全部完成之后，7才能開始進(jìn)行。一個AOV網(wǎng)必定是一個有向無環(huán)圖，即不應(yīng)該帶有回路。否則，會出現(xiàn)先后關(guān)系的自相矛盾。1234上圖就是一個出現(xiàn)環(huán)產(chǎn)生自相矛盾的情況。4是1的前驅(qū)，想完成1，必須先完成4。3是4的前驅(qū)，而2是3的前驅(qū)，1又是2的前驅(qū)。最后造成想完成1，必須先完成1本身，這顯然出現(xiàn)了矛盾。拓?fù)渑判蛩惴?拓?fù)渑判蛩惴ǎ贿m用于AOV網(wǎng)（有向無環(huán)圖）。把AOV網(wǎng)中的所有活動排成一個序列， 使得每個活動的所有前驅(qū)活動都排在該活動的前面，這個過程稱

3、為“拓?fù)渑判颉?，所得到的活動序列稱為“拓?fù)湫蛄小薄Ｒ粋€AOV網(wǎng)的拓?fù)湫蛄惺遣晃ㄒ坏?，例如下面的這張圖，它的拓?fù)湫蛄锌梢允牵篈BCDE，也可以是ACBDE，或是ADBCE。在下圖所示的AOV網(wǎng)中，工程B和工程C顯然可以同時進(jìn)行，先后無所謂；但工程E卻要等工程B、C、D都完成以后才能進(jìn)行。ABCED構(gòu)造拓?fù)湫蛄锌梢詭椭覀兒侠戆才乓粋€工程的進(jìn)度，由AOV網(wǎng)構(gòu)造拓?fù)湫蛄芯哂泻芨叩膶?shí)際應(yīng)用價值。算法思想：構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄋ枷牒芎唵危哼x擇一個入度為0的頂點(diǎn)并輸出然后從AOV網(wǎng)中刪除此頂點(diǎn)及以此頂點(diǎn)為起點(diǎn)的所有關(guān)聯(lián)邊；重復(fù)上述兩步，直到不存在入度為0的頂點(diǎn)為止。若輸出的頂點(diǎn)數(shù)小于AOV網(wǎng)中的頂點(diǎn)

4、數(shù)，則輸出“有回路信息”，否則輸出的頂點(diǎn)序列就是一種拓?fù)湫蛄袕牡谒牟娇梢钥闯?，拓?fù)渑判蚩梢杂脕砼袛嘁粋€有向圖是否有環(huán)。只有有向無環(huán)圖才存在拓?fù)湫蛄?。拓?fù)渑判蛩惴?算法實(shí)現(xiàn)： a) 數(shù)據(jù)結(jié)構(gòu)：indgri: 頂點(diǎn)i的入度; stack : 棧 b) 初始化:top=0 (棧頂指針置零) c) 將初始狀態(tài)所有入度為0的頂點(diǎn)壓棧 d) I=0 (計數(shù)器) e) while 棧非空(top0) i. 棧頂?shù)捻旤c(diǎn)v出棧；top-1; 輸出v；i+； ii. for v的每一個后繼頂點(diǎn)u 1. indgru-; u的入度減1 2. if （u的入度變?yōu)?） 頂點(diǎn)u入棧 f) 算法結(jié)束這個程序采用棧來找出入

5、度為0的點(diǎn)，棧里的頂點(diǎn)，都是入度為0的點(diǎn)。我們結(jié)合上圖詳細(xì)講解：ABCD開始時，只有A入度為0，A入棧。棧：A拓?fù)渑判蛩惴?BCD棧頂元素A出棧并輸出A，A的后繼B、C入度減1，相當(dāng)于刪除A的所有關(guān)聯(lián)邊棧：空拓?fù)湫蛄校篈BCDB、C的入度都變成0，依次將B、C入棧。棧：BC（入棧順序不唯一）拓?fù)湫蛄校篈拓?fù)渑判蛩惴?BD棧頂元素C出棧并輸出C，C的后繼D入度減1棧：B拓?fù)湫蛄校篈CD棧頂元素B出棧并輸出B，B的后繼D入度再減1。這時D入度為0，入棧。棧：D拓?fù)湫蛄校篈CB拓?fù)渑判蛩惴?D棧頂元素D出棧并輸出D。棧空，結(jié)束棧：空拓?fù)湫蛄校篈CBD（不唯一）簡單&高效&實(shí)用的算法。

6、上述實(shí)現(xiàn)方法復(fù)雜度O(V+E)。拓?fù)渑判蛩惴?【例4-12】、家譜樹【問題描述】 有個人的家族很大，輩分關(guān)系很混亂，請你幫整理一下這種關(guān)系。 給出每個人的孩子的信息。 輸出一個序列，使得每個人的后輩都比那個人后列出?！据斎敫袷健?第1行一個整數(shù)N（1=N=100），表示家族的人數(shù)。 接下來N行，第I行描述第I個人的兒子。 每行最后是0表示描述完畢。【輸出格式】 輸出一個序列，使得每個人的后輩都比那個人后列出。 如果有多解輸出任意一解。【輸入樣例】 5 0 4 5 1 0 1 0 5 3 0 3 0【輸出樣例】 2 4 5 3 1拓?fù)渑判蛩惴?【參考程序】/gentree#include#inc

7、ludeusing namespace std;int a101101,c101,r101,ans101;int i,j,tot,temp,num,n,m;int main() freopen(gentree.in,r,stdin); freopen(gentree.out,w,stdout); cin n; for (i = 1; i j; if (j !=0 ) ci+; /ci用來存點(diǎn)i的出度 aici = j; rj+; /ai,-1用來存點(diǎn)i的入度。 while (j != 0); 拓?fù)渑判蛩惴?for (i = 1; i = n; i+) if (ri = 0) ans+tot =

8、 i; /把圖中所有入度為0的點(diǎn)入棧，棧用一維數(shù)組ans表示 do temp = anstot; cout temp ; tot-;num+; /棧頂元素出棧并輸出 for (i = 1; i = ctemp; i+) ratempi-; if (ratempi = 0) /如果入度減1后變成0，則將這個后繼點(diǎn)入棧 ans+tot = atempi; while (num != n); /如果輸出的點(diǎn)的數(shù)目num等于n，說明算法結(jié)束 return 0;拓?fù)渑判蛩惴?【例4-13】獎金【問題描述】由于無敵的凡凡在2005年世界英俊帥氣男總決選中勝出，Yali Company總經(jīng)理Mr.Z心情好，

9、決定給每位員工發(fā)獎金。公司決定以每個人本年在公司的貢獻(xiàn)為標(biāo)準(zhǔn)來計算他們得到獎金的多少。于是Mr.Z下令召開m方會談。每位參加會談的代表提出了自己的意見：“我認(rèn)為員工a的獎金應(yīng)該比b高！”Mr.Z決定要找出一種獎金方案，滿足各位代表的意見，且同時使得總獎金數(shù)最少。每位員工獎金最少為100元。 【輸入格式】第一行兩個整數(shù)n,m，表示員工總數(shù)和代表數(shù)；以下m行，每行2個整數(shù)a,b，表示某個代表認(rèn)為第a號員工獎金應(yīng)該比第b號員工高。 【輸出格式】若無法找到合理方案，則輸出“Poor Xed”；否則輸出一個數(shù)表示最少總獎金。【輸入樣例】2 11 2【輸出樣例】201拓?fù)渑判蛩惴?【數(shù)據(jù)規(guī)?！?0的數(shù)據(jù)滿

10、足n=1000，m=2000；100的數(shù)據(jù)滿足n=10000，m=20000。【算法分析】首先構(gòu)圖，若存在條件“a的錢比b多”則從b引一條有向指向a；然后拓?fù)渑判颍魺o法完成排序則表示問題無解（存在圈）；若可以得到完整的拓?fù)湫蛄?，則按序列順序進(jìn)行遞推： 設(shè)fi表示第i個人能拿的最少獎金數(shù)； 首先所有fi=100（題目中給定的最小值）； 然后按照拓?fù)漤樞蚩疾烀總€點(diǎn)i，若存在有向邊(j,i)，則表示fi必須比fj大，因此我們令fi = Max fi , fj+1 即可； 遞推完成之后所有fi的值也就確定了，而答案就等于f1+fn。拓?fù)渑判蛩惴?【參考程序】#includeusing namespa

11、ce std;int a10001301=0,into10001,ans10001,m,n,money;void init() /讀入數(shù)據(jù)，并構(gòu)建圖，統(tǒng)計入度 int i,x,y; cinnm; for(i=1;ixy; ay0+; /記錄由y引出邊的數(shù)目 ayay0=x; /記錄由ay0引出邊的頂點(diǎn) intox+; /統(tǒng)計入度 bool topsort() /拓?fù)渑判?int t,tot,k,i,j; tot=0;k=0; while(totn) /tot頂點(diǎn)個數(shù) t=0; /用來判斷有無環(huán) for(i=1;i=n;i+) if(intoi=0) 拓?fù)渑判蛩惴?tot+;t+;money+=

12、100; anst=i; intoi=0 xfffffff; if(t=0)return false; /存在環(huán) money+=k*t;k+; for(i=1;i=t;i+) /去掉相連的邊 for(j=1;j=aansi0;j+)intoaansij-; return true;int main() init();money=0; if(topsort()coutmoneyendl; else coutPoor Xedendl; return 0;關(guān)鍵路徑 利用AOV網(wǎng)絡(luò)，對其進(jìn)行拓?fù)渑判蚰軐こ讨谢顒拥南群箜樞蜃鞒霭才?。但一個活動的完成總需要一定的時間，為了能估算出某個活動的開始時間，找出

13、那些影響工程完成時間的最主要的活動，我們可以利用帶權(quán)的有向網(wǎng)，圖中的邊表示活動，邊上的權(quán)表示完成該活動所需要的時間，一條邊的兩個頂點(diǎn)分別表示活動的開始事件和結(jié)束事件，這種用邊表示活動的網(wǎng)絡(luò)，稱為“AOE網(wǎng)”。其中，有兩個特殊的頂點(diǎn)（事件），分別稱為源點(diǎn)和匯點(diǎn)，源點(diǎn)表示整個工程的開始，通常令第一個事件（事件1）作為源點(diǎn)，它只有出邊沒有入邊；匯點(diǎn)表示整個工程的結(jié)束，通常令最后一個事件（事件n）作為匯點(diǎn)，它只有入邊沒有出邊；其余事件的編號為2到n-1。在實(shí)際應(yīng)用中，AOE網(wǎng)應(yīng)該是沒有回路的，并且存在唯一的入度為0的源點(diǎn)和唯一的出度為0的匯點(diǎn)。下圖表示一個具有12個活動的AOE網(wǎng)。圖中有8個頂點(diǎn)，分別

14、表示事件0到7，其中，0表示開始事件，7表示結(jié)束事件，邊上的權(quán)表示完成該活動所需要的時間。關(guān)鍵路徑 AOE網(wǎng)絡(luò)要研究的問題是完成整個工程至少需要多少時間？哪些活動是影響工程進(jìn)度的關(guān)鍵？下面先討論一個事件的最早發(fā)生時間和一個活動的最早開始時間。如下圖，事件Vj必須在它的所有入邊活動eik（1kn）都完成后才能發(fā)生?；顒觘ik（1kn）的最早開始時間是與它對應(yīng)的起點(diǎn)事件Vik的最早發(fā)生時間。所有以事件Vj為起點(diǎn)事件的出邊活動ejk（1km）的最早開始時間都等于事件Vj的最早發(fā)生時間。所以，我們可以從源點(diǎn)出發(fā)按照上述方法，求出所有事件的最早發(fā)生時間。關(guān)鍵路徑 設(shè)數(shù)組earliest1.n表示所有事件

15、的最早發(fā)生時間，則我們可以按照拓?fù)漤樞蛞来斡嬎愠鰁arliestk：earliest1=0earliestk=maxearliestj+dutjk (其中，事件j是事件k的直接前驅(qū)事件，dutjk表示邊上的權(quán))對于上圖，用上述方法求earliest0.7的過程如下：earliest0=0earliest1=earliest0+dut01=0+6=6earliest2=earliest0+dut02=0+7=7earliest4=maxearliest1+dut14，earliest2+dut24=max6+5,7+4=11earliest3=maxearliest1+dut13，earlies

16、t4+dut43=max6+3,11+3=14earliest5=maxearliest3+dut35，earliest4+dut45=max14+2,11+4=16earliest6=earliest4+dut46=11+3=14earliest7=maxearliest3+dut37，earliest5+dut57, earliest6+dut67=max14+5,16+2,14+4=19關(guān)鍵路徑 最后得到的earliest7就是匯點(diǎn)的最早發(fā)生時間，從而可知整個工程至少需要19天完成。但是，在不影響整個工程按時完成的前提下，一些事件可以不在最早發(fā)生時間發(fā)生，而向后推遲一段時間，我們把事件最

17、晚必須發(fā)生的時間稱為該事件的最遲發(fā)生時間。同樣，有些活動也可以推遲一段時間完成而不影響整個工程的完成，我們把活動最晚必須開始的時間稱為該活動的最遲開始時間。一個事件在最遲發(fā)生時間內(nèi)仍沒發(fā)生，或一個活動在最遲開始時間內(nèi)仍沒開始，則必然會影響整個工程的按時完成。事件Vj的最遲發(fā)生時間應(yīng)該為：它的所有直接后繼事件Vjk（1km）的最遲發(fā)生時間減去相應(yīng)邊上的權(quán)（活動ejk需要時間），取其中的最小值。且匯點(diǎn)的最遲發(fā)生時間就是它的最早發(fā)生時間，再按照逆拓?fù)漤樞蛞来斡嬎愠鏊惺录淖钸t發(fā)生時間，設(shè)用數(shù)組lastest1.n表示，即：lastestn=earliestnlastestj=minlastestk

18、-dutjk (其中，事件k是事件j的直接后繼事件，dutj,k表示邊上的權(quán))對于上圖，用上述方法求lastest 0.7的過程如下：lastest7=earliest7=19lastest6=lastest7-dut67=19-4=15lastest5=lastest7-dut57=19-2=17lastest3=minlastest5-dut35，lastest7-dut37 =min17-2,19-5 =14關(guān)鍵路徑 lastest4=minlastest3-dut43，lastest5-dut45, lastest6-dut46 =min14-3,17-4,15-3 =11lastes

19、t2=lastest4-dut24=11-4=7lastest1=minlastest3-dut13，lastest4-dut14 =min14-3,11-5 =6lastest0=minlastest1-dut01，lastest2-dut02 =min6-6,7-7 =0計算好每個事件的最早和最遲發(fā)生時間后，我們可以很容易地算出每個活動的最早和最遲開始時間，假設(shè)分別用actearliest和actlastest數(shù)組表示，設(shè)活動i的兩端事件分別為事件j和事件k,如下所示：活動i事件j 事件k則：actearliesti=earliestjactlastesti=lastestk-dutjk關(guān)

20、鍵路徑 對于上圖，用上述方法求得所有活動的最早和最遲開始時間如下表：活動活動 21 1424353743454 5 6 最早最早0 00 06 66 67 71414141411111111111116161414最遲最遲0 00 011116 67 71515141411111313121217171515余量余量0 00 05 50 00 01 10 00 02 21 11 11 1 上表中的余量（稱為開始時間余量）是該活動的最遲開始時間減去最早開始時間，余量不等于0的活動表示該活動不一定要在最早開始時間時就進(jìn)行，可以拖延一定的余量時間再進(jìn)行，也不會影響整個工程的完成。而余量等于0的活動必

21、須在最早開始時間時進(jìn)行，而且在規(guī)定的工期內(nèi)完成，否則將影響整個工程的完成。我們把開始時間余量為0的活動稱為“關(guān)鍵活動”，由關(guān)鍵活動所形成的從源點(diǎn)到匯點(diǎn)的每一條路徑稱為“關(guān)鍵路徑”。關(guān)鍵路徑 上圖所示的AOE網(wǎng)的關(guān)鍵路徑如下圖所示。細(xì)心的讀者可能已經(jīng)發(fā)現(xiàn)，其實(shí)關(guān)鍵路徑就是從源點(diǎn)到匯點(diǎn)具有最大路徑長度的那些路徑。這很容易理解，因?yàn)檎麄€工程的工期就是按照最長路徑計算出來的。很顯然，要想縮短整個工程的工期，就應(yīng)該想法設(shè)法去縮短關(guān)鍵活動的持續(xù)時間。讀者可以根據(jù)上面的思想編程求出AOE網(wǎng)的關(guān)鍵路徑。上機(jī)練習(xí) 1、煩人的幻燈片【問題描述】李教授將于今天下午作一次非常重要的演講。不信的事他不是一個非常愛整潔的

22、人，他把自己演講要用的幻燈片隨便堆在了一起。因此，演講之前他不得不去整理這些幻燈片。作為一個講求效率的學(xué)者，他希望盡可能簡單地完成它。教授這次演講一共要用n n張幻燈片（n=26n=26），這n n張幻燈片按照演講要使用的順序已經(jīng)用數(shù)字1n1n編了號。因?yàn)榛脽羝峭该鞯?，所以我們不能一下子看清每一個數(shù)字所對應(yīng)的幻燈片?，F(xiàn)在我們用大寫字母A,B,CA,B,C再次把幻燈片依次編號。你的任務(wù)是編寫一個程序，把幻燈片的數(shù)字編號和字母編號對應(yīng)起來，顯然這種對應(yīng)應(yīng)該是唯一的；若出現(xiàn)多種對應(yīng)的情況或是某些數(shù)字編號和字母編號對應(yīng)不起來，我們稱對應(yīng)是無法實(shí)現(xiàn)的?！据斎敫袷健课募牡谝恍兄挥幸粋€整數(shù)n n，表示有n張幻燈片，接下來的n n行每行包括4 4個整數(shù)xmin,xmax,ymin,ymaxxmin,xmax,ymin,ymax（整數(shù)之間用空格分開）為幻燈片的坐標(biāo)，這n n張幻燈片按其在文件中出現(xiàn)的順序從前到后依次編號為A,B,CA,B,C，再接下來的n行依次為n n個數(shù)字編號的坐標(biāo)x,yx,y，顯然在幻燈片之外是不會有數(shù)字的?！据敵龈袷健咳羰菍?yīng)