AOE(activity on edge) 네트워크

AOE(activity on edge) 네트워크

1. 개요

- AOE 네트워크는 그래프의 일종으로, 간선에 가중치가 있는 방향그래프이다. 간선은 작업, 간선의 가중치는 작업 수행 시간, 간선의 방향은 사건의 선후관계를 나타내며, 간선의 끝부분에 있는 노드는 그 작업의 수행의 결과로서 도달하게 되는 사건을 의미한다. 어떤 사건도 그 선행 작업이 종료되기 전에는 일어날 수 없다.

- 수개의 작업을 동시에 수행할 수 있지만, 모든 작업을 다 수행해 최종 사건에 도달하기까지 걸리는 시간은 아무리 빨라도 시작 노드부터 끝 노드까지의 최장경로길이(이를 임계경로라 한다)다.

2. 임계경로를 구하는 알고리즘

1) 개념

- 각 노드 $i$에 대해 함수 e($i$)와 l($i$)의 값을 구해둔 후, 이를 이용해 모든 간선(작업)의 '임계도'를 구한다.

함수명 정의 e($i$) 노드 $i$에 도달하기 위해 필요한 최소시간 l($i$) 전체 작업이 임계경로 시간 안에 수행되기 위해 노드 $i$에서 출발해야 하는 최대 시간 간선 ($i$, $j$)의 임계도 l($i$) - e($i$) + W($i$, $j$)

- 모든 간선에 대해 임계도를 구해 보면, 어떤 간선의 임계도는 0인 경우가 있다. 이 간선들이 임계경로를 구성하는 간선이다.

2) e($i$)를 구하는 알고리즘

-위상정렬을 수행하면서, 현재 도달한 노드 $i$와 연결된 모든 후행 노드 $k$에 대하여 e($k$) = max( e($k$), e($i$) + W($i$, $k$) ) 값을 계산함으로써 e($i$) 값을 구할 수 있다.

3) l($i$)를 구하는 알고리즘

- 일단 위상정렬을 통해 임계경로의 길이를 구한 후, l($i$) 배열을 이 값으로 초기화한다.

- 그 다음, 모든 간선의 방향을 반대로 바꾸고 끝 정점에서부터 거꾸로 위상정렬을 수행한다. 이때 현재 도달한 노드 $i$와 연결된 모든 후행 노드 $k$에 대하여 l($k$) = max( l($k$), l($i$) - W($i$, $k$) ) 값을 계산함으로써 l($i$) 값을 구할 수 있다.

from http://lkwks.tistory.com/25 by ccl(A) rewrite - 2021-09-25 04:27:05