Activity - Selection Problem 프로그래밍

Activity - Selection Problem

To select a maximum - size of mutually compatible activities

Activities  :  S = { 1 , 2 , 3 ... n }

Start Time : Si

Finish Time : Fi

Activities i and j are compatible if Si >= Fi or Sj >= Fj).

i	1	2	3	4	5	6	7	8	9	10	11
Si	1	3	0	5	3	5	6	8	8	2	12
Fi	4	5	6	7	8	9	10	11	12	13	14

다음과 같은 스케쥴표가 있다고 가정하자.

i 는 각 시간들의 인덱스이고, Si 는 시작 시간 , Fi 는 종료 시간을 의미한다.초기 S1 은 1초에 시작해서 4초에 종료 된다. 4초 이후에 시작될수 잇는 Activities 는 [4 , 6 , 7 , 8 , 9 , 11] 이 되고, 4를 StartTime 으로 다시 시작한다. (문제를 단순하게 하기 위해 이미 Finish Time 으로 정렬된 배열을 입력으로 받는다)

이 스케쥴표에서 가장 효과적으로 사용하기 위해서는 어떤 순서로 동작해야 할까. Activity Selection 알고리즘은 현제 Activity가 적절하면 그것을 실행한다. 여기서 적절하다는 것은 종료 시간이 다음 시작시간보다 작거나 같을떄를 의미한다.

그러면 이 알고리즘이 어떤 순서로 동작하는지 보자. 초기값으로 1을 갖는다.

S[  1] = 1, F[  1] = 4

S[  2] = 3, F[  2] = 5   // 인덱스 2는 적절하지 않다 그 이유는 F[1] <= S[2] 이 성립하지 않기 때문이다.

S[  3] = 0, F[  3] = 6   // 마찬가지로 성립하지 않는다.

S[  4] = 5, F[  4] = 7   // F[1] <= S[4] 성립하기 때문에 적절하다.

S[  5] = 3, F[  5] = 8   // 부적절

S[  6] = 5, F[  6] = 9   // 부적절

S[  7] = 6, F[  7] = 10 // 부절절

S[  8] = 8, F[  8] = 11 // 적절

S[  9] = 8, F[  9] = 12 // 부적절

S[10] = 2, F[10] = 13 //  부적절

S[11] =12, F[11] = 14 //  적절

Activity Selection 에 의해 다음과 같은 스케쥴이 정해진다.

1[1,4] -> 4[5,7] -> 8[8,11] -> 11[12,14]

이 알고리즘의 복잡도를 구해도록하겟다. 두가지 경우의 시간이 걸린다.

1. Finish Time 으로 배열을 정렬하기 위해 정렬 알고리즘을 사용하였다. O(n lg n)

2. 시작부터 끝까지 한번 훑기 때문에 θ(n) 의 시간이 걸린다.

이를 프로그램으로 구현해 보도록 하자.

소스 화면 ( 환경 VC 2005 )

결과 화면

Activity Selection 알고리즘은 optimal solution 을 제공할까? 답은 아니다. 그러나 이 문제에 대해 항상 Optimal solution을 보장해 주는 알고리즘이 있다. 그것은 GREED - ACTIVITY - SELECTOR 이다. 일단 여기서는 Activity Selection 문제에 초점을 맞추도록 하겠다.