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