Greedy Algorithms

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Interval Scheduling

시작시각과 종료시각이 존재하는 job이 여러개 있을 때, 시간이 겹치는 job은 overlap될 수 없다. 이 때, 최대로 실행할 수 있는 job subset을 구하는 문제이다. 

 

 

 

이 문제를 풀기위해 다음 4개의 Greedy 전략을 생각할 수 있다.

 

1. Start time이 빠른 job 우선

2. Finish time이 빠른 job 우선

3. Job 실행시간이 작은 job 우선

4. Conflict가 작은 job 우선

 

1, 3, 4번은 반례를 통해 Optimal이 아니라는 것을 보일 수 있다.

 

Interval Scheduling의 Greedy alogrithm은 Finish time이 빠른 순으로 실행하는 방법이다.

 

 

 

* Time complexity : $O(nlogn)$

 

 

Pf ) Optimal이 아니라고 가정했을 때 모순임을 보이자.

Greedy 보다 더 좋은 OPT상태가 있을 것이고, $r$번째 job까지 동일하다 하자.

$j_r$이 끝난 시점부터 $j_{r+1}$이 끝나는 시점을 들여다보자. 그 구간에서 더 빨리 끝나는 $i_{r+1}$을 배치하는 것이 앞으로 더 많은 job을 배치할 수 있는 좋은 상태이다.

Greedy가 OPT보다 좋은 상태를 가지므로 가정에 모순이다.

 

 

 

 

Interval Partitioning

시작시각과 종료시각이 존재하는 interval이 여러개 있고, 실행할 수 있는 room이 여러개 있다. 최소의 room을 사용하면서 모든 interval을 실행하도록 schedule하는 문제이다.

 

 

`

 

Depth : 어떤 시간에 겹치는 interval의 최대 개수이다. 위의 예제에서 depth = 3이다.

Depth만큼의 room을 사용하는 것이 optimal이다.

Interval Partitioning 문제의 greedy algorithm은 start time이 빠른 순으로 scheduling하는 것이다.

 

 

 

* Time complexity : $O(nlogn)$

 

 

Pf ) 두 가지 경우로 나누어 optimal임을 보인다.

 

1. 어떤 interval이 unlabeled인 채로 끝나는 경우는 없다.

-> 어떤 interval과 overlap된 것의 개수를 t라하자. Depth 정의에 의해, $t+1 \leq depth$이다. 이를 통해 이 interval이 unlabeled이 아님을 보장한다.

 

2. overlap된 두 개의 interval은 같은 label을 가지지 않는다.

-> 알고리즘상에 exclude과정이 있기 때문에 같은 label을 할당하지 않는다.

 

 

 

Scheduling to Minimze Lateness

length와 deadline을 가지는 job이 여러개 있고 한 시점에 하나의 job밖에 실행하지 못한다. 그리고 lateness이란 finish time - deadline이다. 제일 큰 lateness의 크기를 최소화하는 문제이다.

 

 

 

 

Scheduling to Minimize Lateness문제의 greedy algorithm은 deadline이 빠른 것을 먼저 선택하는 schedule이다.

 

 

 

증명에 앞서, 여러 observation이 있다.

Optimal schedule 중에 idle time이 없는 것이 무조건 존재한다.

Inversion : 두 개의 job의 실행 순서가 뒤바뀐 것을 inversion이라 한다. 모든 schedule은 optimal에서 inversion을 통해 만들 수 있다.

 

 

$d_i < d_j$일 때, inversion이 일어나면 max lateness가 같거나 작아진다.

 

Pf ) swap 전의 lateness를 $l_i, l_j$라 하고 swap 후의 lateness를 $l_{i}^{'}, l_{j}^{'}$라 하자.

Before swap의 lateness는 $l_i$이다.

 

$l_{i}^{'} \leq l_i$,  $l_{j}^{'} \leq l_i$  성립

{$l_{i}^{'}, l_{j}^{'}$}이 After swap의 lateness를 결정하는데,

위의 대소관계에 의해 둘다 $l_i$보다 작다.

따라서, Swap후의 lateness가 Swap전보다 작거나 같다.

 

 

Pf ) Greedy schedule $S$가 optimal임을 증명

$S^*$가 optimal이라 가정. 위의 observation에 의해 $S, S^*$는 idle time을 가지지 않는다고 할 수 있다.

그리고 $S^*$는 $S$에서 inversion을 통해 만들 수 있다.

Inversion이 일어나지 않았다면 $S = S^*$

Inversion이 한번 이상 일어났다면 위의 성질에 의해 Maximum lateness가 증가한다.

 

따라서 $S^*$는 optimal이 아니고 모순이다.

 

 

 

Greedy Analysis Strategies

1. Greedy algorithm stays ahead

각 step에서 optimal 여부를 증명하는 방법

ex) Interval scheduling

 

2. Structural

'Depth'와 같은 structure(value)를 발견하고 이를 중심으로 접근

ex) Interval paritioning

 

3. Exchange argument

'Inversion'과 같이 optimal을 해치는 방향으로 설정한뒤 증명하는 방법

ex) Exchange argument

 

위에서 소개한 알고리즘 이외에도 무수히 많은 greedy algorithm이 있다.