[Algorithm Part 3] 7. Greedy Approach algorithms

이번 글에서는, 유명한 greedy 알고리즘에 대해 살펴볼 것이다.

---

1. Single-source shortest paths

Problem

source vertex(=s)에서 그 외 나머지 vertex까지의 최소 경로를 구하는 문제다.

이 문제의 핵심은 다음과 같다. "최소 경로의 하위 경로도 최소 경로"다!!

Approach (Dijkstra's algorithm)

빈 F, Y에서 시작해 T가 MST가 될 때까지 edge를 순차적으로 추가한다.

• selection procedure: "V-Y의 vertex 중 s와 가장 가까운 vertex(=v)"를 선택한다.
  
• feasibility check: 바로 v와 Y를 잇는 edge(=$e$)를 T에 추가하고, v를 Y에 추가한다.
  (왜냐하면, $e$를 추가한 T는 무조건 순환하지 않기 때문이다.)
• solution check: Y == V인지 확인한다.

Correctness of algorithm

이전 글(Algorithm Part 2. Shortest Paths)에서 증명함

Analysis

base operation: 비교(=compare) 연산

input size: n(=# of vertex), m(=# of edge)

data structure	every-case time complexity
array PQ	$\Theta(n^2)$
heap PQ	$\Theta(m\log n)$

그래프가 sparse하면 heap PQ, dense하면 array PQ를 사용한다.

---

2. Scheduling

2.1. Minimizing total time in the system

Problem

모든 schedule 중 total time in the system이 최소인 schedule을 찾는 문제다.

The time spent both waiting and being served is called the time in the system.

service 시간이 최소인 작업부터 scheule에 추가하는 것이 문제의 핵심이다.

Approach

빈 schedule(=S)에서 시작해 모든 작업이 schedule에 포함될 때까지 작업을 순차적으로 추가한다.

• selection procedure: "현재 선택되지 않은 job 중 minimum service time job(=j)"를 선택한다.
  
• feasibility check: 바로, j를 S에 추가한다.
  (점검해야할 조건이 없다.)
• solution check: S에 모든 작업이 들어 있는지 확인한다.

Correctness of algorithm

"total time in the system이 최소인 schedule은 "작업을 serivce time 기준 오름차순으로 scheduling한 것이다."

귀류법을 통해 위 명제가 참임을 증명하겠다.

 

만약 optimal schedule이 오름차순이 아니면, 적어도 $t_i > t_{i+1}$인 부분이 존재한다.

($t_i$: i번째 작업의 service time)

만약 i번째 작업이랑, i+1번째 작업을 바꾸면, $T^\prime = T + t_{i+1} - t_i$가 된다.

($T$ = total time of original schedule, $T^\prime$ = total time of rearranged schedule)

---

2.2. Scheduling with deadlines

Problem

각 작업에는 마감일(=deadline)과 마감일 전에 시작하면 주는 보상(=profit)이 있을 때,

보상을 최대로 받을 수 있는 schedule일 구하는 문제다.

즉, 최대 보상을 주는 feasible sequence(=optimal sequence)를 찾는 문제다.

schedule that has a job scheduled after its deadline is called impossible.

feasible sequenceif all the jobs in the sequence start by their deadlines.

set of jobs is called feasible set if there exists at least one feasible sequence for the jobs in the set.

보상이 높은 작업부터 scheule에 추가하는 것이 문제의 핵심이다.

Approach

빈 sequence(=S)에서 시작해 선택할 작업이 없을 때까지 작업을 순차적으로 추가한다.

• selection procedure: "현재 선택되지 않은 job 중 maximum profit job(=j)"를 선택한다.
  
• feasibility check: 바로, S∪{j}이 feasible set인지 점검한다.
  만약 feasible set이라면, S에 j를 추가한다. (by Lemma 4.3)
  
• solution check: 더 이상 선택할 작업이 없는지 확인한다.

Lemma 4.3

Let S be a set of jobs. Then S is feasible if and only if the sequence obtained by ordering the jobs in S according to nondecreasing deadlines is feasible.

Correctness of algorithm

귀납법을 통해 증명하겠다.

작업이 보상을 기준으로 내림차순으로 정렬되어 있다.

알고리즘이 첫 n개 작업에서 얻은 작업 집합(=A$^\prime$)이 첫 n개 작업에서 얻은 최적 집합(=B$^\prime$)이라고 가정하자.

이때, 알고리즘이 첫 n+1개 작업에서 얻은 작업 집합(=A)와 첫 n+1개 작업에서 얻은 최적 집합(=B)가 같음을 보여주면 된다.

 

Case 1: B가 n+1번째 작업을 포함하고 있지 않을 경우, B와 B$^\prime$이 같다.

알고리즘에 의해 A$^\prime$ ⊆ A이기 때문에, A는 B보다 무조건 보상이 크거나 같다. 즉, A는 최적 집합이다.

 

Case 2: B가 n+1번째 작업을 포함하고, A도 n+1번째 작업을 포함하는 경우,

B = B$^\prime$ ∪ {n+1번째 작업}, A = A$^\prime$ ∪ {n+1번째 작업}이다.

A$^\prime$과 $^\prime$은 같기 때문에, A는 최적 집합이다.

 

Case 3: B가 n+1번째 작업을 포함하고, A도 n+1번째 작업을 포함하지 않는 경우,

B에서 n+1번째 작업이 차지하고 있는 위치가 i라고 할 때, A의 i번째 위치에는 다른 작업($j_i$)이 위치해 있다.

B에서 $j_i$번째 작업이 차지하고 있는 위치가 i+1라고 할 때, A의 i+1번째 위치에는 다른 작업($j_{i+1}$)이 위치해 있다.

이 과정을 계속 이어나가다보면, A에는 있고 B에는 없는 $j_k$번째 작업이 존재한다. (작업 개수는 유한하기 때문이다.)

n+1번째 작업을 없애고, i번째 위치에 $j_i$작업을 이동시키고, i+1번째 위치에 $j_{i+1}$작업을 이동시키고, ..., k번째 위치에 $j_{k}$작업을 추가시키는 방식으로 B를 수정할 경우, 간단히 말해, n+1번째 작업을 $j_k$작업으로 대체할 경우, B의 보상이 올라간다. ($j_k$작업 보상이 n+1번째 작업 보상보다 크기 때문이다.) 이는 모순이므로, 위 경우는 존재하지 않는다.

Analysis

base operation: 비교(=compare) 연산

input size: n(=# of jobs)

every-time time complexity: $\Theta(n^2)$

---

3. Optimal binary code

Problem

문자열 파일을 최소의 bit 개수로 표현할 수 있는 codeword를 찾는 문제다.

optimal binary code의 한 종류인 huffman code를 통해 이 문제를 풀 수 있다.

huffman code는 optimal prefix code다.

Prefix code has no codeword for one character constitutes the beginning of the codeword for another character.

Every prefix code can be represented by a binary tree(=$T$) whose leaves are the characters that are to be encoded.

$$\text{bits}(T) = \sum_{i=1}^n \text{frequency}(v_i)\text{depth}(v_i)$$

$\text{frequency}(v_i)$ is the number of times $v_i$ occurs in the file.

$\text{depth}(v_i)$ is depth of $v_i$ in $T$.

service 시간이 최소인 작업부터 scheule에 추가하는 것이 문제의 핵심이다.

Approach

각 character를 root노드로 두는 트리를 만든다. 즉, n개의 트리가 만들어진다.

트리가 optimal binary code에 해당되는 이진 트리가 될 때까지 노드를 선택한다.

• selection procedure: "frequency가 가장 낮은 2개 트리(u, v)" 선택한다.
  
• feasibility check: u와 v를 하나로 합쳐 트리 w로 만든다.
  frequency(w) = frequency(u) + frequency(v)
  (점검해야할 조건이 없다.)
  
• solution check: 트리가 하나가 되는지 확인한다.

Correctness of algorithm

귀납법을 통해 증명하겠다.

알고리즘이 n번째 단계에서 얻은 서브 트리들이 optimal binary tree(=T)의 서브 트리라고 가정하자.

이때, 알고리즘이 n+1번째 단계에서 얻은 서브 트리들도 optimal binary tree(=T)의 서브 트리임을 보여주면 된다.

 

n+1번째 단계에서 선택한 트리가 u와 v라고 할 때,

 

Case 1: 만약 u와 v가 T에서 sibling인 경우, n+1번째 단계에서 얻은 트리(=C)는 무조건 서브 트리다.

 

Case 2: 만약 u와 v가 T에서 sibling이 아닌 경우,

1). u와 sibling인 서브 트리 w가 존재(by Lemma 4.4)하고, 2). depth(u)  ≥ depth(v)이다.
( u의 깊이가 v의 깊이보다 높으면, u와 v의 위치를 바꾼 트리가 보다 optimal하는 모순이 발생하기 때문이다.)

이때, w와 v의 위치를 바꾼 트리(=T$^\prime$)를 만든다면, bits(T$^\prime$) ≤ bits(T)가 된다.

왜냐하면, frequency(w) > frequency(u)고 depth(w)  ≥ depth(u)이기 때문이다.

이는 모순이므로, 위 경우는 존재하지 않는다.

Lemma 4.4

The binary tree corresponding to an optimal binary prefix code is full. That is, every nonleaf has two children

Analysis

base operation: 비교(=compare) 연산

input size: n(=# of jobs)

every-time time complexity: $\Theta(n\log n)$