計(jì)算關(guān)鍵路徑

1、五、五、 計(jì)算關(guān)鍵路徑計(jì)算關(guān)鍵路徑【例題】計(jì)算能影響整個(gè)計(jì)劃完成時(shí)間的關(guān)鍵活動(dòng)【例題】計(jì)算能影響整個(gè)計(jì)劃完成時(shí)間的關(guān)鍵活動(dòng)工廠的工程計(jì)劃用一張有向圖表示，有向圖的結(jié)點(diǎn)表示事件，有向邊表示活動(dòng)，邊上的權(quán)標(biāo)明一項(xiàng)活動(dòng)需要的時(shí)間。結(jié)點(diǎn)所表示的事件實(shí)際上就是它入邊代表的活動(dòng)均已完成，出邊代表的活動(dòng)可以開始這樣一種狀態(tài)。例如上圖含12項(xiàng)活動(dòng)、9個(gè)事件。其中事件v1表示開始時(shí)活動(dòng)a1、a2、a3并行實(shí)施；事件v5代表活動(dòng)a4、a5已經(jīng)完成，活動(dòng)a7、a8可以開始。V9表示整個(gè)計(jì)劃完成?；顒?dòng)依事件的順序要求進(jìn)行。例如活動(dòng)a4、a5、a6只有當(dāng)事件v2、v3、v4分別發(fā)生后才能進(jìn)行，而它們的完成又標(biāo)志事件v5

2、、v6的發(fā)生。當(dāng)活動(dòng)a10、a11、a12完成后，整個(gè)計(jì)劃完成。上述有向圖存在唯一的入度為0的開始結(jié)點(diǎn)v1，表明整個(gè)計(jì)劃從該事件開始；存在唯一的出度為0的完成結(jié)點(diǎn)vn，表明該事件完成后，整個(gè)計(jì)劃結(jié)束?，F(xiàn)在的問題是，整個(gè)計(jì)劃完成至少需要多少時(shí)間，為提前完成計(jì)劃應(yīng)該加快哪些活動(dòng)的速度。輸入：輸入： n(事件數(shù)，1n100) e(活動(dòng)數(shù)，1e4000)。以下為e行，每行為連接兩個(gè)事件的序號(hào)以及活動(dòng)需要的時(shí)間輸出：輸出：完成整個(gè)計(jì)劃的最少時(shí)間。以下k行，每行為一個(gè)關(guān)鍵活動(dòng)（i，j）和目前花費(fèi)的時(shí)間wij，加快該活動(dòng)的速度能提前完成計(jì)劃 關(guān)鍵路徑的由來關(guān)鍵路徑的由來如果有向圖的結(jié)點(diǎn)表示活動(dòng)，有向邊表示活

3、動(dòng)間的優(yōu)先關(guān)系，那么我們通過拓?fù)渑判驅(qū)D中的結(jié)點(diǎn)排成一個(gè)滿足活動(dòng)先后順序要求的線性序列。如果有向有權(quán)圖滿足下述條件存在唯一的入度為0的結(jié)點(diǎn)和唯一的出度為0的結(jié)點(diǎn)；可通過拓?fù)渑判驅(qū)D中的結(jié)點(diǎn)排成一個(gè)滿足活動(dòng)先后順序要求的線性序列（即有向圖沒有回路）則稱該有向有權(quán)圖為AOV網(wǎng)（活動(dòng)結(jié)點(diǎn)網(wǎng)絡(luò)）。 利用AOV網(wǎng)可以估算出整個(gè)計(jì)劃完成至少需要多少時(shí)間，為提前完成計(jì)劃應(yīng)該加快哪些活動(dòng)的速度等問題。解決這些問題有一種有效的方法求關(guān)鍵路徑方法。由于AOV網(wǎng)中的活動(dòng)可以并行進(jìn)行，因此完成整個(gè)計(jì)劃的最少時(shí)間是從開始結(jié)點(diǎn)v1到完成結(jié)點(diǎn)vn的最長路徑長度（路徑上各邊權(quán)的和）。具有最大長度的路徑稱作關(guān)鍵路徑。在上圖中v

4、1v2v5v8v9是一條關(guān)鍵路徑，長度為18。換句話說，整個(gè)計(jì)劃至少需要18個(gè)時(shí)間單位完成。關(guān)鍵路徑上的活動(dòng)又稱關(guān)鍵活動(dòng)。如果不能按期完成這些活動(dòng)會(huì)貽誤整個(gè)計(jì)劃。找出關(guān)鍵活動(dòng)后就可以適當(dāng)調(diào)度，集中力量于關(guān)鍵活動(dòng)，以保證計(jì)劃如期或提前完成。關(guān)鍵路徑的計(jì)算關(guān)鍵路徑的計(jì)算為了找出關(guān)鍵活動(dòng)，我們先定義幾個(gè)變量： nAOV網(wǎng)的結(jié)點(diǎn)數(shù)； mAOV網(wǎng)的有向邊數(shù)； eeivi事件可能發(fā)生的最早時(shí)間，即從開始結(jié)點(diǎn)v1至結(jié)點(diǎn)vi的最長路徑長度。我們從ee(1)=0開始向前遞推 eej=maxeei+wij|(i,j) E； lei在保證完成結(jié)點(diǎn)vn所代表的事件在een時(shí)刻發(fā)生的前提下，事件vi允許發(fā)生的最晚時(shí) 間

5、，即lei=ee(n)-vi至vn最長路徑長度。我們從len=een出發(fā)向后遞推 lei=minlej-wij |(i,j) E ek活動(dòng)ak（對(duì)應(yīng)邊）可能的最早開始時(shí)間，即等于事件vi的可能的最早發(fā)生時(shí)間eei；lk活動(dòng)ak(對(duì)應(yīng)邊)允許的最晚完成時(shí)間，即等于事件vj允許最晚發(fā)生時(shí)間lej； (1i， jn， 1km) 顯然活動(dòng)ak的最大可利用時(shí)間是lk-ek。若最大可利用時(shí)間等于ak邊所帶的權(quán)wk(即為計(jì)劃時(shí)間)，則ak是關(guān)鍵活動(dòng)。ak延期，則整個(gè)計(jì)劃將順延。若最大可利用時(shí)間大于wk，則ak不是關(guān)鍵活動(dòng)，ak的完成時(shí)間允許超過wk。只要不超過最大可利用時(shí)間，無妨于整個(gè)計(jì)劃完成的進(jìn)度。我們可

6、以采取以下步驟，計(jì)算上面定義的幾個(gè)變量值，從而找到關(guān)鍵活動(dòng)： 計(jì)算能影響整個(gè)計(jì)劃完成時(shí)間的關(guān)鍵活動(dòng)計(jì)算能影響整個(gè)計(jì)劃完成時(shí)間的關(guān)鍵活動(dòng) 在找出關(guān)鍵活動(dòng)后，只要將所有的非關(guān)鍵活動(dòng)從AOV網(wǎng)中去掉，這時(shí)從開始結(jié)點(diǎn)至完成結(jié)點(diǎn)的所有路徑都是關(guān)鍵路徑。AOV網(wǎng)中的關(guān)鍵路徑可能不止一條。并不是加快任一關(guān)鍵活動(dòng)就可以縮短整個(gè)計(jì)劃的完成時(shí)間。只有加快并不是加快任一關(guān)鍵活動(dòng)就可以縮短整個(gè)計(jì)劃的完成時(shí)間。只有加快那些包括在所有關(guān)鍵路徑上的關(guān)鍵活動(dòng)才能達(dá)到目的的。那些包括在所有關(guān)鍵路徑上的關(guān)鍵活動(dòng)才能達(dá)到目的的。設(shè)a為關(guān)鍵路徑組成的01矩陣，a0為輔助矩陣；b為關(guān)鍵活動(dòng)序列，其中bk.x、bk.y和bk.l分別為第

7、k項(xiàng)關(guān)鍵活動(dòng)的兩個(gè)頂點(diǎn)序號(hào)和花費(fèi)；nopath為v1至vn間有路可走的標(biāo)志； 首先計(jì)算關(guān)鍵活動(dòng)序列b和關(guān)鍵活動(dòng)組成的有向圖a。然后逐一地在a圖中去除一條關(guān)鍵活動(dòng)邊，看一看是否存在v1至vn的路徑。如果v1至vn間無路可走,則說明這個(gè)關(guān)鍵活動(dòng)為影響整個(gè)計(jì)劃完成的關(guān)鍵活動(dòng)。判別過程采用深度優(yōu)先搜索procedure dfs(i:integer)；深度優(yōu)先搜索a0圖中由頂點(diǎn)i出發(fā)的所有可能路徑。若存在一條到達(dá)頂點(diǎn)n的路徑，則nopath設(shè)為false；否則為true begin fitrue； if i=n then begin nopathfalse；exit；endthen for j1 to

8、n do begin if (not(fj)and(a0i,j=1) then dfs(j)； end；for end；dfs由此得出算法 活動(dòng)的時(shí)間矩陣w初始化為0；輸入帶權(quán)有向圖的信息（頂點(diǎn)數(shù)n、活動(dòng)數(shù)e和活動(dòng)的時(shí)間矩陣w）；if 圖中的所有頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?then 失敗退出；fillchar(ee，sizeof(ee)，0)；for i1 to n-1 do for j1 to n do 計(jì)算各個(gè)事件的最早發(fā)生時(shí)間表ee if (i,j)E)and(eejeei+wij) then eejeei+wij；輸出完成整個(gè)計(jì)劃的最少時(shí)間een；for i1 to n do leiee

9、n； 所有事件的最晚發(fā)生時(shí)間初始化k0； 關(guān)鍵活動(dòng)數(shù)初始化for in-1 downto 1 do 計(jì)算各個(gè)事件的最晚發(fā)生時(shí)間表le for j1 to n do if (wij0)and(leieej-wij) then leieej-wij；fillchar(a,sizeof(a),0)； 由關(guān)鍵活動(dòng)組成的有向圖a初始化for i1 to n-1 do 計(jì)算關(guān)鍵活動(dòng)和由關(guān)鍵活動(dòng)組成的有向圖a for j1 to n do if (wij0 )and(lej-eei=wij) then begin kk+1；bk.xi；bk.yj；bk.lwij；ai,j1；end；then for t1 to k do 枚舉每一個(gè)關(guān)鍵活動(dòng)Begina0a；a0bt.x，bt.y0；在有向圖a中去除第t個(gè)關(guān)鍵活動(dòng)fillchar(f，sizeof(f)，false)；nopathtrue；訪問標(biāo)志和成功標(biāo)志初始化dfs(1)；通過深度優(yōu)先搜索判斷v1與vn間是否有路if nopath then輸出關(guān)鍵活動(dòng)（bt.x，bt.y）和目