References
- Algorithms (Sanjoy Dasgupta)
Contents
- Set Cover (집합 커버) 문제
- Approximation Factor
위 이미지에서 점들은 마을을 표현합니다. 여기서 학교를 어디에 배치할 것인가 결정하는데, 두 가지 제한 사항이 있습니다. 각 학교는 마을 내에 위치해야 하고, 학교는 어떤 마을에서도 30마일보다 가까운 곳에 위치해야 합니다. 이 경우 필요한 학교의 최소 갯수는 몇 개 일까요?
이 문제는 전형적인 집합 커버(set cover) 문제입니다. 각 마을 x에 대해, \(S_x\)는 30마일 이내에 있는 마을들의 집합이라고 합시다. x에 있는 학교는 기본적으로 이 집합의 다른 마을들을 커버(cover)합니다. 이때 문제는 '얼마나 많은 집합 \(S_x\)가 있는가?' 입니다.
Set Cover의 입력과 출력은 다음과 같습니다.
- Input: 요소들 B의 집합. \(S_1, \cdots, \S_m \subseteq B\)
- Output: 합집합이 B가 되는 \(S_i\)의 선택
이 예제에서 B의 요소들은 마을들을 의미합니다. 그리고 이 문제는 다음과 같이 그리디한 방법으로 해결할 수 있습니다.
- B의 모든 요소들이 커버될 때까지 다음을 반복: 커버되지 않는 가장 많은 수의 요소들을 가진 \(S_i\)를 뽑는다.
이는 매우 자연적이면서 직관적입니다. 이 예제에서 무엇을 할 수 있는지 살펴보겠습니다.
마을 a에 첫 번째로 학교를 배치합니다. a 위치에 배치하는 것이 가장 많은 다른 마을들을 커버합니다. 그런 다음, c, j, 그리고 f나 g를 선택하여 3개의 학교를 더 선택하면, 총 4개의 학교를 선택하게 됩니다. 하지만 이 예제의 솔루션에는 b, e, j를 선택하면 총 3개의 학교를 선택하는 것이 있습니다. 즉, 그리디한 방법이 최적의 솔루션을 찾지 못하고 있습니다.
하지만 다행히 최적의 솔루션과 그리 멀지는 않습니다.
Claim: B가 n개의 요소들을 포함하고, 최적의 커버가 k개의 집합들로 구성된다고 가정하면, 그리디 알고리즘은 최대 \(k\ln n\)개의 집합들을 사용하게 될 것이다.
\(n_t\)는 그리디 알고리즘을 t번 반복 후에 아직까지 커버되지 않은 요소들의 개수라고 가정해봅시다. 남아 있는 요소들은 최적의 k개의 집합들에 의해 커버되기 때문에, 이들 중에는 적어도 \(\frac{n_t}{k}\)개의 요소를 갖는 어떤 집합이 되어야 합니다. 따라서 그리디 전략은 다음 공식을 보장합니다.
\[n_{t+1} \leq n_t - \frac{n_t}{k} = n_t (1 - \frac{1}{k})\]
여기서 위 식은 \(n_t \leq n_0 (1 - \frac{1}{k})^t\)임을 의미합니다.
그리고, 아래의 부등식을 통해서 최적해의 경계를 얻을 수 있습니다.
- 모든 x에 대해 \(1-x \leq e^{-x}\)이며, 필요충분 조건으로 x = 0이면 \(1-x = e^{-x}\)이다.
위 식은 아래의 그래프에 의해서 쉽게 증명됩니다.
따라서, 다음의 식이 만족합니다.
\[n_t \leq n_0(1-\frac{1}{k})^t < n_0 (e^{-\frac{1}{k}})^t = ne^{-\frac{1}{k}}\]
그러므로 \(t = k\ln n\)에서 \(n_t\)는 \(ne^{-\ln n} = 1\)보다 엄격하게 작으며, 이는 커버되어지는 요소가 하나도 남아 있지 않음을 의미합니다.
그리디 알고리즘의 솔루션과 최적해 간의 비율(ratio)은 입력에 따라 다르지만, 항상 \(\ln n\)보다는 작습니다. 그리고 이 비율이 \(\ln n\)과 매우 근접하는 특정 입력들이 존재합니다. 여기서 가장 큰 비율을 그리디 알고리즘의 근사 계수(approximation factor)라고 부릅니다.
개선의 여지가 많은 것처럼 보이지만, 사실 이와 같은 희망은 근거가 없습니다. 또한 알려진 복잡한 가정 하에서, 더 작은 근사 계수를 갖는 다항 시간 알고리즘이 없는 것으로 아마도 없을 것입니다.
이 문제는 단순히 결정하는 경우에는 NP-Complete, 최적해를 구하는 문제인 경우에는 NP-Hard에 속합니다.
댓글