拓?fù)渑判蜿P(guān)鍵路徑

拓?fù)渑判颉㈥P(guān)鍵路徑AOV網(wǎng)在日常生活中，一項(xiàng)大的工程可以看作是由若干個(gè)子工程（這些子工程稱為“活動(dòng)”）組成的集合，這些子工程（活動(dòng)）之間必定存在一些先后關(guān)系，即某些子工程（活動(dòng)）必須在其他一些子工程（活動(dòng)）完成之后才能開始，我們可以用有向圖來(lái)形象地表示這些子工程（活動(dòng)）之間的先后關(guān)系，子工程（活動(dòng)）為頂點(diǎn)，子工程（活動(dòng)）之間的先后關(guān)系為有向邊，這種有向圖稱為“頂點(diǎn)活動(dòng)網(wǎng)絡(luò)”，又稱AOV網(wǎng)。一個(gè)AOV網(wǎng)應(yīng)該是一個(gè)有向無(wú)環(huán)圖，即不應(yīng)該帶有回路，否則必定會(huì)有一些活動(dòng)互相牽制，造成環(huán)中的活動(dòng)都無(wú)法進(jìn)行。①②③④⑤⑥⑦0拓?fù)渑判颍喊巡粠Щ芈稟OV網(wǎng)中所有活動(dòng)排成一個(gè)線性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，這個(gè)過(guò)程成為“拓?fù)渑判颉?，所得到的活?dòng)序列稱為“拓?fù)湫蛄小薄Ｐ枰⒁獾氖茿OV網(wǎng)的拓?fù)湫蛄惺遣晃ㄒ坏摹Ｈ鐖D有以下幾種拓?fù)湫蛄校?2143567、01243657、02143657、01243567拓?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)數(shù)，則輸出“有回路信息”，否則輸出的頂點(diǎn)序列就是一種拓?fù)湫蛄小＂佗冖邰堍茛蔻?拓?fù)湫蛄心M：0124356701243567算法框架：（采用鄰接矩陣描述）Programaov(input,output);constmaxvtxnum=100;

varg:array[0..maxvtxnum,1..maxvtxnum]ofinteger;s:array[1..maxvtxnum]ofboolean;{標(biāo)記數(shù)組}list:array[1..maxvtxnum]ofinteger;{記錄拓?fù)湫蛄衹

i,j,k,n:integer;begin

assign(input,’aov.in’);reset(input);

assign(output,’aov.out’);rewrite(output);

readln(n);fori:=1tondoforj:=1tondoread(g[i,j]);fori:=1tondos[i]:=false;

fork:=1tondobeginforj:=1tondobeging[0,j]:=0;{統(tǒng)計(jì)頂點(diǎn)的入度}fori:=1tondog[0,j]:=g[0,j]+g[i,j];end;j:=1;{查找入度為0，且未在序列中出現(xiàn)過(guò)}while((g[0,j]>0)ors[j])and(j<n)doj:=j+1;ifj>nthenexit;{存在環(huán)}

list[k]:=j;s[j]:=true;fori:=1tondog[j,i]:=0;end;ifk<nthenwrite(‘error’)elsefori:=1tondowrite(list[i]:2);

close(input);close(output);End.應(yīng)用實(shí)例士兵排隊(duì)【問(wèn)題描述】有n個(gè)士兵（1≤n≤26），編號(hào)依次為A、B、C…隊(duì)列訓(xùn)練時(shí)，指揮官要把一些士兵從高到矮依次排成一行。但現(xiàn)在指揮官不能直接獲得每個(gè)人的身高信息，只能獲得“p1比p2高”這樣的比較結(jié)果（p1，p2∈{‘A’,…‘z’}），記為p1>p2。根據(jù)這些關(guān)系，求出排隊(duì)方案。假設(shè)比較結(jié)果為：A>B,B>D,F>D,B>F，則排隊(duì)方案為ABFD[輸入數(shù)據(jù)]第一行：n第二行：n個(gè)大寫字母（表示士兵編號(hào)）；第三行：k（表示高矮關(guān)系個(gè)數(shù)）；接下來(lái)k行：p1p2(表示高矮關(guān)系)AOE網(wǎng)一個(gè)活動(dòng)的完成總需要一定的時(shí)間，為了能估算出某個(gè)活動(dòng)的開始時(shí)間，找出那些影響工程完成時(shí)間的最主要的活動(dòng)，我們可以利用帶權(quán)的有向圖。圖中的邊表示活動(dòng)，邊上的權(quán)表示完成該活動(dòng)所需要的時(shí)間，一條邊的兩個(gè)頂點(diǎn)分別表示活動(dòng)的開始事件和結(jié)束事件，這種用邊表示活動(dòng)的網(wǎng)絡(luò)，稱為“AOE網(wǎng)”。其中兩個(gè)特殊的頂點(diǎn)（事件），分別稱為源點(diǎn)和匯點(diǎn)。源點(diǎn)表示整個(gè)工程的開始，通常令第一個(gè)事件作為源點(diǎn)，它只有出邊沒(méi)有入邊；匯點(diǎn)表示整個(gè)工程的結(jié)束，通常令最后一個(gè)事件（事件n）作為匯點(diǎn)，它只有入邊沒(méi)有出邊；其余事件的編號(hào)為2到n-1。在實(shí)際應(yīng)用中，AOE網(wǎng)應(yīng)該沒(méi)有回路的，并且存在唯一的入度為0的源點(diǎn)和唯一出度為0的匯點(diǎn)①②③④⑤⑥⑦0AOE網(wǎng)研究的問(wèn)題：1.完成整項(xiàng)工程至少需要多少時(shí)間？

2.哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？關(guān)鍵路徑由于在AOE網(wǎng)中有些活動(dòng)可以并行地進(jìn)行，所以完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑。764533432542引入兩個(gè)定義事件的最早發(fā)生時(shí)間：時(shí)間0最早發(fā)生時(shí)間是0，事件7的最早發(fā)生時(shí)間是整個(gè)工程最快完成時(shí)間，事件4的發(fā)生時(shí)間是以4為終點(diǎn)的所有弧上活動(dòng)全部完成的最快時(shí)間。事件的最遲發(fā)生時(shí)間：由于0是整個(gè)工程的起點(diǎn)，因此事件0的最遲發(fā)生時(shí)間是0，事件4的最遲發(fā)生時(shí)間是保證不影響進(jìn)度的前提下最遲可以發(fā)生的時(shí)間。顯然，事件7的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間相等。最早發(fā)生時(shí)間的計(jì)算設(shè)數(shù)組earliest[1..n]表示所有事件的最早發(fā)生時(shí)間，則我們可以按照拓?fù)渑判蛞来斡?jì)算出earliest[k];Earliest[1]=0Earliest[k]=max{earliest[j]+dut[j,k]}(其中，事件j是事件k的直接前驅(qū)事件，dut[j,k]表示邊<j,k>上的權(quán)。)①②③④⑤⑥⑦0764533432542最遲發(fā)生時(shí)間的計(jì)算設(shè)用數(shù)組lastest[1..n]表示最遲發(fā)生時(shí)間，按照逆拓?fù)渑判蛞来斡?jì)算出所有事件的最遲發(fā)生時(shí)間：Lastest[n]=earliest[n]Lastest[j]=min{lastest[k]-dut[j,k]}(其中，事件k是事件j的直接后繼事件，dut[j,k]表示邊<j,k>上的權(quán)。)①②③④⑤⑥⑦0764533432542關(guān)鍵路徑的計(jì)算01243567earliest067Max（11，11）=11Max（9，14）=14Max（16，15）=1614Max（18，18，19）=19lastest067Min（11，13，12）=11Min（14，15）=1417