16. Greedy Algorithms

최적화 문제에 동적 계획법이 과도할 때도 있다. 때로는 국소적으로 최적인 해를 계속 이어나가는 탐욕적 알고리즘이 전역적으로 최적인 해를 구성하기도 한다.

16.1. An activity-selection problem

첫 번째 예는 시간표에서 여러 활동들을 가능한 많이 겹치지 않게 고르는 문제이다. 각각의 활동들이 시작 시간끝나는 시간이 있을 때 활동간 시간이 겹치지 않으면 호환 가능하다고 하자. 활동 선택 문제에서는 서로 호환 가능한 활동들을 가장 많이 고른다. 이는 동적 계획법으로 풀 수 있지만, 탐욕적 알고리즘으로도 풀 수 있으며 그것이 더 빠르다.

The optimal substructure of the activity-selection problem

활동 선택 문제는 최적 부분 구조를 가진다. 그러므로 동적 계획법으로 풀 수 있다.

Making the greedy choice

활동 선택 문제는 탐욕적 해를 구하는 것으로 풀 수 있다. 즉, 그 시점에서 가장 빨리 끝나는 활동을 계속 선택해나가는 것으로 충분하다.

Theorem. 공집합이 아닌 부분 문제 S_{k}에 대해, 그 부분 문제 내에서 가장 빨리 끝나는 활동을 a_{m}이라 하면, a_{m}S_{k} 내에서 서로 겹치지 않는 활동들의 최대 크기 부분집합에 포함된다.

탐욕적 알고리즘에 의한 해를 구성하는 과정은 상향식일 필요가 없으며 하향식으로도 풀 수 있다.

A recursive greedy algorithm

이를 재귀적으로 풀면 다음과 같다.

RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n)
m = k + 1
while m ≤ n and s[m] < f[k]
    m = m + 1
if m ≤ n
    return {a_m} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n)
else
    return Φ

이 때 활동들이 끝나는 시간으로 이미 정렬되어 있다는 가정하에 이 알고리즘의 수행 시간은 \Theta(n)이 된다.

An iterative greedy algorithm

이를 반복적으로 풀면 다음과 같다.

GREEDY-ACTIVITY-SELECTOR(s, f)
n = s.length
A = {a_1}
k = 1
for m = 2 to n
    if s[m] ≥ f[k]
        A = A ∪ {a_m}
        k = m
return A

역시, 활동들이 끝나는 시간으로 이미 정렬되어 있다는 가정하에 이 알고리즘의 수행 시간은 \Theta(n)이 된다.

16.2. Elements of the greedy strategy

탐욕적 전략을 요약하면 다음과 같다.

  1. 문제의 최적 부분 구조를 판정한다.
  2. 재귀적 해를 구성한다.
  3. 탐욕적 선택을 하면 하나의 부분 문제만이 남음을 보인다.
  4. 탐욕적 선택을 하는 것이 안전함을 보인다.
  5. 탐욕적 선택을 구현하는 재귀적 알고리즘을 구성한다.
  6. 재귀적 알고리즘을 반복적으로 바꾼다.

이를 요약하면 다음과 같다.

  1. 최적화 문제를 변형해서, 선택을 하면 하나의 부분 문제만 풀게 되도록 한다.
  2. 탐욕적 해로부터 얻어지는 해가 최적해가 됨을 보인다.
  3. 부분 문제의 최적해에 탐욕적 선택으로 얻은 해를 결합하면 원본 문제의 최적해가 되는 최적의 부분 구조를 증명한다.

Greedy-choice property

탐욕적 해에 필요한 첫 번째 핵심 요소는 탐욕적 선택 특성으로, 국소적으로 최적인 (탐욕적) 해를 조합해 전역적으로 최적인 해를 구성할 수 있다는 것이다. 전처리를 통해 탐욕적 해를 구하는 방법을 더 효율적으로 만들 수 있다.

Optimal substructure

문제의 최적해가 부분 문제의 최적해들로 조합될 경우 최적의 부분 구조를 갖고 있다고 한다.

Greedy versus dynamic programming

탐욕적 방법과 동적 계획법을 비교할 수 있는 적절한 예로 배낭 문제가 있다. 0-1 배낭 문제는 각각 무게 w_{i}, 가치 v_{i}를 가진 물건 n개를 무게 제한 W의 배낭에 담아서 가치를 최대화시키는 문제이다. 분수 배낭 문제는 0-1 배낭 문제와 같지만 물건을 특정 비율만큼 담을 수 있다. 둘 모두 최적의 부분 구조를 갖고 있지만, 분수 배낭 문제는 탐욕적 방법으로 풀 수 있고 0-1 배낭 문제는 탐욕적 방법으로 풀 수 없다. 동적 계획법은 가능하다.

16.3. Huffman codes

허프만 코드는 데이터를 효율적으로 압축하는 알고리즘으로, 각 문자가 등장하는 빈도를 세어서 이진 문자 코드를 구성하여 가장 효율적인 압축을 고안한다. 이 문자 코드 내에서는 각 문자가 유일한 이진 문자열인 코드워드로 표현되며, 이는 고정 길이 코드일 수도 있고 가변 길이 코드일 수도 있다.

Prefix codes

여기서 고려할 코드는 전치사 코드로, 어떠한 코드워드가 다른 코드워드의 전치사가 되지 않는 코드를 고려한다. 이는 최적의 데이터 압축을 보장하며, 복호화하는 과정에서 각 문자의 코드워드에 대한 구별 불가능성이 없다. 대개 각 문자를 리프로 갖는 이진 트리로 나타내어진다. 이 때 파일을 인코딩하기 위한 비트의 수는 다음과 같다.

B(T) = \sum_{c \in C} c.freq \cdot d_{T}(c)

이를 트리 T의 비용이라 한다.

Constructing a Huffman code

최적의 전치사 코드인 허프만 코드를 구성하는 탐욕적 알고리즘이 존재한다. 이는 다음과 같다.

HUFFMAN(C)
n = |C|
Q = C
for i = 1 to n - 1
    allocate a new node z
    z.left = x = EXTRACT-MIN(Q)
    z.right = y = EXTRACT-MIN(Q)
    z.freq = x.freq + y.freq
    INSERT(Q, z)
return EXTRACT-MIN(Q)

총 수행 시간은 O(n \lg n)이다.

Correctness of Huffman’s algorithm

허프만 알고리즘의 정당성은 다음과 같이 증명된다.

Lemma. 알파벳 C 내의 문자 각각 c가 c.freq의 빈도로 등장한다고 하자. x, y가 C 내에서 가장 최소 빈도로 등장하는 두 문자라 할 때, x, y가 마지막 비트만 다른 같은 길이의 코드워드가 되는 C의 최적 전치사 코드가 존재한다.

Lemma. 알파벳 C 내의 문자 각각 c가 c.freq의 빈도로 등장한다고 하자. x, y가 C 내에서 가장 최소 빈도로 등장하는 두 문자라 할 때, C’를 C에서 x, y를 없애고 새 문자 z를 추가한 알파벳이라 하자. C’에 대한 f를 C와 같이 정의하되, z.freq = x.freq + y.freq로 정의하자. T’를 C’의 최적 전치사 코드를 나타내는 트리라 할 때, T’에서 노드 z를 자식 노드 x, y를 가진 내부 노드로 대체한 트리 T는 C의 최적 전치사 코드를 나타낸다.

Theorem. HUFFMAN은 최적의 전치사 코드를 구성한다.

16.4. Matroids and greedy methods

Matroids

매트로이드는 다음 조건을 만족하는 순서쌍 M = (S, I)이다.

  1. S는 유한집합이다.
  2. I는 S의 부분집합들의 공집합이 아닌 집합으로, S의 독립 부분집합이라 불리며 다음 조건을 만족한다. B \in I이고 A \subseteq B이면 A \in I. 이 때 I를 세습적이라 한다. 공집합은 I에 반드시 속한다.
  3. A \in I, B \in I, \lvert A \rvert < \lvert B \rvert이면 어떠한 원소 x \in B - A가 존재해서 A \cup \{x\} \in I를 만족한다. 이 때 M이 교환 특성을 만족한다고 한다.

이 이름은 행렬 매트로이드로부터 유래되었다. 비방향그래프로 G = (V, E)부터 유도되는 그래프 매트로이드 M_{G} = (S_{G}, I_{G})도 있다.

  • S_{G}는 G의 간선의 집합 E이다.
  • A가 E의 부분집합이면, A가 비순환인 것과 A \in I_{G}임은 동치이다. 즉, G_{A} = (V, A)가 숲인 것과 A가 독립인 것은 동치이다.

Theorem. G = (V, E)가 비방향그래프이면, M_{G} = (S_{G}, I_{G})는 매트로이드이다.

매트로이드 M = (S, I)에 대해, x \notin AA \in I에 추가했을 때에도 독립이 유지되면 x를 A의 확장이라 한다. 매트로이드 M의 독립부분집합 A가 확장이 없으면 최대라고 한다.

Theorem. 매트로이드의 모든 최대 독립 부분집합의 크기는 같다.

그래프 매트로이드의 경우 신장 트리가 된다. 매트로이드 M = (S, I)가 S 내의 모든 원소 x에 대해 양의 가중치가 부여된 경우 가중이라 한다.

Greedy algorithms on a weighted matroid

탐욕적 접근법은 가중 매트로이드에서의 최대 가중치 독립 부분집합, 즉 최적 부분집합을 찾는 것으로 치환될 수 있다. 예를 들면 최소 신장 트리 문제 등이 그렇다. 일반화하면 다음과 같다.

GREEDY(M, w)
A = Φ
sort M.S into monotonically decreasing order by weight w
for each x ∈ M.S, taken in monotonically decreasing order by weight w(x)
    if A ∪ {x} ∈ M.I
        A = A ∪ {x}
return A

수행 시간은 O(n \lg n + nf(n))이다. (f(n)은 집합의 독립성 여부를 체크하는 시간)

Lemma. M = (S, I)가 가중치 w가 부여된 가중 매트로이드로 S는 가중치가 단조감소하는 순서로 정렬되어 있다고 하자. x가 {x}가 독립이 되는 S의 첫 번째 원소라 하자. 그런 x가 존재한다면, x를 포함하는 S의 최적 부분집합 A가 존재한다.

Lemma. M = (S, I)가 매트로이드라 할 때, S 내의 독립부분집합 A에 대해 S의 원소 x가 A의 확장이 된다면, x는 공집합의 확장도 된다.

Corollary. M = (S, I)가 매트로이드라 할 때, S의 원소 x가 공집합의 확장이 되지 않는다면, x는 S의 어떤 독립부분집합에 대해서도 그 집합의 확장이 될 수 없다.

Lemma. 가중 매트로이드 M = (S, I)에 대해 x를 GREEDY에 의해 S에서 선택된 첫 번째 원소라 하자. x를 포함하는 최대 가중치 독립 집합을 찾는 문제는 가중 매트로이드 M'=(S', I')의 최대 가중치 독립 집합을 찾는 문제와 같다. (S’는 \{x, y\} \in Iy \in S의 집합, I’는 B \cup \{x\} \in IB \subseteq S - \{x\}의 집합, M’에 부여된 가중치는 M에 부여된 가중치와 같음) 이 때 M’을 x에 대한 M의 수축이라 한다.

Theorem. M = (S, I)가 가중치 w가 부여된 매트로이드라 할 때, GREEDY(M, w)는 최적의 부분집합을 반환한다.

16.5. A task-scheduling problem as a matroid

작업 스케쥴링 문제도 매트로이드 이론으로 풀 수 있다. 단위 시간이 걸리는 작업을 단위 시간 작업이라 하고, 단위 시간 작업의 집합 S에 대해 S의 스케쥴을 S 내의 작업들의 순열이라 하자. 단일 프로세서에 패널티와 데드라인이 있는 단위 시간 작업 스케쥴링 문제는 다음과 같다.

  • S = \{a_{1}, \cdots, a_{n}\}는 n개의 단위 시간 작업이다.
  • 작업에 대해한 n개의 정수 데드라인 d_{1}, \cdots, d_{n}이 존재한다.
  • 데드라인을 맞추지 못했을 때의 패널티 w_{1}, \cdots, w_{n}이 존재한다.

이 때 패널티를 최소로 하는 S의 순열을 찾는 문제이다.

스케쥴에 대해 각 작업이 데드라인에 맞췄을 경우 일찍 끝났다고 하고, 이외에는 늦게 끝났다고 하자. 이 때 임의의 스케쥴을 일찍-우선 형태로 변환할 수 있다. 그리고 자연 형태로도 변환할 수 있다. 이 때 작업의 부분집합 A에서 A 내의 작업들이 단 하나도 늦게 끝나지 않게 하는 스케쥴이 존재할 경우 A를 독립이라 하자.

Lemma. 작업의 집합 A에 대해, 다음의 명제들은 동치이다.

  • A는 독립이다.
  • 각 t에 대해, N_{t}(A) \leq t이다.
  • A 내의 작업들이 데드라인이 단조증가하는 순서대로 스케쥴되어 있다면, 작업들이 늦게 끝나지 않는다.

Theorem. S가 단위 시간 작업의 집합으로 데드라인이 존재하고, I가 독립적인 작업의 집합들의 집합이라면, (S, I)는 매트로이드이다.

이를 이용해서 O(n^{2}) 시간에 스케쥴링을 할 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중