關(guān)鍵路徑算法ppt課件(已修改)
2025-05-18 06:28 本頁(yè)面
【正文】 關(guān)鍵路徑 ?與 AOV網(wǎng)相對(duì)應(yīng)的是 AOE網(wǎng) (Activity On Edge)即邊表示活動(dòng)的網(wǎng)。 AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖，其中，頂點(diǎn)表示事件 (Event)，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間。通常， AOE網(wǎng)可用來估算工程的完成時(shí)間。 ?例如，圖 11項(xiàng)活動(dòng)的 AOE網(wǎng)。其中有 9個(gè)事件 v1， v2， v3， … ， v9，每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開始。如 v1表示整個(gè)工程開始， v9表示整個(gè)工程結(jié)束， v5表示 a4和 a5已經(jīng)完成， a7和 a8可以開始。與每個(gè)活動(dòng)相聯(lián)系的數(shù)是執(zhí)行該活動(dòng)所需的時(shí)間。比如，活動(dòng) a1需要 6天， a2需要 4天等。 ? 和 AOV網(wǎng)不同，對(duì) AOE網(wǎng)有待研究的問題是： ? (1)完成整項(xiàng)工程至少需要多少時(shí)間 ? ? (2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵 ? ? 由于在 AOE網(wǎng)中有些活動(dòng)可以并行地進(jìn)行，所以完成工程的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度 (這里所說的路徑長(zhǎng)度是指路徑上各活動(dòng)持續(xù)時(shí)間之和，不是路徑上弧的數(shù)目 )。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑 (Critical Path)。假設(shè)開始點(diǎn)是 v1，從 v1到 vi的最長(zhǎng)路徑長(zhǎng)度叫做事件 vi的最早發(fā)生時(shí)間。這個(gè)時(shí)間決定了所有以 vi為尾的弧所表示的活動(dòng)的最早開始時(shí)間。我們用 e(i)表示活動(dòng) ai的最早開始時(shí)間。還可以定義一個(gè)活動(dòng)的最遲開始時(shí)間 l(i)，這是在不推遲整個(gè)工程完成的前提下，活動(dòng)ai最遲必須開始進(jìn)行的時(shí)間。兩者之差 l(i)e(i)意味著完成活動(dòng) ai的時(shí)間余量。我們把 l(i)=e(i)的活動(dòng)叫做關(guān)鍵活動(dòng)。顯然，關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)，因此提前完成非關(guān)鍵活動(dòng)并不能加快工程的進(jìn)度。因此，分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的工效，縮短整個(gè)工期。 ? 由上分析可知，辨別關(guān)鍵活動(dòng)就是要找 e(i)=l(i)的活動(dòng)。為了求得 AOE網(wǎng)中活動(dòng)的 e(i)和 l(i)， 首先求事件的最早發(fā)生時(shí)間 ve(j)和最遲發(fā)生時(shí)間 vl(j)。如果活動(dòng) ai由弧 j,k表示，其持續(xù)時(shí)間記為 dut(j,k),則有如下關(guān)系： ? e(i ) = ve(j) (71) ? l (i) = vl(k)dut(j,k) ? 求 ve(j)和 vl(j)需分兩步進(jìn)行： ? （ 1）從 ve(0)開始向前遞推 ? ve(j) = Max{ve(i)+dut(i,j)} ? i ? i,j ∈ T, j=1,2,3,…,n 1 （ 72） ? 其中， T是所有以第 j個(gè)頂點(diǎn)為尾的弧的結(jié)合。 ? （ 2）從 vl(n1)=ve(n1)起向后遞推 ? vl(i) = Min{ vl (j) – dut(i,j) } ? j ? i,j ∈ S , i=n2,…,0 （ 73） ? 其中， S是所有以第 i個(gè)頂點(diǎn)為頭的弧的集合。 ? 這兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。也就是說 ve(j1)必須在 vj的所有前驅(qū)的最早發(fā)生時(shí)間求得之后才能確定，而 vl(j1)則必須在 vj的所有后繼的最遲發(fā)生時(shí)間求得之后才能確定。因此，可以在拓?fù)渑判虻幕A(chǔ)上計(jì)算 ve(j1)和 vl(j1)。 ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1