有向無(wú)環(huán)圖及其應(yīng)用-資料下載頁(yè)
2024-10-19 20:28本頁(yè)面
【正文】 拓?fù)溆行蚣?逆拓?fù)溆行?的前提下進(jìn)行。 ? 設(shè) 活動(dòng) ak (k=1,2,…, e)在帶權(quán)有向邊 Vi , Vj 上 , 其持續(xù)時(shí)間用 dur (Vi , Vj ) 表示 , 則有 e[k] = ve[i]； l[k] = vl[j] dur(Vi , Vj )； k = 1, 2, …, e。這樣就得到計(jì)算關(guān)鍵路徑的算法。 ? 為了簡(jiǎn)化算法 , 假定在求關(guān)鍵路徑之前已經(jīng)對(duì)各頂點(diǎn)實(shí)現(xiàn)了拓?fù)渑判?, 并按拓?fù)溆行虻捻樞驅(qū)Ω黜旤c(diǎn)重新進(jìn)行了編號(hào)。 ? 對(duì)算法 ： （算法 ve） ① 設(shè)初值 ve(i)=0 (0≤ i≤ n1) ② 計(jì)算 Vj的直接后繼 Vk的 ve(k)： 若 ve(j)+dut(j,k) ve(k) 則 ve(k)=ve(j)+ dut(j,k) ③ 為求 vl，設(shè)一棧記錄拓?fù)溆行蛐蛄?，之后彈棧求逆拓?fù)溆行蛐蛄? ? 算法 （先求各事件的 vl，再求各活動(dòng)的 e和 l（ 中用 ee和 el表示），當(dāng)某個(gè)活動(dòng)的 e=l，則該活動(dòng)是關(guān)鍵活動(dòng)） 1 3 2 4 a1=8 a2=12 5 6 7 8 a10=12 a9=6 a8=18 a5=28 a6=8 a7=6 a3=14 a4=10 Ve Vl 1 2 3 4 5 6 7 8 0 8 12 22 28 40 46 58 0 8 12 22 28 40 46 58 e l 0 0 8 12 12 22 22 28 40 46 0 0 8 12 12 32 22 28 40 46 1 2 3 4 5 6 7 8 9 10 三條關(guān)鍵路徑： 124578 134578 13678 注意 ?所有頂點(diǎn)按拓?fù)溆行虻拇涡蚓幪?hào) ?僅計(jì)算 ve[i] 和 vl[i] 是不夠的，還須計(jì)算 e[k] 和 l[k]。 ?不是任一關(guān)鍵活動(dòng)加速一定能使整個(gè)工程提前。 ?想使整個(gè)工程提前，要考慮各條關(guān)鍵路徑上所有關(guān)鍵活動(dòng)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1