Lec21 資料結構 第十五週課程

NYCU OCW
75粉絲
2023年12月3日
Graph (4/4)
授課教師:資訊工程學系 彭文志老師
課程資訊:http://ocw.nctu.edu.tw/course_detail.php?bgid=9&gid=0&nid=412
授權條款:Creative Commons BY-NC-SA
更多課程歡迎瀏覽交大開放式課程網站:http://ocw.nctu.edu.tw/ 本課程同時收錄至國立交通大學機構典藏,詳情請見:
http://ir.nctu.edu.tw/handle/11536/108205
各位同學我們開始上課
禮拜五的時候就是我們有最後的時候
講到那個叫 activities on vertex
這個東西就是顧名思義
就是說 activity 就是那個行為
或是他的
就是他發生的地點
就是可以在 graph 上用 vertex 來代表
那這個 AOV 這叫 AOV
這 AOV 的 network
那他其實他的那個箭頭 edge 的箭頭
代表的是他的順序
就是 AOV 代表他的順序
那通常的話就是
他這個 AOV 的 network
可能是從左邊到右邊
從左邊到右邊
對 那就代表說
我現在有很多的 activity
他們的前後順序的關係是什麼
那在 AOV 上面
你可以根據他的順序的關係
推導出一個叫做 topology order
那 topology order 是什麼
這上面有很多的文字
可以不用管他
為什麼你知道說
假設我在 AOV 裡面抓兩個點出來
那他們的前後順序關係
會在 topology order output sequence 上
去 maintain 住
所以 topology order 他出來的是什麼
他出來是一個 sequence
你看上面是一個 linear order 的 sequence
那在 graph 上認兩點
在 graph 上認兩點的前後的關係
在那 topology order 的 sequence 上
他都會 maintain 住
都會 maintain 住
就是保留著
那最常聞用到 AOV network 的例子
最盛行的例子是什麼呢
就是這種大學的修課系統
那在這地方的話
就是大家看一下
總共有 15 門課
然後他的先修課程
如果你沒有修過這些課程的話
你不能夠修某些課程
比方說 C10 programming language
那你要修 PL 的話
先修課程的話是 C7
C7 的話你必須要學習演算法
那演算法你就可以看一下
他的先修課程 C3 和 C6
你可以對應到 C3 是 data structure
C6 的話是 linear algebra
所以這是一個課程的 table
那他的先修的課程
是代表說他的條件
那根據這樣子一個 table
你可以畫出一個 graph 出來
這是一個 graph
那這個 graph 的話
同樣的他是 AOV
那為什麼他 AOV 呢
他的頂點代表的是課程
你就可以把他想像說
你修一個課程就相當於
在做一個修課
修那一門課的 activity
那箭頭呢
其實他上面都沒有什麼 age
他沒有什麼 weight
但他箭頭代表就是順序的方向
那這就是出來一個 AOV 的圖
那在這邊的話
他跟同學講說
如果我給你一個 AOV 的 network
那你的 output 呢
Topology order 的 output
就是一個 sequence
那像這個地方
sequence 的話就是 0 3 2 5 1 4
他就是一個 sequence
0 3 2 5 1 4 他就是一個 sequence
那大家看一下
在這個 sequence 裡面
我隨便抓兩個數字
比方說 0 3 2 5 1 4
我隨便一個抓 3 一個抓 5
3 一定會在 AOV graph 裡面
3 一定會在 5 之前
那你看一下
在這 AOV graph 裡面
最原始那個 A 的 graph 裡面
3 一定會在 5 之前
那今天 3 和 4 咧
你看在那個 sequence 裡面
任意抓兩個數字
他們前後順序的關係
在 AOV graph 裡面
他是 maintain 住的
3 和 4 也是一樣
你看 3 就在 4 之前
那接下來就是同學要問的是說
假設我給你一個 AOV 的 network
那我要怎麼產生 topology order
怎麼產生 topology order
那產生的方式呢
其實是很簡單的
我上禮拜三分鐘就講完了
你看一下
就是在這個 graph 裡面
你首先看一下示意圖
在這個 graph 裡面
首先看一下
假設 in degree
in degree 是 0
in degree 就是沒有人指到他的話
那你就可以 output 出來
就是在這個 graph 裡面
AOV graph 裡面
假設那個 vertex 的 in degree
是 0 的話
你就可以把這個 node output 出來
那當這個 node
就是第一個步驟
那第二個步驟是什麼
當這個 node output 出來以後呢
把這個 node 所指的那些點
vertex
他們的 in degree
這些 vertex 他們的 in degree
做 update
然後呢
接下來做什麼事
第三步驟是幹嘛
重複 loop
第一步驟和第二步驟
所以這個 AOV 變 topology order
演算法很簡單
所以在這個地方
如果依照剛剛我們所講的準則
A 這個部分
是原來的那個 graph
in degree 是 0
in degree 是 0 的
就是 node 0
所以接下來呢
就把 node 0
把它 output 出來
所以你看到
在上面那個 topology order sequence 裡面
第一個數字就是 0
那 node 0 被 output 出來以後呢
node 0 所指到的那些 node
要把他們的 in degree
去做 update
反正 1 2 3
他的 in degree 是 1 的
現在 1 2 3
因為 0 被移出來了
所以 1 2 3
in degree 就是 0 了
要去做 update
這第二步驟
那 update 完成以後呢
接下來要做的是什麼
就回音到第一步驟去
對
其實就回音到第一個步驟去
那第一個步驟是什麼呢
因為現在 in degree 是 0 的
有三個點
1 2 3
三個點
對
那這三個點呢
你認取一個點出來
把他 output 出來
認取任何一個點出來
把他 output 出來這樣
所以在這地方
你可以取 3
在這裡面是取 3
所以 3 就被 output 出來了
那 3 被 output 出來以後呢
第二步驟
3 所指到的那一些點
就是 4 號和 5 號的點
他的 in degree 要改變
要改變
那就變成了 C 這樣子的結果
那接下來在 C 這個 subgraph 裡面
就在這個 graph 裡面
你看 in degree 是 0 的是誰
1 和 2 這樣
那隨便你要取哪一個出來
那在這個例子裡面呢
就是他取 2 出來
就把 2 output 出來這樣
那同樣的
2 被 output 出來以後呢
這個就要把 4 和 5 的 in degree 改變
那以此類推
所以 Tarpagio 的其實很簡單
就是你會有一個 graph
那在這個 graph 裡面
第一個步驟
看 in degree 是 0 的
output 出來
第二個 update 他的 in degree
然後 loop
就一個 loop 這樣
1 到 2 這樣
直到什麼時候結束
直到把所有的 node
output 出來為止這樣
就結束了
這裡有個問題
那要達到這樣子的話呢
要達到這樣子的話呢
就是在原來的 adjacent list 裡面
可以多一個欄位這樣
那這個欄位是什麼呢
就是有一個叫 count 的這樣
那 count 是什麼
就計算說他的 in degree
所以 count 就是計算他的 in degree 這樣
那所以在這個地方的話呢
就是剛才那個
那個 AOV 的 graph
是他的 adjacent list 可以表示成這樣
所以
就是如果是這樣表示方法的話呢
你就要去 scan
scan 那個 count 的欄位
看他是 0 的
就可以把他 output 出來
所以以這個例子來看的話
你看就是 count 的欄位
第一個是什麼
第一個是 vertex 0 這樣
因為他 count 0
所以把他 output 出來
那接下來呢
循著 vertex 0 所連過去的
那個 adjacent list 123
那他接下來做什麼事
接下來就要去做
123 他所對應到的 count 的值這樣
減 1
就像 in degree 要減 1 這樣
那所以呢
就是 123 減 1
你會發現 123
vertex 1 vertex 2 vertex 3
他們的 count 就是 0 0 0 的這樣
然後接下來就
就重複我剛才所說的這個步驟這樣
就結束了
那所以這是一個 implement 的方式
是 implement 方式
來做到 topology order 這樣
那
對 很明顯的
就是 topology order
他不是唯一的
這要注意
topology order
這個 order 他不是唯一的這樣
那很明顯 為什麼
123
在這例子裡面
我們 output 3 先出來
其實在
這個就是
第 b 的這個 graph
123 這樣
我們把 3 先 output 出來
事實上我們也可以把 1
或者是把 2 output 出來
為什麼 因為
對
比方說我這個 topology order
叫 0 1 2 3
0 1 2 3
可不可以
前面四個 sequence
0 1 2 3
還是可以的
對 為什麼呢
因為他還是符合那個
前後順序他 guarantee 這樣
對 所以
給你一個 AOV
他的 topology order
只要他符合那個特質
就是前後順序關係
maintain 住就可以了這樣
所以
他的那個
就是
sequence 並不是唯一的這樣
對 這有沒有問題啊
好 那這是一種
implement 方式這樣
就是 count 的定義這樣
那如果不要用這種
implement 方式可不可以
可不可以
不要用這個 implement 方式這樣
其實之前我們有講過一個叫做
inverse adjacent list
inverse adjacent list 是什麼
一個 graph
他可能會有一個叫做
adjacent list 這樣
那 inverse adjacent list
是要去 maintain
maintain 他的 in-degree 這樣
in-degree 跟誰接這樣
所以其實你也可以用
inverse adjacent list
和 adjacent list 搭配
來達到
只不過我們這邊是
用最笨的方法這樣
可以直接做到最笨的方法
就加了一個欄位
那個欄位就是 count 這樣
都結束了這樣
好 這有沒有問題啊
所以 topology order
就到這邊了
那接下來我們再看
另外 AOV 講過了這樣
那一個叫做
另外一個叫做 activity on edge 這樣
他叫 AOE 這樣
其實 AOE 的縮寫是
activity on edge 這樣
那 activity on edge 的話呢
就跟 AOV 是不一樣的
就是他的 activity 發生在哪裡
發生在 edge 上
頂點
這樣用來幹嘛
頂點只是告訴你說
這個 activity 什麼時候發生
什麼時候結束這樣
所以大家看一下
這是一個 AOE 的 network 這樣
這是一個 AOE 的 network
你可以想像
一開始 vertex 0 代表什麼呢
vertex 0 就代表說
這是一個開始
這整個是一個計劃
那計劃搞不好
我們就可以把它想說
那我們來做一個 project
做一個 web 搜索引擎這樣
那要去做 web 搜索引擎呢
有幾個步驟
那包含了
其實在這個例子
假設有 11 個步驟
11 個步驟
那第一個步驟呢
就第一個 activity A1
就是從 0 到 1
這大家看一下
對 從 0 到 1 這樣
那他所需要花的時間
要開發這個 activity A1
所需要花的時間是 6
6 個時間單位這樣
那 A2 所需要花的時間是
4 個時間單位這樣
然後 0 到 3
就代表說 A3 這個 activity
所需要花的時間是 5 個單位這樣
那所以呢
做完了 1 2 5 以後呢
假設一個 project 開始了這樣
他可以同時進行這樣
因為一個 project 都是
可能是一個 team
一個 team work 這樣
所以每一個人呢
他可能負責某一個項目
可以想說有人負責 A1
有人負責 A2
有人負責 A3 這樣
那做完了以後呢
接下來進入到下一個 phase 這樣
就是 A4 A5 和 A6 這樣
就是一直在推
那 4 那個地方呢
是什麼呢
4 那個地方
對 4 大家看一下
4 那個地方是什麼
就是說 A4 和 A5 做完以後
A4 和 A5 做完以後
對 纔能夠啟動
啟動 A7 和 A8 的
就是這個 activity 這樣
所以你看
對 這地方
A4 A5 做完以後
到達這個點這樣
那這個點完以後呢
纔能夠啟動 A7 和 A8
這個 activity 這樣
那直到做完
就是 8 的話
他就是 finish 這樣
對
那這是一個 AOE 這樣
那這 AOE 呢
在哪個地方最
最常被使用
對
就是現在
對
就是一些大公司
比方說
我們就舉
對 趨勢
其實趨勢呢
他在開發一個軟體這樣
假設他開發一個軟體這樣
就是會用這樣子來控管
控管每一個人的
就是計畫要做什麼
然後時間
時限是多少這樣
所以假設你有一個人 delay 的話
那這個
他那個趨勢在開發一個叫
cloud 的這個防毒軟體這樣
他就沒辦法如期完工
所以
這個 AOE 呢
就是最常被用到的是
program
是一個 project
那要讓他能夠如期進行
所以就會有這個
AOE 的 graph 這樣
然後掌控每個人的流程這樣
掌控每個人的流程這樣
然後他可以隨時去做一些
預估
這是
是否完成這樣
對
這沒問題
對 我剛剛講的趨勢是一個
然後另外一個
像 Yahoo 也是這樣
Google 就更不用講了
這種軟體公司進去
對 你要用到的是什麼
就是要使用到那些
就是開發一個
開發一個 service
或 internet 的 service 這樣
不是你一個人完成的
是很多人
teamwork 組成的
然後呢 把
你只是其中一個小螺絲釘
可是那個小螺絲釘也很重要
對 就是不要
就是因為你這樣
然後就
就讓整個 project delay
那這是一個是
很典型的
反正你碰到那種大軟體
一起要開發的
都一定會走這種流程這樣
那就是掌控
你的 project 是如期運行的這樣
那所以在這個
在這 AOE 的 graph 裡面
他的表示方法會怎麼樣
他表示方法可能就會像這樣
那這個也是一個 adjacent list
這是 adjacent list
這 adjacent list 呢
同樣的
他的每一個 node 這樣
那他前面會有一個 count 的欄位
那 count 的欄位是記載什麼
記載說
這是他的 in degree
是誰指導他
有多少人指導他
那接下來你看他的 list
比方說 vertex 0 這樣
那 vertex 0 呢
他連出去有 1 2 3
三個 node 這樣
那這個 node 上面呢
每個 node 的那個欄位
就是那個 list element
list node 的欄位
又多增加一個欄位這樣
本來是隻要知道說他連到誰就好了
但在這地方的話
有增加一個欄位
這個欄位就叫做 duration
duration
那 duration 的意思是什麼呢
就是說這個 vertex 從 0 連到 1
從 0 連到 1
這個 edge
他是一個 activity
這個 activity 他所需要花的時間單位
那在 duration 像這個是 6
6 個時間單位這樣
所以你看
他就是代表是 0 到 1
0 到 1 2 3 三個 node 這樣
那其中跟 0 連到 1 那個 node 這樣
duration 是 6 這樣
就是持續
所需要花的時間是 6 個單位這樣
0 到 2 的話
大家看一下 0 到 2
其實在
對 在中間這個地方這樣
那他 duration 是 4
然後 0 到 3
對 duration 是 5 這樣
所以這個 linked list 呢
除了要記載了那個頂點的資訊以外
還要把 duration 的資訊放上來這樣
duration 的資訊放上來
所以這是一個 adjacent list
那根據這個 adjacent list
我們等一下會做什麼事
根據這個 adjacent list
那我們來想想看
就是說每個 activity
我們去計算他的
最早完成時間這樣
那這個叫做 1 1
這是 earliest
這是
我們來看一下
這是他的縮寫
我們會去計算他最早
可以被完成的時間
要簡寫成 1 1 這樣
對 那什麼叫做最早完成時間
就是說這個 activity
他可以多快 多早被完成
多快被完成這樣
好 那
對 那大家看一下這個
這個示意圖這樣
那我們要怎麼樣去計算
最早被完成的時間呢
比方說那個 a 1
那他最早什麼時候可以被完成
假設我們時間的
從 0 開始這樣
從 0 個時間單位開始這樣
那接下來我們要執行這個 project
執行這個 project
那接下來呢
我們就要去計算
就是每一個 activity
他最快
就是最快
多快可以把這個 activity
這個完成
假設他沒有任何的 delay 的話
那先不要看這下面了
那你看上面這樣
a 1
a 1 他最早完成時間是多少
從 0 開始嘛
那假設這個 activity
需要花的時間是 6 的話
要完成這個 a 1
這個 activity
完成這個 a 1
需要時間 6
所以 a 1 如果被完成的時候呢
完成的時候
他的時間維度
已經到達什麼了
6
對 就是 a 1
他需要 6
就是 a 1 需要
假設
用天好了
那個時間單位用天好了
就 a 1 需要 6 天的時間來完成這樣
那所以完成 a 1
如果沒有 delay 的話
要完成 a 1
那他的時間是 6
那 a 2 的話是 4 這樣
a 2 的話是 4 這樣
那如果你要完成 a 2 這樣
最早
什麼時候可以完成
假設沒有 delay 的話
就是 0 加 4
就是 4 這樣
那所以呢
接下來我們要跟同學講說
那個最早完成時間
要怎麼去做計算呢
實際上你就要去看他說
這個 edge
他所連到的那個頂點
那個頂點呢
頂點就是比方說
a 1 等於 6 嘛
他指的是 0 到 1
0 到 1
這個 edge 這樣
那我們要去計算的是說
在 1 這個地方
會有他的完成時間
他代表是 a 1 被完成
那 0 走到 1
你可以想說
0 走到 1 要花多少時間呢
要花 6 個時間單位
所以 1 的話就是 6 這樣
那一直雷推
那接下來呢
大家想想看就是說
那如果我要去做這樣子
一個計算的話
要怎麼做
那這個地方
就會利用到
所謂的 topology order 這樣
會用到 topology order
來去完成他
那怎麼說呢
那在這個 AOE 的 graph 裡面
那首先我們來看一下
這個 vertex
每一個 vertex
他 integrate
一開始的時候
integrate 是 0 的
是誰
就是隻有那個點
就是 0 起點
所以這個 0 這個點呢
就會被 push 到 stack 裡面
被 push 到 stack 裡面
就把他放到 stack 裡面
那既然 0 被放到 stack 裡面呢
那我們就
stack 就只有一個元素
就是 0 這樣
那他的 integrate 是 0
所以接下來呢
我們就要把 stack
這個 element
把他 pop out 出來
那丟出來以後呢
0 被丟出來以後呢
他要做的事情是什麼
他要做的事情就是
根據 vertex 0
現在開始的時間 0
現在開始的時間是 0 這樣
然後呢
對每一個 vertex
對他所指到的每一個 vertex
去計算
到達那些 vertex
所需要花的時間這樣
所以你看那紅色字那地方
就是把 0 output 出來以後呢
接下來要去做的時間
就是 0 加 6
他花 6 個時間單位
可以到 vertex 1 這樣
那 0 加 4
a2 等於 4 嘛
0 加 4
可以花 4 個時間單位
到達 vertex 2
然後 0 加 5
可以花 5 個時間單位
到達 3
那做完這件事情以後呢
就是說你看他那個紅色的
就是 output 的 0 以後
所以是 1 2 3
每一個的時間單位
就變成 6 4 5 了這樣
那做完這件事情以後呢
要把
就是 0 被 output 出來了
被 delete 出來了
那 0 所指到的那些 vertex
就是 1 2 3
他的 in-degree
就是那 count 的欄位
他去減 1 這樣
count 欄位減 1
然後接下來呢
根據那個
這個 count 的欄位
看哪一些 node
他的 in-degree 是 0
那如果是 0 的
把那些 node
push 到 stack 裡面
所以在 stack 裡面
就有 3 2 1 這樣
3 2 1 這些數字
那當 stack 裡面有 3 2 1
這些數字以後呢
接下來要做的事情是什麼
從 stack 裡面
pop out 一個 element 出來
就是這些 element 是代表什麼
就是 in-degree 是 0
那在這地方我們 pop out 3 這樣
3 就被 pop out 出來了
那 3 一旦被 pop out 出來以後呢
接下來要做的事情是什麼
就是從 3 他可以指到 5 這樣
那到達 3 的時間是什麼
到達 3 的時間是 5 這樣
所以這個 vertex A6
他需要花的時間是 2
所以 5 加 2
就是你看一下那藍色的這樣
就是到達 5
所需要花的時間就是 7 了這樣
到達
從 0 開始
到達這邊要 5 個單位
那到達這邊
就是 2 個單位
所以到達這個 5 的時間
最早
就是 7 個時間單位
那其他的就依此類推
那當這個
當這個 5 呢
就是 3 值到 5 嘛
那這個 5 被我們計算出來以後
這個 5 的 in-degree 就設成是 0 了
那同樣的
這個 5 呢
就會被 push 到 stack 裡面
那所以呢
就是就 iteration 去做這件事情
那直到什麼時候結束呢
就是 stack 是空了
那這個步驟就停止了
所以這個是計算
計算每一個 activity
他最早的完成時間
最早的完成時間
那事實上呢
他就是去計算每一個
他 edge 所指到的那個 node
最早的到達時間
那這又是另外一個例子
這是另外一本教科書的一個例子
所以剛才這個是比較 detail 的
跟你講說
假設我要 implement 這個方法的話
會怎麼做
會有一個 stack
然後你要用到 topology order
然後每一次 topology order output 出來以後呢
你要對他所指到的那個 node
針對每一個 node
去計算他的到達時間
所以他原則上
他會用到 topology order 的概念
那在這地方再來看一個例子
這例子等一下會告訴你說
我們要從這個 AOE 的 graph 裡面
找出什麼叫一個 critical path
critical path 就是說
critical path 的話
意思就是說
從起點到終點
我要找出一些 node
找出一些 node
他是 secret 什麼 node
然後呢
他這些 node 非常重要
那為什麼他們非常重要
他沒有允許有 delay 的空間
delay 的空間是什麼
就是有時候我在完成這個
比方說我要 A1
我要完成的時間是 6
可是呢
我可能會允許說
你可以提早完成
或延緩一天完成
那 critical path 的話是
你不能夠有任何的 delay
一旦你有任何 delay 的話
這個 project 就會因為你們這些 node
沒有及時完成
所以就毀了
等一下我們要導出 critical path
那要導出 critical path 有兩個步驟
第一個步驟呢
就是計算每個 activity
計算每個 activity 的
最早的完成時間
那每個 activity 最早完成時間怎麼算
就是
當然應該有大概講過了
就是透過 topology order
就是透過 topology order 的概念
那一開始的時候
那個 node 設成 0
那接下來呢
就是會有一個公式
就是在 w 那個 vertex
在 w 那個 vertex
會有一個時間
那這個時間怎麼決定
那時間的決定方法呢
就是等於 max eev 加 dvw
eev 的話呢
是什麼
就是 eev
是 w 被 node v 所指到
w 被 v 所指到
所以最早到達 node v 的時間
再加上
從 v 到 w 的 duration
所需要花的時間
那就是 w 的最早到達時間
所以其實這個公式很簡單
那等一下我們來看例子是怎麼做的
你只要會
一開始的時候時間單位是 0
那所以呢
要到達 vertex 2 的話
所需要花的時間是 3
所以它時間是多少
你要去計算
最早可以完成的時間
0 加 3 嘛
然後呢
接下來看一下
0 到 s 到 3
這個 vertex 3
它所需要花的時間是 2
0 加 2
那接下來
好玩的來了
6'
6' 的話意思是什麼
為什麼要多一個 6'
這是一個示意圖
其實它指的是什麼呢
其實指的是說
從 2 到 3
2 到 3 它們都會指到 6
2 到 3
它們事實上是指到 6 了這樣
那上面呢
是 2 和 3 要一起被完成以後
纔能夠進行
2 和 3 要一起
都要同時被完成
2 要完成
A activity 和 B activity
都要被執行過
完成了
才會去做 activity
D 這個動作這樣
所以你可以看一下
6' 這個目的是幹嘛
是一個 sync
它代表說是一個 sync 的步驟
你要把 activity
D 要給它啟動的話
開始執行的話
你要有把兩個 activity 把它做完
那分別是 A 和 B
這兩個 activity 要做完
那所以呢
大家看一下就是說
這 6' 呢
畫起來的意思就是
它要讓它同
要確認 2 和 3
它們已經被到達了
到達了
纔可以去做這樣
那 2 和 3
一個是 3
一個是 2 這樣
最大值是多少
最大值是 3
那所以呢
就代表說 D
D 這個 activity 它要啟動的話
至少要等三個時間單位以後
三個時間單位以後
那所以呢
在三個時間單位以後呢
D 就假設被啟動了
到達 6 這個時間的話
就是 3 加 2
6 就是 5 了這樣
就是大家看一下
就是 5 這樣
那前面那個
C 到 C3 然後到 4 的話
還好
3 加 3 嘛
就是 6 這樣
那重要的是
這個到達 6
所需要花的時間
你可以這樣想就是說
D 如果要啟動的話
它的前提是
A 和 B 這兩個 activity
都必須要完成
那 A 和 B 要完成的話
對
A 和 B 都要完成
那最保險的時間是什麼
第三天以後
你纔去啟動 D 這樣
纔去啟動 D 這樣
因為 A 要花三天的時間
B 要花兩天的時間這樣
那你當然還是要等到 A 完成嘛
那所以等 A 完成的話
是三天以後這樣
就是 3 加 2 是 5 這樣
那下面的話呢
對 就是 2 加 1 是 3
那所以大家可以看到就是說
你其實就是要去計算
每一個 node
最早
我們會把它叫做
最早的到達時間
arrival time 這樣
那上面的數字就是
arrival time 這樣
對 然後再以此類推
同樣的在這邊也很好玩
就是 Q'
Q' 代表什麼呢
它代表是說
這個 activity
C 和 D 它必須要完成以後
纔能夠執行
activity F 這樣
那所以呢
就是一個要六天
一個要花五天的時間
對 所以最保險是六天以後
你才開始啟動這個 F 這樣
所以 Q' 是在協助你說
對 要去決定 6 和 5
這是誰比較大
這地方是 6 這樣
對 然後再
以此類推這樣
然後再一直往
其實這個計算是
再繼續往前推
推到 後面我們就不講了
推到底的話呢
就是說這整個 project
這整個 project
如果要完成的話
什麼時候可以完成
十天以後
這是十個單位時間
就是假設我們用天
為當作單位的話
十天以後會完成
對 這有沒有問題
有沒有問題
所以那個
這是每一個點
每一個點
它代表的是什麼
代表的是
要完成某一個 activity
就是這個點
你要往前看它的 edge
要完成這個 activity
它最早的完成時間
最早的完成時間
最早完成這個 K
所需要花的時間
在這邊是 7
就指說 K
最早可以在七天內
就被完成了
這是 earliest compute
這是 E1的意思
那等一下我們要講說
既然有最早的完成時間
那我們也可以計算說
這個 activity
可以多慢
最慢 什麼時候要完成
那這個就叫做
latest completion time
就一個 activity
它可以最早什麼時候開始
那我們也可以問說
這個 activity
最晚 什麼時候要完成
當然越早完成越好
可是我們也可以去計算說
這個 activity 最晚
多晚可以被完成
那要計算這個 latest
就是最晚
什麼時候可以被完成的話
它的計算方法
就跟剛才那個方法
有點不大一樣
為什麼不大一樣呢
剛才我們去計算
最早完成時間的話
是從左邊到右邊
那要計算最晚
什麼時候被完成的話
是從右邊到左邊
那右邊到左邊
它的目的是幹嘛
我們都知道
其實在剛才那個例子裡面
我們都知道
這個 project 要完成
是在十天之內
就必須要完成了
所以我就推估
十天是我的底線
是這個 project
要完成的底線
所以十天
不管怎麼樣
你一定要完成這個 project
是我的底線
那我們來回推
回推每個 activity
最晚
可以什麼時候被完成
用回推的機制
所以就是從右邊到左邊
很簡單
也是一樣
它第一個步驟叫做
compute by reverse topology order
要想一下
reverse 的 topology order
是什麼意思
那個演算法
topology order 的演算法
是需要改變
因為它現在是顛倒過來
是電腦這樣計算
以前我們是 count
算什麼
算 count 0 的話
是看 in degree
所以 reverse topology order 的話
可能是
count 是算 out degree
接下來
它會利用到這些公式
那這些公式是什麼
先不要看它
我們來看
是怎麼 run
所以在一開始的時候
從右邊到左邊
一開始的時候
這個 project
什麼時候要完成
在十天之內就要完成
那在十天之內要完成的話
那我們就往左邊走
十減
那這個 h
h 代表什麼意思
就是這個 activity
它需要花一天的時間來完成
所以十減去一
所以我到達這個 10'
這個點
這個點的時間是什麼
是 9
是這個 9 這樣
那接下來呢
就是再往
就是往回走
然後 9 減 0
到達這個 7 的時間是多少
是 9 這樣
其他一直內推
就是 9 這樣
這三個都是 9 這樣
那接下來呢
這個 7
到達這個 7 的時間
到達這個 7 的時間是 9 這樣
然後呢
9 減去 3
回到這個 7'
所需要花的時間是
到達 7'
它的時間是什麼
是 9.7
9.3 是 6 這樣
那同樣的一直內推
那接下來這個來了
這裡會面對一個抉擇點
那這個抉擇點是什麼呢
就是 4 到 7
這是 9
那所以到達 5 的時間
一個是 7 減 0
那一個是 9 減 4
一個是 7 減 0
一個是 9 減 4 這樣
所以你會有兩個選擇
到底是 7 還是 5 這樣
到底是 7 還是 5
那在這個地方的話呢
先看公式
它有一個準則
就是去選 minima 的值
那 minima 的值
那所以呢
就是先知道怎麼算
就是 7 減 0
7 減去 0 是 7
減去 4 是 5 這樣
所以 5 這個地方
它有兩個選擇
一個是 7 和 5
選最小的值
所以是 5 這樣
所以這個要去選 5 這個值
那想想看
選 5
選 7 可不可以
7 是不行的
為什麼
假設你選了 7 了以後
那你看喔
你要完成 K
需要花的時間是 4 天
所以 7 加 4 就 11 天了
到達 9 的時候是 11 天
那 total 來看的話
這個 project 總共
只能夠有 10 天的時間
你已經超過了 10 天
那不行
所以在這個地方的話呢
其實選 minima 值的意思就是說
我最晚要多
對於 K 來看的話
我最晚要在 5 天就必須要執行
最晚要在第 5 天
就必須要去啟動它
因為它要花 4 天的時間纔能夠到達這個點
然後確保這個數字是對的
那也纔能夠確保整個 project 是如期進行
所以就是在這地方
會去選最小的值
那其他的就
大家看一下就一直在推
回推回去這樣
這個我們就跳過去
就回推回去
紅色的代表的是
每一個 activity
那它最晚
要多晚被完成
多晚被
可以拖多久
就是被完成它
那接下來呢
你有藍色數字也有紅色數字
那什麼叫做 critical path
那大家看一下
每一個 vertex 都會對應到一個藍色和紅色數字
那什麼叫做 critical path
critical path 的話呢
就是那個 node 藍色和紅色數字相減
是 0 的
那就叫 critical path
那現在你看一下
在這個 activity 裡面
上面有一個紅色的線
上面有一個紅色的 path
從 x 走到 2
2 走到 4
4 走到 7
7 走到 10
10 到 10
那它是一個 critical path
那在這個 path 上呢
那個 node
那個 node 最早和最晚完成的時間
是不能夠被延誤
因為它的相減是 0
那就是 critical path
所以可以想想看
critical path 是不是一定會存在
critical path 是否一定會存在
那有沒有可能說
因為這個老師在某一個點
就斷掉了
繼續想一想
然後第二個呢
就是會問你說
怎麼去找 critical path
如果給你一個 AOE 的 graph
你已經算出來
你已經算出每個頂點
那個紅色字
藍色那紅色字
那接下來你怎麼去找 critical path
怎麼去找 critical path
所以這個 graph 我們就講到這邊
這已經從頭了
所以到目前
今天我們講的
還是環繞在 topology order
然後接下來環繞在 AOE
那 topology order 要知道怎麼算
那 AOE 和 AOV 的話
是要知道說
它會利用到 topology order 的特性
那去推導
就是推導這個
所謂的 critical path
