AOE(Activity On Edge) 네트워크에서 해당 작업의 가장 … | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 08년 1회차
AOE(Activity On Edge) 네트워크에서 해당 작업의 가장 이른 시간(earliest time)과 가장 늦은 시간(latest time)을 각각 나타내는 early(i)와 late(i)를 구하고자 한다. 가장 이른 사건 발생 시간(earliest event occurrence time)을 earliest라고 하고, 가장 늦은 사건 발생 시간(latest event occurrence time)을 latest라고 할 때, 작업 ai가 간선 <k, l>로 표현된다면, 다음 식으로부터 early(i)와 late(i)를 구할 수 있다.early(i) = earliest[k]다음과 같은 AOE 네트워크에서 early(i)와 late(i)를 구한 결과 중 옳지 않은 것은?
late(i) = latest[l] - 작업 ai의 작업 시간(duration)
1
early(3) = 6, late(3) = 10
2
early(5) = 10, late(5) = 10
3
early(7) = 7, late(7) = 12
4
early(9) = 14, late(9) = 14
해설
작업 a3은 early(3) = 6이지만 late(3) = 11이므로, late(3)을 10으로 제시한 결과가 옳지 않다.
전진 계산으로 earliest를 구하면 V1 = 6, V3 = 10, V4 = 7, V6 = 14, V7 = 11, V8 = 19이다. 후진 계산으로 latest를 구하면 V6 = 14, V7 = 16, V4 = min(14 − 2, 16 − 4) = 12이다.
a3은 간선 <1, 4>, 작업 시간 1이므로 late(3) = latest[4] − 1 = 11이다.
- early(5) = 10, late(5) = 10: a5는 <3, 6>, 시간 4로 earliest[3] = 10, latest[6] − 4 = 10이다.
- early(7) = 7, late(7) = 12: a7은 <4, 7>, 시간 4로 earliest[4] = 7, latest[7] − 4 = 12이다.
- early(9) = 14, late(9) = 14: a9는 <6, 8>, 시간 5로 earliest[6] = 14, latest[8] − 5 = 14이다.
오류나 개정된 내용이 보이면 알려주세요
