關(guān)鍵路徑算法ppt課件-展示頁
2025-05-15 06:28本頁面
【正文】 xType data。 ? struct ArcNode *nextarc。 ? typedef struct ArcNode ? { int adjvex。 ? /*圖的關(guān)鍵路徑問題的算法 */ ? include ? include ? define MAXVEX 100 ? define TRUE 1 ? define FALSE 0 ? typedef char VertexType[MAXVEX]。若某條弧滿足條件 e(s)=l(s)，則為關(guān)鍵活動。如果得到的拓撲有序序列中頂點個數(shù)小于網(wǎng)中頂點數(shù) n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟 (3)。因此，可以在拓撲排序的基礎上計算 ve(j1)和 vl(j1)。 ? 這兩個遞推公式的計算必須分別在拓撲有序和逆拓撲有序的前提下進行。如果活動 ai由弧 j,k表示，其持續(xù)時間記為 dut(j,k),則有如下關(guān)系： ? e(i ) = ve(j) (71) ? l (i) = vl(k)dut(j,k) ? 求 ve(j)和 vl(j)需分兩步進行： ? （ 1）從 ve(0)開始向前遞推 ? ve(j) = Max{ve(i)+dut(i,j)} ? i ? i,j ∈ T, j=1,2,3,…,n 1 （ 72） ? 其中， T是所有以第 j個頂點為尾的弧的結(jié)合。 ? 由上分析可知，辨別關(guān)鍵活動就是要找 e(i)=l(i)的活動。顯然，關(guān)鍵路徑上的所有活動都是關(guān)鍵活動，因此提前完成非關(guān)鍵活動并不能加快工程的進度。兩者之差 l(i)e(i)意味著完成活動 ai的時間余量。我們用 e(i)表示活動 ai的最早開始時間。假設開始點是 v1，從 v1到 vi的最長路徑長度叫做事件 vi的最早發(fā)生時間。 ? 和 AOV網(wǎng)不同，對 AOE網(wǎng)有待研究的問題是： ? (1)完成整項工程至少需要多少時間 ? ? (2)哪些活動是影響工程進度的關(guān)鍵 ? ? 由于在 AOE網(wǎng)中有些活動可以并行地進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度 (這里所說的路徑長度是指路徑上各活動持續(xù)時間之和，不是路徑上弧的數(shù)目 )。與每個活動相聯(lián)系的數(shù)是執(zhí)行該活動所需的時間。其中有 9個事件 v1， v2， v3， … ， v9，每個事件表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始。通常， AOE網(wǎng)可用來估算工程的完成時間。關(guān)鍵路徑 ?與 AOV網(wǎng)相對應的是 AOE網(wǎng) (Activity On Edge)即邊表示活動的網(wǎng)。 AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中，頂點表示事件 (Event)，弧表示活動，權(quán)表示活動持續(xù)的時間。 ?例如，圖 11項活動的 AOE網(wǎng)。如 v1表示整個工程開始， v9表示整個工程結(jié)束， v5表示 a4和 a5已經(jīng)完成， a7和 a8可以開始。比如，活動 a1需要 6天， a2需要 4天等。路徑長度最長的路徑叫做關(guān)鍵路徑 (Critical Path)。這個時間決定了所有以 vi為尾的弧所表示的活動的最早開始時間。還可以定義一個活動的最遲開始時間 l(i)，這是在不推遲整個工程完成的前提下，活動ai最遲必須開始進行的時間。我們把 l(i)=e(i)的活動叫做關(guān)鍵活動。因此，分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動，以便爭取提高關(guān)鍵活動的工效，縮短整個工期。為了求得 AOE網(wǎng)中活
教學課件相關(guān)推薦
鄂ICP備17016276號-1