약간 발칙한 상상을 해봅시다. 여러분은 도둑이고 고가의 귀중품을 훔치기 위해 한 가게에 들어와 있습니다. 여러분의 눈앞에는 보기만 해도 휘황찬란한 물건들이 진열되어 있습니다. 당연히 모두 챙길 수 있다면 가장 좋을 겁니다. 하지만 이 물건들을 들고 가는 방법은 오직 여러분의 등에 매달린 배낭을 사용하는 것 뿐입니다. 배낭에는 최대로 견딜 수 있는 하중이 정해져 있고, 이를 초과하여 물건을 담는다면 배낭이 찢어져 버립니다. 배낭을 못 쓰게 된다면 손에 몇 개 쥐고 나오는 것 밖에는 방법이 없으니 큰 손해임이 분명합니다. 따라서 여러분의 목표는 배낭이 찢어지지 않을 정도의 무게로 가장 가치있는 물건들을 선택하는 것이 되겠죠.
이 문제가 바로 잘 알려진 NP-난해(NP-hard) 문제 중 하나인 배낭 문제(knapsack problem)입니다. 이 문제를 좀더 엄밀히 정의하자면 다음과 같습니다. 문제의 입력으로는 물건의 집합 \(I\)와 배낭이 견딜 수 있는 최대 하중 \(B\)가 주어집니다. 각 물건 \(i \in I\)에 대해서는 물건의 무게 \(w_i \in \mathbb{Q}_+\)와 가치 \(v_i \in \mathbb{Q}_+\)도 함께 주어집니다. 우리의 목표는 총 무게가 \(B\)를 넘지 않으면서 최대의 가치를 갖도록 물건을 선택하는 것입니다. 다시 말해, \[ \sum_{i \in S} w_i \leq B \]를 만족하면서 \[ v(S) := \sum_{i \in S} v_i \]가 최대인 \(S \subseteq I\)를 구하는 것이죠.
이 문제는 NP-난해라고 하였으므로, 아무래도 다항 시간에 이 문제를 해결하기는 매우 어렵습니다. 따라서 이를 근사적으로 해결하는 방법에 대해서 알아봐야 하겠죠. 이제부터 몇 가지 아이디어를 제시하고 이것들이 좋은 해결책이 될 것인지 분석해보겠습니다.
첫 번째 아이디어는 어차피 우리의 목표가 최대 가치를 갖도록 하는 것이므로, 가치가 큰 물건부터 순서대로 고르는 것입니다.
알고리즘 1. Greedy choice in descending order of values
입력: 물건의 집합 \(I\), 최대 하중 \(B\)
출력: 최대 하중을 만족하는 물건의 부분집합
- \(S \gets \emptyset \)
- \(I\)가 빌 때까지 다음을 반복한다.
- 현재 \(I\)에서 가치가 가장 큰 물건을 \(i\)라고 하자.
- 만약 \(S \cup \{ i \}\)의 총 무게가 \(B\)를 넘지 않으면, \( S \gets S \cup \{i\} \)
- \(I \gets I \setminus \{ i \}\)
- \(S\)를 반환한다.
안타깝게도 이 방법으로는 항상 좋은 근사해를 구하지는 못합니다. 여러분이 다음 표와 같이 물건을 갖고 있다고 해보죠. 표의 첫 번째 행은 물건의 이름을, 두 번째 행은 무게를, 마지막 행은 가치를 나타냅니다. 배낭의 최대 하중은 8이라고 합시다.
| \(I\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| \(w_i\) | 8 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| \(v_i\) | 1.001 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
총 무게가 8을 넘지 않으면서 가장 가치있게 담는 방법은 \( \mathsf{OPT} = \{ 1, 2, \cdots, 8 \} \)입니다. 그러면 총 8의 가치를 얻을 수 있죠. 하지만 알고리즘 1은 가장 가치 있는 0번 물건을 가장 먼저 고를 것입니다. 문제는 그 물건의 무게가 이미 8이라서 더 이상 물건을 담을 수 없다는 것이죠. 따라서 \( \frac{v(S)}{v(\mathsf{OPT})} \approx \frac{1}{8} \)이 됩니다.
이를 확장하면 쉽게 알고리즘 1을 망치는 입력을 만들 수 있습니다. 배낭의 최대 하중을 어떤 양의 정수 \(B\)라고 했을 때, 총 \(B+1\) 개의 물건이 있고, 하나의 물건만 무게가 \(B\), 가치가 \(1 + \epsilon\)(단, \(\epsilon\)은 매우 작은 양수), 나머지는 모두 무게가 \(1\), 가치도 \(1\)이라고 합시다. 그러면 최적해는 가치가 \(1\)인 물건 \(B\)개를 모두 고르는 것이므로 \( v(\mathsf{OPT}) = B \)가 됩니다. 하지만, 알고리즘 1은 가치가 \(1 + \epsilon\)인 물건을 하나 고르고 끝날 것이므로 \( v(S) = 1 + \epsilon \)이 되겠죠. 따라서 \(B\)가 커질수록, \[\frac{v(S)}{v(\mathsf{OPT})} = \frac{1 + \epsilon}{B} \rightarrow 0\]이 됩니다.
알고리즘 1의 멍청한 점은 무엇일까요? 네, 바로 가성비를 생각하지 않았다는 점입니다. 아무리 가치가 많이 나가더라도 무게가 엄청 크면 당연히 효율이 좋지 않을 겁니다. 이를 토대로 다음과 같이 가성비를 먼저 생각하는 알고리즘을 고안할 수 있습니다.
알고리즘 2. Greedy choice in descending order of value-weight ratios
입력: 물건의 집합 \(I\), 최대 하중 \(B\)
출력: 최대 하중을 만족하는 물건의 부분집합
- \(S \gets \emptyset \)
- \(I\)가 빌 때까지 다음을 반복한다.
- 현재 \(I\)에서 가성비가 가장 좋은 물건을 \(i\)라고 하자. 즉, \( \frac{v_i}{w_i} \)가 가장 큰 물건을 가지고 온다.
- 만약 \(S \cup \{ i \}\)의 총 무게가 \(B\)를 넘지 않으면, \( S \gets S \cup \{i\} \)
- \(I \gets I \setminus \{ i \}\)
- \(S\)를 반환한다.
과연 이 알고리즘은 좋은 성능을 보일까요? 안타깝게도 이 알고리즘 또한 특정 입력에 대해서는 좋지 않은 결과를 반환합니다. 가방의 최대 하중을 100이라고 합시다. 물건은 다음과 같이 두 개가 주어진다고 합시다.
| \(I\) | 1 | 2 |
| \(w_i\) | 100 | 1 |
| \(v_i\) | 100 | 1.001 |
| \(v_i / w_i\) | 1 | 1.001 |
당연히 최적해는 1 번 물건을 고르는 것입니다. 가치가 100이니까요. 하지만 재밌게도 가성비는 2번이 약간 더 좋습니다. 따라서 알고리즘 2는 2번 물건을 먼저 고를 겁니다. 문제는 가방의 최대 하중이 100이기 때문에 2번을 고르면 1번을 더 이상 고를 수 없다는 점입니다. 따라서 \( \frac{v(S)}{v(\mathsf{OPT})} \approx \frac{1}{100} \)이 됩니다.
위 경우와 비슷하게 이를 확장하면 알고리즘 2를 망가뜨리는 입력을 만들 수 있습니다. 최대 하중 \(B\)에 대해서 \(w_1 = v_1 = B\)인 물건과 \(w_2 = 1, v_2 = 1 + \epsilon\)인 물건이 입력으로 들어온다면, 최적해는 1번 물건을 고르는 것이지만 알고리즘 2는 2번 물건을 고르고 알고리즘을 종료할 것입니다. 따라서 \(B\)의 값이 커질수록, \[ \frac{v(S)}{v(\mathsf{OPT})} = \frac{1 + \epsilon}{B} \rightarrow 0 \]임을 알 수 있습니다.
알고리즘 2가 좋은 결과를 주지 못한 이유는 또 무엇일까요? 아무리 가성비를 따지더라도 그 물건 자체의 가치가 작으면 큰 도움이 되지 않기 때문이죠. 나아가 소소한 물건을 주워담다 보면 어느샌가 배낭에 가치가 큰 물건을 넣을 공간이 없어지게 될 겁니다.
이를 통해 알 수 있는 사실은 바로 알고리즘 1과 알고리즘 2가 상호보완적이라는 것입니다. 가치가 좋은 것만 계속 추구했다가는 무게가 남아나지 않을 수 있고, 반대로 극한으로 가성비만을 좇는다면 큰 가치를 수집하지 못할 것입니다. 따라서 이 둘을 적절히 섞어줍시다. 어떻게요? 그냥 둘 다 돌리고, 둘 중 더 좋은 것을 출력해 봅시다.
알고리즘 3. A 0.5-approximation algorithm for the knapsack problem
입력: 물건의 집합 \(I\), 최대 하중 \(B\)
출력: 최대 하중을 만족하는 물건의 부분집합
- 같은 입력으로 알고리즘 1을 수행한 후 얻은 결과를 \(S_1\)이라고 하자.
- 같은 입력으로 알고리즘 2를 수행한 후 얻은 결과를 \(S_2\)라고 하자.
- \(S_1\)과 \(S_2\) 중 총 가치가 더 높은 쪽을 출력한다.
이 알고리즘이 최대 하중을 만족하는 올바른 답을 출력한다는 것은 쉽게 알 수 있습니다. 알고리즘 1과 알고리즘 2가 출력하는 결과가 모두 최대 하중을 만족하기 때문이죠. 따라서, \(S_1\)의 총 가치나 \(S_2\)의 총 가치 중 적어도 하나는 반드시 최적해의 총 가치의 절반보다 크거나 같다는 것을 보일 수 있다면 이 알고리즘이 0.5-근사 알고리즘이라는 것을 보일 수 있게 됩니다.
이를 증명하기 위해서는 약간 변형된 문제를 생각해야 합니다. 이 문제에서는 우리에게 좀더 많은 자유가 있습니다. 바로, 물건을 떼어내서 가방에 넣을 수 있는 것입니다. 이때 떼어낸 양에 비례하여 가치도 정해지게 됩니다. 예를 들어, 가치가 100, 무게가 100인 물건이 있을 때, 이 물건의 60% 만큼을 떼어내 가방에 넣으면 가치는 60이 되고 동시에 무게도 60이 되는 것이죠. 이 문제도 유명한 배낭 문제의 변형 중 하나로, 분수 배낭 문제(fractional knapsack problem)으로 불립니다. 참고로 분수 배낭 문제와 구분하기 위해서 물건을 쪼갤 수 없는 위 문제를 0-1 배낭 문제(0-1 knapsack problem)으로 부르기도 합니다.
한 가지 중요한 사실 중 하나는, 분수 배낭 문제의 최적해의 가치는 항상 원래 배낭 문제의 최적해의 가치보다 나쁘지 않다는 것입니다. 다시 말해, 같은 입력에 대해, 분수 배낭 문제의 최적해를 \( \mathsf{OPT}_\mathsf{frac} \), 원래 문제의 최적해를 \( \mathsf{OPT}_\mathsf{int} \)라고 하였을 때, 항상 \[ v(\mathsf{OPT}_\mathsf{frac}) \geq v(\mathsf{OPT}_\mathsf{int}) \tag{1}\]를 만족합니다. 그 이유는 간단합니다. 원래 문제를 만족하는 모든 해는 분수 배낭 문제의 가능한 해이기도 하기 때문입니다. 원래 배낭 문제보다 더 많은 자유가 있는 분수 배낭 문제이니 당연한 귀결이죠.
그러면 분수 배낭 문제는 어떻게 해결할 수 있을까요? 이 경우에는 가성비만 따지면 됩니다. 즉 알고리즘 2처럼 동작시키되 어느 순간 배낭에 물건을 온전히 넣을 수 없는 때가 오면 남은 무게만큼 물건을 떼어내서 채우는 것이죠. 이렇게 선택하는 것이 최적인 이유는 어찌보면 당연합니다. 만약 가성비가 떨어지는 물건의 부분이 배낭에 들어가 있고, 가성비가 그보다 좋은 물건의 부분이 아직 들어가지 않은 상태라면, 같은 무게만큼 떼어내서 서로 바꿔치기하면 가치가 더 증가하게 되기 때문입니다.
따라서 위 방법을 통해 온전히 들어간 물건의 가치를 각각 \(v_1, \cdots, v_k\)라고 하고, 마지막에 잘려서 들어간 물건의 원래 온전한 가치를 \(v_{k + 1}\)이라고 한다면, 우리는 \[ \sum_{i = 1}^k v_i + v_{k + 1} \geq v(\mathsf{OPT}_\mathsf{frac}) \tag{2} \]이라는 사실을 알 수 있습니다. 흥미로운 사실은 물건이 온전히 들어갈 때까지는 알고리즘 2와 동일하다는 것입니다. 즉, \[ v(S_2) = \sum_{i = 1}^k v_i \]라는 사실을 얻을 수 있습니다. 그러면 \(v_{k + 1}\)은 어떻게 처리할까요? 바로 알고리즘 1을 통해서입니다. 알고리즘 1은 가치가 큰 물건부터 순서대로 배낭에 넣기 때문에 분명 가치가 가장 큰 물건이 들어갈 것입니다. 그러므로, \[ v(S_1) \geq v_{k + 1} \]은 자명한 사실이 됩니다. 이 두 식을 식 2에 적용하면 \[ v(S_1) + v(S_2) \geq v(\mathsf{OPT}_\mathsf{frac}) \]이라는 사실을 얻게 되고, 식 1과 함께 \[ v(S_1) + v(S_2) \geq v(\mathsf{OPT}_\mathsf{int}) \]도 이끌어낼 수 있습니다. 따라서, \(S_1\)과 \(S_2\) 중 적어도 하나는 가치가 \( \frac{1}{2} v(\mathsf{OPT}_\mathsf{int})\)보다 크거나 같게 됩니다.
지금까지 유명한 NP-난해 문제 중 하나인 배낭 문제에 대해서 알아보고, 이를 근사적으로 해결하는 방법에 대해서 공부하였습니다. 구체적으로 어떤 입력이 주어지더라도 최적해의 가치의 절반 이상의 가치를 갖는 결과를 출력하는 알고리즘을 소개하고, 그것이 어째서 0.5의 근사비를 가질 수 있는지도 함께 보였습니다.
과연 더 잘 할 수 있을까요? 일단 이 알고리즘으로는 불가능합니다. 다음의 예제를 고려해 봅시다. 배낭의 최대 하중은 2입니다. 매우 작은 양수 \(\epsilon\)에 대해, 물건은 다음과 같이 총 세 개가 주어집니다.
| \(I\) | \(1\) | \(2\) | \(3\) |
| \(w_i\) | \(1 + \epsilon\) | \(1\) | \(1\) |
| \(v_i\) | \(1 + \epsilon\) | \(1 - \epsilon\) | \(1 - \epsilon\) |
| \(v_i / w_i\) | \(1\) | \(1 - \epsilon\) | \(1 - \epsilon\) |
이러면 알고리즘 1이든 알고리즘 2든 1번 물건을 먼저 선택하게 됩니다. 하지만 배낭의 최대 하중 때문에 1번 물건을 선택하면 더이상 물건을 배낭에 넣을 수 없습니다. 따라서 두 알고리즘 모두 가치가 \(1 + \epsilon\)인 결과를 출력하게 됩니다. 하지만 최적해는 2번 물건과 3번 물건을 동시에 담는 것으로 가치가 \( 2 - 2\epsilon \)이 됩니다. 따라서 매우 작은 \( \epsilon\)에 대해서 알고리즘 3의 근사비는 \( \frac{1}{2} \)에 수렴하게 됩니다.
그러면 방법은 더이상 없는 걸까요? 그렇지 않습니다. 놀랍게도 원하는 정확도 \(\epsilon\)에 대해서 \(1-\epsilon\)의 근사비를 갖는 결과를 출력하는 알고리즘을 만들 수 있습니다. 이러한 알고리즘을 다항 시간 근사 해법(polynomial-time approximation scheme, PTAS)이라고 부릅니다. 이 방법에 관한 좀더 자세한 내용은 다음 포스트에서 정리해 보도록 하겠습니다.
글에 잘못된 점이 있거나 궁금하신 점이 있으시면 알려주시기 바랍니다. 고맙습니다.
참조
[1] 전체적인 내용 : https://courses.cs.cornell.edu/cs4820/2018fa/lectures/approx-onlinet.pdf
'근사 알고리즘 > Knapsack' 카테고리의 다른 글
| [배낭문제 / Knapsack Problem] 다항 시간 근사 해법 (PTAS) (0) | 2020.06.19 |
|---|
