6-9강 - [중요] Dynamic Programming 9 (Directed Acyclic Graphs)

9. Directed Acyclic Graphs 

: cycle이 없는 graph

1) Activity On Vertex (AOV) 

Vertex : action

Edge : precedence relation

 

0> 기본 용어

i = j의 predecessor (j = i의 successor)

i = k의 immediate predecessor (k = i의 immediate predecessor)

 

1> relation - partial order

[1] transitive (iRj & jRk => iRk)

[2] irreflexive (iRi가 항상 성립하지 않는다.)

 

2> topology order

아래 조건을 만족하는 linear ordering

"i = j의 predecessor" => "i precede j in linear ordering"

(선후수과목 수강과 유사)

 

3> Linear Ordering on AOV network (Topological Ordering, 위상 정렬)

AOV에 대한 Topological Ordering을 구하기

[1] indegree counting : 모든 edge에 대해 'u -> v'가 있으면 v의 indegree(incoming degree)를 1 증가

[2] indegree=0 (predecessor가 없는)인 vertex를 stack에 저장

[3] stack에서 u를 pop -> u R v인 v의 indegree 1 감소 (만약 indegree가 0이 되면 S에 push)

 

2) Activity On Edge (AOE)

edge : activity (작업에 필요한 시간)

vertex : event

=> event에 선후 관계가 있으며, 이를 다 완수하는데 걸리는 시간을 측정

 

1> completion time 관련 정의

[1] edge 관련 변수

early(i) : activity i를 시작할 수 있는 가장 빠른 시간

late(i) : activity i를 시작할 수 있는 가장 느린 시간 (주어진 project duration을 준수하는 전제 하에)

=> early(i) <= activity i의 시작 시간 <= late(i)

[2] vertex 관련 변수

earliest[k] : event k가 일어날 수 있는 가장 빠른 시간

latest[k] : event k가 일어날 수 있는 가장 느린 시간 (주어진 project duration을 준수하는 전제 하에)

=> early(k) <= event k의 시작 시간 <= latest(k)

 

2> 관계식

[1] early(i) = earliest[k] 

(activity i를 시작할 수 있는 가장 빠른 시간 = k가 

[2] late(i) = lateset[l] - duration of <k, l> = lateset[l] - activity i 지속 시간

 

3> earliest[l] 구하기 (forward topological searching)

4> latest[k] 구하기 (backward topological searching)

 

cf> d : deadline (d >= earilest(n+1) 이어야 task를 완수할 수 있습니다.)

 

5> d = earilest(n+1)인 상황

[1] early(i) = late(i) -> activity critical

[2] slack = late(i) - early(i)

[3] Critical Path

(원래 정의)시작 Vertex부터 최종 Vertex까지의 가장 긴 경로의 길이
(재정의) 모든 edge가 activity critical (slack = 0)

 

 

 

 

 

<풀이 꼭 참고>

m.blog.naver.com/heojh93/220019810426

wccclab.cs.nchu.edu.tw/www/images/Data_Structure_105/chapter6.pdf