1. 다양한 접근법
- Earliest start time (Earlist Job First) : 시작 시간이 가장 빠른 작업들로 스케쥴링, 하지만 이는 항상 최적해를 구하지 않는다. 정확하지 않은 알고리즘
- Shortest interval (Shortest Job First) : 가장 짧은 구간(시간이 적게 걸리는)을 가진 작업들로 스케쥴링, 하지만 이 또한 반례가 존재. 항상 최적해를 구할 수 없다.
- Earilest finish time : 작업 종료 시간이 가장 빠른 작업들로 스케쥴링, 몇가지 예시들을 생각해보면 최적이라는 것을 알 수 있다. [증명 1.2]
* 스케쥴링 문제의 해는 구간들의 부분집합으로 이루어진다. (Exaustive Scheduling)
즉, 2^n개의 부분집합 각각 모두를 고려하면 해가 반드시 하나는 존재한다.
하지만 시간복잡도가 커 문제를 해결하는데 시간이 오래걸린다.
-> 이보다 더 빠른 시간 안에 해결할 수 있는가?
- Earilest finish time (Optimal Scheduling) : 수학적 귀납법으로 재귀적인 증명이 가능하다. 어떤 작업 E를 제외하고 최적의 해인 부분집합 I’이 있다고 생각할 때, (가정) 작업 시간이 겹치는 다른 작업들(E, E’, E’’, …)과 비교했을 때 가장 먼저 끝나는 작업 E를 포함하는 것이 최적의 해라는 것을 증명하면 된다.
2. 최적의 접근법에 대한 증명과 고찰
즉, E를 포함하는 부분집합이 최대 구간의 수를 갖는다를 증명 (최대 구간의 수를 갖는 독립집합)
// (독립집합 (Independent Set) : 집합 간에 서로소가 되는 집합)
: 그렇다면 E를 포함하지 않는 부분집합이 최적의 해가 아니라고 할 때 (E’을 포함한 부분집합이 최적이라면) E를 포함하도록 변형이 가능하다면 이를 증명할 수 있다. E와 E’ 작업을 뺀 부분집합은 E와 E’의 작업시간과는 겹치지 않는다. 그러므로 E’을 빼고 E를 포함해도 구간의 수는 똑같이 최적임을 알 수 있다. E를 포함한 부분집합과 E’ 포함한 부분집합의 구간의 수는 같다는 말.
* 쉽게 생각해보면 빨리 시작하는 작업을 고르는 알고리즘과는 다르게 현재 가장 빨리 끝나는 작업(E)을 매 순간에 고르게 됐을 때,
선택된 작업은 시작시간이 어떻게 됐든 간에 매 순간에 가장 빨리 끝나는 작업(E)을 고르는 것을 반복했기 때문에
이전에 고른 가장 빨리 끝나는 작업(E') 시간이 현재 고른 가장 빨리 끝나는 작업(E)의 시작 시간보다 늦을 수가 없다는 이야기이다.
즉, 가장 빨리 끝나는 작업들을 계속해서 고르게 되면 처리할 수 있는 가장 많은 작업의 수를 고를 수 있다는 것이다.
3. 시간복잡도
- 시간복잡도는 O(NlogN)에 가능.
1) 입력 데이터를 정렬 2) 입력 데이터가 들어올 때마다 힙(Heap) 자료구조에 삽입하여 가장 빨리 끝나는 작업 시간을 가진 데이터가 먼저 pop되도록 구성
위의 두 가지 방법이 있다. 이후 각각 작업시간을 비교하여 겹치는지 여부를 확인해주며 최대 처리가능한 작업의 개수를 세면 된다.
4. 심화
4.1 작업들에 가중치(비용)이 존재한다면?
: 결론부터 말하면 정점에 가중치가 존재하는 Interval Graph에서 특정한 가중독립집합을 구하는 문제가 된다.
// 독립집합 <=> 클릭 (Clique) : 모든 가능한 변이 존재하는 꼭짓점들의 부분집합
여기서 말하는 클릭은 Interval Graph에서 정점의 모든 쌍에 대해 간선이 존재하는 정점의 부분집합.
* Coloring Problem : 지도가 있을 때 인접한 구간이면 서로 다른 색으로 색칠(서로 배타적인 구간을 최소 개수로 나눠라)하는 문제
-> NP-Complete
(구간을 정점으로 하고 인접한 구간에 대해 간선을 구성하면 최소 개수의 독립집합으로 그래프를 칠하는 문제라고 볼 수 있다.)
Interval Graph에서는 Coloring 부분집합의 수와 Clique의 수가 같다. 평면 그래프는 어떤 경우이든 간에 4가지 색으로 해결 가능.
star형 그래프의 경우는 5가지 색이 필요하다.
모든 부분집합을 탐색할 필요없이 구간들의 관계를 나타내는 방향그래프를 구성한다.
왼쪽에 있는 구간에서 부터 오른쪽에 있는 구간으로 사이클이 없는 방향그래프(Directed Acyclic Graph)로 구성이 된다. // DAG라는 것은 다른 그래프들보다 빠른 시간 안에 해결 가능한 문제로 만들 수 있다는 의미.
위의 DAG를 위상정렬한 뒤, 정점의 가중치의 합이 최대가 되는 최대가중경로를 구하면 된다. 최대가중경로를 구하는 알고리즘은 모든 정점들에서 그 정점을 지나는 순간에 가장 큰 가중치를 가질 때의 값을 배열에 저장한 뒤, 배열에서 가장 큰 값에서 시작하여 역산(정점의 가중치는 빼고 해당 값을 배열에서 찾는 작업의 반복)으로 경로를 구할 수 있다. 구간에 대한 문제를 그래프 문제로 변형하였기 때문에 최악의 경우 O(N^2)의 시간복잡도를 갖는다.
- 조금 더 빠른 시간 안에 문제를 해결할 수 있는가? 다른 방안의 변형이 가능한가?
구간들의 관계를 나타내는 그래프를 전부 구성할 필요가 없다. 왼쪽 끝점 or 오른쪽 끝점을 기준으로 정렬하면 DAG를 구성하여 위상정렬할 필요없이 구간을 순차적으로 볼 수 밖에 없다.
이것이 라인 스위핑 [Algorithm 2]
구간을 순차적으로 보면서
- 겹치는 구간이 아닌지를 확인
- 이전 부분집합들 안에서 최대의 가중치의 값만을 따로 저장하여 확인
- 각 구간에서 가능한 경우에 대해서 가중치의 합들을 짝(끝점, 가중치의 합)을 지어 가장 먼저 오는 끝점을 기준으로 하는 최소힙에 저장한다. (현재 보고있는 구간의 시작점 좌표가 이전 구간들의 끝점 좌표를 비교하여 겹치는 구간을 확인해주기 위함.)
- 반복해서 힙에 push, pop을 반복하여 왼쪽부터 오른쪽 구간까지 모두 확인하여 최대 가중치를 구해주면 된다. 위에 나온 가중치를 합하는 과정에 대한 기록과 역산을 포함하면 경로 또한 구할 수 있다.
@ Search Keyword : 구간경로에서 최대가중치를 찾는 알고리즘