【正文】 E K H C F G D J 第 81頁 ? 分別用普里姆算法和克魯斯卡爾算法畫出下圖中的網(wǎng)的最小生成樹生成過程。 V2 V0 V3 V5 V4 V1 3 1 5 8 7 4 6 9 5 2 第 82頁 ? 在工程實踐中，一個工程項目往往由若干個子項目組成，這些子項目間往往有多種關(guān)系： ? ①先后關(guān)系，即必須在一子項目完成后，才能開始實施另一個子項目； ? ②子項目之間無次序要求，即兩個子項目可以同時進行，互不影響。 ? 在工廠中，一件設(shè)備的生產(chǎn)包括許多工序，各工序之間也存在這兩種關(guān)系。 ? 學(xué)校里某個專業(yè)的課程學(xué)習，有些課程是基礎(chǔ)課，它們可以獨立于其它課程，即無前導(dǎo)課程；有些課程必須在一些課程學(xué)完后才能開始學(xué)。 2022/2/13 第七章 圖 82 第 83頁 ? 這些類似的問題都可以用有向圖來表示，我們把這些子項目、工序、課程看成一個個頂點稱之為活動 (Activity)。 ? 如果從頂點 Vi到 Vj之間存在有向邊 Vi， Vj,則表示活動 i必須先于活動 j進行。這種圖稱做頂點表示活動的網(wǎng)絡(luò) (Activity On Vertex work,簡稱 AOV網(wǎng)絡(luò) )。 ? 例如某校計算機專業(yè)的課程及其相互之間的關(guān)系，它對應(yīng)的 AOV網(wǎng)絡(luò)如下頁圖所示。 2022/2/13 第七章 圖 83 第 84頁 2022/2/13 第七章 圖 84 C2 C3 C4 C5 C6 C7 C8 C1 課程代號 普通物理 計算機原理 程序設(shè)計 離散數(shù)學(xué) 數(shù)據(jù)結(jié)構(gòu) 編譯技術(shù) 操作系統(tǒng) 高等數(shù)學(xué) 課程代號 C1 C2 C1, C4 C4, C5 C4, C6 C3, C6 先行課程 第 85頁 2022/2/13 第七章 圖 85 C1 C2 C3 C4 C5 C 6 C7 C8 第 86頁 ? 在 AOV網(wǎng)絡(luò)中，如果頂點 Vi的活動必須在頂點 Vj的活動以前進行，則稱 Vi為 Vj的前趨頂點，而稱Vj為 Vi的后繼頂點。這種前趨后繼關(guān)系有傳遞性。 ? AOV網(wǎng)絡(luò)中一定不能有有向環(huán)路。例如在下頁圖那樣的有向環(huán)路中， V2是 V3的前趨頂點， V1是 V2的前趨頂點， V3又是 V1的前趨頂點，環(huán)路表示頂點之間的先后關(guān)系進入了死循環(huán)。 ? 因此，對給定的 AOV網(wǎng)絡(luò)首先要判定網(wǎng)絡(luò)中是否存在環(huán)路，只有有向無環(huán)路網(wǎng)絡(luò)在應(yīng)用中才有實際意義。 ? 一個無環(huán)的有向圖稱為 有向無環(huán)圖 ，它是一類較有向樹更一般的特殊有向樹。 2022/2/13 第七章 圖 86 第 87頁 2022/2/13 第七章 圖 87 ③ ① ② 第 88頁 ? 所謂 “ 拓撲排序 ” 就是將 AOV網(wǎng)絡(luò)中的各個頂點(各個活動 )排列成一個線性有序序列，使得所有要求的前趨、后繼關(guān)系都能得到滿足。 ? 由于 AOV網(wǎng)絡(luò)中有些頂點之間沒有次序要求，它們在拓撲有序序列中的位置可以任意顛倒，所以拓撲排序的結(jié)果一般并不是唯一的。 ? 通過拓撲排序還可以判斷出此 AOV網(wǎng)絡(luò)是否包含有有向環(huán)路，若有向圖 G所有頂點都在拓撲排序序列中，則 AOV網(wǎng)絡(luò)必定不包含有有向環(huán)路。 2022/2/13 第七章 圖 88 第 89頁 ? (1) 在網(wǎng)絡(luò)中選擇一個沒有前趨 (入度為 0)的頂點，并把它輸出； ? (2) 從網(wǎng)絡(luò)中刪去該頂點和從該頂點發(fā)出的所有有向邊； ? (3) 重復(fù)執(zhí)行上述兩步，直到網(wǎng)中所有的頂點都被輸出 (此時，原 AOV網(wǎng)絡(luò)中的所有頂點和邊就都被刪除掉了 )。 ? 如果進行到某一步，無法找到無前趨的頂點，則說明此 AOV網(wǎng)絡(luò)中存在有向環(huán)路，遇到這種情況，拓撲排序就無法進行了。 2022/2/13 第七章 圖 89 第 90頁 ? AOV網(wǎng)絡(luò) 2022/2/13 第七章 圖 90 ⑤ ④ ③ ① ② ?輸出 V3后 ⑤ ④ ① ② 第 91頁 ? 輸出 V4后 2022/2/13 第七章 圖 91 ?輸出 V2后 ⑤ ① ② ⑤ ① ⑤ ?輸出 V1后 ?輸出 V5后 輸出拓撲序列為： 3 4 2 1 5 第 92頁 ? 關(guān)鍵路徑法是采用邊表示活動 (Activity On Edge)的網(wǎng)絡(luò)，簡稱為 AOE網(wǎng)絡(luò)。 ? AOE網(wǎng)絡(luò)是一個帶權(quán)的有向無環(huán)路圖，其中，每個頂點代表一個事件 (Event)，事件說明某些活動或某一項活動的完成，即階段性的結(jié)果。 ? 離開某頂點的各條邊所代表的活動，只有在該頂點對應(yīng)的事件出現(xiàn)后才能開始。 ? 權(quán)值表示活動持續(xù)的時間。 2022/2/13 第七章 圖 92 第 93頁 2022/2/13 第七章 圖 93 a1=6 ② ⑤ ① ③ ④ ⑥ ⑧ ⑨ ⑦ a2=4 a4=1 a3=5 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 第 94頁 通常利用 AOE網(wǎng)絡(luò)可以研究以下兩個問題： ? (1) 完成整個工程至少需要多少時間？ ? (2) 哪些活動是影響工程進度的關(guān)鍵？ 2022/2/13 第七章 圖 94 第 95頁 ? 完成工程所需的時間就是從開始點起進行到結(jié)束點止所需的時間。 ? 路徑長度是指沿路徑各邊的權(quán)值之和，也就是這些邊所代表的活動所需時間之和。 ? 完成整個工程所需的時間取決于從開始點到結(jié)束點的最長路徑長度，此長度最大的路徑叫做 關(guān)鍵路徑 。 ? 分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動，以便爭取提高關(guān)鍵活動的效率，縮短整個工期。 2022/2/13 第七章 圖 95 第 96頁 ? 在描述關(guān)鍵路徑的算法時，設(shè)活動 ai由弧 j,k表示，要確定如下幾個相關(guān)的量： ? (1) 事件 Vj的 最早出現(xiàn)時間 和活動的 最早開始時間 ：從源點 V1到某頂點 Vj的最長路徑長度叫作事件 j的最早出現(xiàn)時間，表示成 ve[j]。頂點 Vj的最早出現(xiàn)時間 ve[j]決定了從 Vj指出的各條邊所代表活動的最早開始時間，因為事件 j不出現(xiàn)，它后面的各項活動就不能開始。我們以 e[i]表示活動 ai的最早開始時間。顯然 e[i]= ve[j] 。 2022/2/13 第七章 圖 96 第 97頁 ? (2) 活動 ai的 最遲開始時間 ：在不影響整個工程按時完成的前提下，此項活動最遲的必須開始時間，表示成 L[i]。 ?只要某活動 ai有 L[i]=e[i]的關(guān)系，我們就稱 ai為 關(guān)鍵活動 。關(guān)鍵活動只允許在一個確定的時間開始，再早，它前面的事件還沒出現(xiàn)，尚不能開始；再晚，又會延誤整個工程的按時完成。由于完成整個工程所需的時間是由關(guān)鍵路徑上各邊權(quán)值之和所決定的，顯然關(guān)鍵路徑上各條邊所對應(yīng)的活動都是關(guān)鍵活動。 2022/2/13 第七章 圖 97 第 98頁 ? (3) 事件 j的 最遲出現(xiàn)時間 ：即事件 j在不延誤整個工程的前提下允許發(fā)生的最遲時間，表示為 vl[j]。對某條指向頂點 Vk的邊所代表的活動 ai可得到： L[i]= vl[k](活動 ai所需時間 ) 也就是活動 ai必須先于它后面事件的最遲出現(xiàn)時間開始，提前的時間為進行此活動所需的時間。 ? 下圖所示為活動開始時間與事件出現(xiàn)時間的關(guān)系。 2022/2/13 第七章 圖 98 Vj ai Vk 第 99頁 ?確定關(guān)鍵路徑的方法就是要確定 e[i]=L[i]的關(guān)鍵活動。 ?假設(shè)以 w[j,k]表示有向邊 j,k的權(quán)，即此邊對應(yīng)的活動所需的時間，為了求 AOE網(wǎng)絡(luò)中活動 ai的最早開始時間 e[i]和活動 ai的最遲開始時間 L[i]，先要求得頂點 Vk的最早出現(xiàn)時間 ve[k]和最遲出現(xiàn)時間vl[k] 。 2022/2/13 第七章 圖 99 第 100頁 ? ve[k]和 vl[k]可以采用下面的遞推公式計算： ? (1) 向匯點遞推 由源點的 ve[1]=0開始，利用公式： 向匯點的方向遞推，可逐個求出各頂點的 ve 。式中 p表示所有指向頂點的邊的集合。 2022/2/13 第七章 圖 100 )1(]),[][(][ m a x,nkkjwjvekvepkj???????第 101頁 ? 此式的意義為：從指向頂點 Vk的各邊的活動中取最晚完成的一個活動的完成時間作為 Vk的最早出現(xiàn)時間 ve[k]。 2022/2/13 第七章 圖 101 Vj Vk ???????p第 102頁 ? (2) 向源點遞推 由上一步的遞推，最后總可求出匯點的最早出現(xiàn)時間 ve[n]。因匯點就是結(jié)束點，最遲出現(xiàn)時間與最早出現(xiàn)時間相同，即 vl[n]=ve[n]。從匯點的最遲出現(xiàn)時間 vl[n]開始，利用下面公式： 向源點的方向往回遞推，可逐個求出各頂點的最遲出現(xiàn)時間 vl。式中 s表示所有由 Vj點指出的邊的集合，如下頁圖所示。 2022/2/13 第七章 圖 102 )1(]),[][(][ m i n,njkjwkvljvlskj???????第 103頁 ? 上述公式的意義為：由從 Vj頂點指出的各邊所代表的活動中取需最早開始的一個開始時間作為 Vj的最遲出現(xiàn)時間。 2022/2/13 第七章 圖 103 Vj V k s???????第 104頁 ? 無論是向匯點遞推還是向源點遞推，都必須按一定的頂點順序進行。 ? 對所有的有向邊，向匯點遞推是先求出尾頂點的 ve值，再求頭頂點的 ve值；向源點遞推則相反，先求頭頂點的 vl值，再求尾頂點的 vl值。 ? 為此，可利用上節(jié)介紹的拓撲排序得到的頂點次序進行向匯點的遞推，向源點的遞推按相反的順序進行即可，不必再重新排序。 2022/2/13 第七章 圖 104 第 105頁 2022/2/13 第七章 圖 105 事件 j ev[j ] Lv[j ] 活動 i e[ i ] L[ i ] L [i ] e[ i ] 1 0 0 1 0 0 0 2 6 6 2 0 2 2 3 4 6 3 0 3 3 4 5 8 4 6 6 0 5 7 7 5 4 6 2 6 7 10 6 5 8 3 7 16 16 7 7 7 0 11 14 14 0 10 16 16 0 9 18 18 9 7 10 3 8 14 14 8 7 7 0 第 106頁 ? 由表可知時間余量為零的活動都是關(guān)鍵活動，即為 a1， a4， a7， a8， a10， a11。 ? 這些關(guān)鍵活動構(gòu)成兩條關(guān)鍵路徑，即關(guān)鍵路徑(V1， V2， V5， V7， V9)和 (V1， V2， V5， V8， V9)。 ? 在安排工程時，對于關(guān)鍵活動和余量小的活動應(yīng)重點保證，余量較大的活動可適當?shù)胤潘尚?，對非關(guān)鍵活動加速進行，并不能使整個工程提前完成，只有提高關(guān)鍵路徑上的活動的效率，才能縮短整個工程的工期。 2022/2/13 第七章 圖 106 第 107頁 ?所謂 最短路徑 （ shortest path）問題指的是：如果從圖中某頂點出發(fā)（此點稱為源點），經(jīng)圖的邊到達另一頂點（稱為終點）的路徑不止一條，如何找到一條路徑使沿此路徑上各邊的權(quán)值之和為最小。 ?設(shè)一有向網(wǎng)絡(luò) G =（ V,E），已知各邊的權(quán)值，并設(shè)每邊的權(quán)均大于零，以某指定 V0為源點，求從V0到圖的其余各點的最短路徑。 ?以下頁圖為例，若指定以頂點 V6為源點 V0，該圖比較簡單，通過觀察可得到從 V6到其余各點的最短路徑。 2022/2/13 第七章 圖 107 第 108頁 2022/2/13 第七章 圖 108 18 ⑥ ⑤ ④ ① ② ③ 5 10 24 25 8