알고리즘(Algorithm) - Greedy Algorithm
1. Interval Scheduling
- j라는 일이 sj에 시작해서 fj에 끝날 때, 일들의 수행시간이 서로 겹치지 않으면서 일을 최대로
많이 할 수 있도록 스케쥴링하는 문제.
여러가지 Greedy Algorithm들을 생각해보고 Counter Example을 찾아서 하나씩 제외시킴
a) Earliest start time (시작시간이 빠른 순서대로)
반례는 아래와 같다.
b) Shortest interval (일의 시간이 가장 짧은 순서대로)
반례는 아래와 같다.
c) Fewest conflicts (겹치는 일이 가장 적은 순서대로)
반례는 아래와 같다.
d) Earliest finish time (끝나는시간이 빠른 순서대로)
반례를 찾을 수 없으며, 알고리즘은 다음과 같다.
이 알고리즘은 O(nlogn)의 러닝타임을 갖는다.
-> Merge Sort를 사용하여 Sorting하는데에 O(nlogn)이며, for루프는 O(n)이므로
- Optimality
Theorem) Greedy algorithm is optimal
Pf) (by contadiction)
1. 그리디 알고리즘으로 찾은 결과가 optimal이 아니라고 가정하고 그리디 알고리즘 결과와
실제 optimal한 결과가 있을 때 r번째 까지는 같다고 가정하자.
2. optimal한 결과의 r+1번째 일을 그리디 알고리즘의 결과와 똑같도록 만들 수 있으며 여전히
optimal이고 그리디 알고리즘의 결과와 r+1번째까지 같게 된다.
3. 그러나, 가정에서는 r번째 까지만 같다고 했으므로 모순이다.
2. Interval partitioning
- j라는 강의는 sj에 시작하고 fj에 끝날 때, j개의 강의가 있을 때, 시간과 강의실이 겹치지 않도록
최소한의 강의실을 배정하는 방법을 찾는 문제.
※ Key observation. Number of classrooms needed >= depth
(필요한 강의실의 수는 최소한 특정한 시간에 겹치는 강의의 갯수 이상이다.
시작시간 순서대로 강의실을 배정하면 되는데, 알고리즘은 다음과 같다.
이 알고리즘은 O(nlogn)의 러닝타임을 갖는다. ( Sorting에 O(nlogn), for루프에 O(n) )
- Optimality
Theorem) Greedy algorithm is optimal
pf)
1. d를 그리디 알고리즘으로 할당한 강의실의 갯수라고 하자.
2. d번째 강의실은 d-1번째 강의실에 배정된 강의와 시간이 겹치는 강의가 생겼을 때
할당된다.
3. 이러한 d번의 일은 각각의 sj 이후에 발생한다.
4. 시작시간 순으로 정렬했기 때문에, 이렇게 강의가 겹치는 일은 sj이후에 시작되지 않는
강의에 의해 발생한다.
5. 그래서, sj+￡ 시점에 d개의 겹치는 강의가 있다.
6. Key observation에 따르면 Number of classrooms needed >= depth이다.
3. Minimizing lateness problem
- 한번에 한가지의 job만 실행할 수 있으며, job j는 끝마치는데에 tj만큼의 시간이 걸리고,
시작시간은 sj, 끝나는 시간은 fj, 마감시간은 dj일 때(fj = sj + tj) lateness lj는 fj - dj중에
가장 큰 값을 말하며 lateness가 가장 작도록 job들을 스케줄링하는 문제.
a) Shortest processing time first
반례 : t1 = 1, d1 = 100
t2 = 10, d2 = 10
b) Smallest slack
반례 : t1 = 1, d1 = 2
t2 = 10, d2 = 10
c) Earliest deadline first
알고리즘은 다음과 같다.
- Observation
There exists an optimal schedule with no idle time.
(공백이 없도록 왼쪽으로 밀면 idle time이 없는 schedule이 만들어진다.)
- Observation
The greedy schedule has no idle time.
- Inversions
i라는 job이 j보다 deadline이 앞서지만, j가 i앞에 위치된 schedule을 inversion이라 한다.
- Observation
Greedy schedule has no inversions.
- Observation
If a chedule (with no idle time) has an inversion, it has one with a pair of inverted jobs
scheduled consecutively.
- inversion proof
Claim) Swapping two consecutive, inverted jobs reduves the number of inversions by one
and does not invrease the max lateness.
pf) Let L be the lateness before the swap, and let L' be it afterwards.
1. L'k = Lk for all k ≠i,j
2. L'i <= Li
* L'j = f'j - dj (definition)
= fi - dj (j finishes at time fi)
<= fi - di (i<j)
<= Li (definition)
- Optimality
Theorem) Greedy schedule S is optimal.
pf)
1. S*를 optimal한 schedule이고 inversion이 최소라고 가정하자.
2.
1) S*가 inversion이 없는 경우
S = S*이다.
2) S*가 inversion이 있는 경우, i와 j를 inversion이 발생한 인접한 job들이라 하자
i와 j를 swap해도 maximum lateness는 증가하지 않으며 오히려 감소한다.
inversion이 최소라는 가정에 모순
4. Optimal Caching
- Goal
Eviction schedule that minimizes number of cache misses.
- Cache hit
item already in cache when requested.
- Cache miss
item not already in cache when requested : must bring requested item into cache, and evict some existing item, if full.
- Farhest-in-future
Evict item in the cache that is not requested until farthest in the future.
- Reduced Ecivtion Schedules
A reduced schedule is a schedule that only inserts an item into the cache in a step in which that item is requested.
Claim) Given any unreduced schedule S, can transform it into a reduced schedule S' with
no more cache misses.
pf) (by induction)
1. Suppose S breings d into the cache at time t, without a request.
2. Let c be the item S evicts when it brings d into the cache.
3. Case1 : d evicted at time t', before next request for d.
Case2 : d requested at time t' before d is evicted
- Optimality
Theorem) FF is optimal eviction algorithm.
pf) (By induction)
1. optimal 알고리즘으로 찾아낸 schedule을 S라 하고, j번째 까지 같은 행동을 하는
FF알고리즘을 SFF라 하고, SFF와 j+1번째 까지 같은 행동을 하는 알고리즘을 S'이라 하자.
2. j = 1 일 때, S = SFF이다.
3. j > 1 일 때, j번째에 다음과 같이 cache에 item이 들어있다고 하자.
S -> a b e f
S' -> a b e f
Case 1) j+1번째 request가 a,b,e,f중 하나일 경우
S와 S'모두 cache hit이므로 S = S'
Case 2) j+1번째 request가 c이고, 같은 item을 evict한 경우
S = S'
Case 3) j+1번째 request가 c이고, 서로 다른 item을 evict한 경우
S는 f를, S'은 e를 evict했다고 생각하자.
S -> a b e c
S' -> a b c f
j'을 j+1번 바로 뒤에 오는 request라고 하면,
Case 3a) j' = e
S'이 e가 제일 나중에오기 때문에e 를 빼고 c를 집어넣었으므로,
j'은 e가 될 수 없다.
Case 3b) j' = f
S가 e를 빼면 S = S'
S가 그 외를 빼면 S'이 e를 cache로 가져오면 S = S'
Case 3c) j' = k
S가 e를 빼면 S'은 f를 빼고 k를 넣으면 S = S'
S가 그 외를 빼면 S = S'
5. Shortest Path Problem
- Dijkstra's algorithm
Maintain a set of explored nodes S for which we have determened the shortest path distance d(u) from s to u.
Initialize S = {s}, d(s) = 0.
Repeatedly choose unexplored node v which minimizes π(v) = S에 속한 노드 u와 인접한 노드인 v의 거리 d(u)의 최솟값 + 시작 노드에서 u까지의 거리
add v to S, and set d(v) = π(v).
'알고리즘' 카테고리의 다른 글
| 알고리즘(Algorithm) - Network Flow (0) | 2015.05.30 |
|---|---|
| 알고리즘(Algorithm) - Algorithm Analysis (0) | 2015.03.29 |
| 알고리즘(Algorithm) - Stable Matching (0) | 2015.03.08 |
