지난 포스트에서는 유명한 NP-난해(NP-hard) 문제 중 하나인 배낭 문제(knapsack problem)에 대해서 공부하였습니다. 어떤 문제인지 다시 정의하자면, 우리에게는 물건의 집합 \(I = \{1, \cdots, n\}\)와 배낭의 최대 하중 \(B \in \mathbb{Z}_+ \)가 주어집니다. 각각의 물건 \(i \in I\)에도 무게 \(w_i \in \mathbb{Z}_+\)와 가치 \( v_i \in \mathbb{Z}_+\)가 함께 주어집니다. 여기서 지난 시간과는 달리, 입력으로 주어지는 값 \(Z, w_i, v_i\) 모두가 (음이 아닌) 정수라는 가정을 하도록 하겠습니다.[ㄱ] 또한 어차피 무게가 \(B\)를 넘으면 가방에 담을 수도 없으니 무게가 \(B\)를 넘는 물건은 없다고 가정하겠습니다. 우리는 물건을 쪼개서 배낭에 담을 수는 없습니다. 온전히 넣든지 아니면 넣지 않든지 해야 합니다. 이런 상황에서 우리의 목표는 배낭의 최대 하중을 만족하면서 최대의 가치를 갖도록 물건을 선택하는 것입니다. 다시 말해, \(\sum_{i \in S} w_i \leq B\)를 만족하면서 \( \sum_{i \in S} v_i \)가 최대가 되도록 하는 \(S \subseteq I\)를 찾는 것입니다.
이 문제를 해결하는 0.5-근사 알고리즘에 대해서도 지난 시간에 함께 알아보았습니다. 각각 최대 무게와 가성비를 기준으로 가장 좋은 것만 계속 선택하는 탐욕 알고리즘(greedy algorithm) 두 개를 수행한 후 둘 중 더 좋은 결과를 출력하는 알고리즘이었습니다. 안타깝지만 이 알고리즘이 더 좋은 근사비를 가질 수 없다는 것도 함께 보였습니다. 그러면 컴퓨터과학도로서 자연스럽게 다음의 질문이 떠오를 겁니다. 더 잘 할 수 있을까요? 네, 잘 할 수 있습니다. 더 놀라운 점은 엄청 잘 할 수 있다는 것입니다. 이번 시간에는 이에 대해 알아보도록 하겠습니다.
동적 계획법으로 정확하게 풀기
엄청 좋은 근사 알고리즘을 곧장 공부하기 전에, 이 알고리즘을 정확하게 해결하는 방법에 대해서 먼저 알아보도록 하죠. 바로 동적 계획법(dynamic programming)을 활용하는 것입니다. 이 방법은 매우 유명하여, 아마 알고리즘 수업을 들으셨던 분이라면 이 방법을 가물가물하게나마 기억하실 겁니다. 이 글에서는 동적 계획법이 어떤 것인지에 대해서는 설명하지 않겠습니다. 이를 잘 모르신다면, 이를 먼저 숙지하시고 아래를 읽으시는 것을 추천드립니다.
대개는 물건의 부분집합과 최대 하중을 기준으로 점화식을 작성하지만, 이번 시간에는 약간 다르게 정의해보도록 하겠습니다. 바로 물건의 부분집합과 이룰 수 있는 총 가치를 기준으로 작성하는 것이죠. 모든 물건의 가치를 더한 것을 \(V := \sum_{i \in I} v_i\)라고 하겠습니다. 그리고, \(i = 0, \cdots, n\), \(v = 0, \cdots, V\)에 대해 \( \mathsf{OPT}(i, v) \)를 \( \{1, \cdots, i\} \)의 물건만을 가지고 총 가치가 정확히 \(v\)가 되도록 물건을 선택하는 방법이 이룰 수 있는 가장 작은 총 무게로 정의하겠습니다. 만약 해당 물건만 가지고는 \(v\)의 가치를 이룰 수 없다면 \( \mathsf{OPT}(i, v) = \infty \)로 설정하겠습니다. 그러면 우리는 다음과 같은 점화식을 얻을 수 있습니다.
정리 1. 동적 계획법 점화식
임의의 \(i = 0, \cdots, n\)과 \(v = 0, \cdots, V\)에 대해서, \[ \mathsf{OPT}(i, v) = \left\{ \begin{array}{ll} 0, & \text{if } v = 0,\\ \infty, & \text{if } i = 0, v > 0,\\ \min\{ \mathsf{OPT}(i - 1, v), \mathsf{OPT}(i - 1, v - v_i) + w_i \}, & \text{otherwise.} \end{array} \right. \]를 만족한다.
[증명] 만약 \(v = 0\)이라면, 아무것도 고르지 않는 것으로 총 가치 \(v = 0\)을 이룰 수 있으므로 \( \mathsf{OPT}(i, 0) = 0 \)이 됩니다. 또, 만약 \(i = 0\)인데, \(v > 0\)이라면 선택할 수 있는 물건이 없는데 0보다 큰 가치를 얻어야 하므로 \( \mathsf{OPT}(0, v) = \infty \)가 되는 것도 확인할 수 있습니다.
그외의 경우에 대해서 간단히 증명하겠습니다. 물건을 \(1, \cdots, i\)까지 고려하면서 총 가치를 정확히 \(v\)로 만들기 위해서는
- \(1, \cdots, i - 1\)까지 고려하여 총 가치를 정확히 \(v\)로 만드는 방법을 그대로 가지고 온 후 물건 \(i\)은 선택하지 않는 방법, 혹은
- \(1, \cdots, i - 1\)까지 고려하여 총 가치를 정확히 \(v - v_i\)로 만드는 방법을 가지고 온 후 물건 \(i\)를 선택하는 방법,
이렇게 두 가지 중 하나입니다. 우리의 목표는 가장 작은 총 무게를 구하는 것이므로 그중 더 작은 무게를 이루는 방법으로 선택하면 되겠습니다. □
이 점화식을 그대로 활용하면 우리가 원하는 동적 계획법의 알고리즘이 됩니다.
알고리즘 1. Exact algorithm by dynamic programming
입력: 물건의 집합 \(I = \{1, \cdots, n\}\) (각 물건 \(i \in I\)마다 무게 \(w_i \in \mathbb{Z}_+\)와 가치 \(v_i \in \mathbb{Z}_+\)), 배낭의 최대 하중 \(B \in \mathbb{Z}_+\)
출력: 최대 하중을 만족하는 \( S \subseteq I \)
- \(V \gets \sum_{i \in I} v_i \)
- \(M\)과 \(\mathsf{prev}\)를 \(n \times V\)의 2차원 배열로 둔다.
- \(M[i, 0] \gets 0, \quad \mathsf{prev}[i, 0] \gets \mathsf{start} \quad \forall i = 1, \cdots, n \)
- \(M[0, v] \gets \infty, \quad \mathsf{prev}[0, v] \gets \mathsf{null} \quad \forall v = 1, \cdots, V \)
- 모든 \(i = 1, \cdots, n\)에 대해서 다음을 수행한다.
- 모든 \(v = 1, \cdots, V\)에 대해 다음을 수행한다.
- \(M[i, v] \gets \min \{ M[i - 1, v], M[i - 1, v - v_i] + w_i \} \)
- 만약 \( M[i, v] = M[i - 1, v] \)이면, \( \mathsf{prev}[i, v] = (i-1,v) \)
- 반대로 만약 \( M[i, v] = M[i - 1, v - v_i] + w_i \)라면, \( \mathsf{prev}[i, v] = (i - 1, v - v_i) \)
- 모든 \(v = 1, \cdots, V\)에 대해 다음을 수행한다.
- \( M[n, v] \leq B \)를 만족하는 \(v\) 중 가장 큰 값을 \(v^\star\)라고 하자.
- \( S \gets \emptyset, (i, v) \gets (n, v^\star) \)
- \(\mathsf{prev}[i ,v] = \mathsf{start} \)가 될 때까지 아래를 반복한다.
- 만약 \( \mathsf{prev}[i, v] = (i - 1, v - v_i)\)이면, \(S \gets S \cup \{ i \}\)
- \( (i, v) \gets \mathsf{prev}[i, v] \)
- \(S\)를 반환한다.
이 알고리즘이 정확하게 동작한다는 것은 정리 1을 통해서 쉽게 보일 수 있습니다. 특히 \( \mathsf{prev} \)를 통해 역으로 찾아나가는 방법은 동적 계획법에서 최적해를 구할 때 흔히 사용하는 기법입니다.
의사 다항 시간 알고리즘
그렇다면 과연 이 알고리즘의 시간 복잡도는 어떻게 될까요? 2차원 배열의 크기가 \(n \times V\)이고, 각 항목을 상수 시간에 채워넣을 수 있으므로 알고리즘 1은 \( O(nV) \) 시간에 동작하게 됩니다. 얼핏 보기에는 다항 시간에 동작하는 것처럼 보이기는 합니다. 하지만 여기서 우리는 문제의 입력이 무엇이었는지를 잘 생각해야 합니다.
이 문제의 입력의 크기는 어느 정도일까요? 좀더 엄밀히 물어보도록 하겠습니다. 이 문제의 입력을 컴퓨터 메모리에 올린다고 가정했을 때 총 몇 개의 비트(bit)로 표현할 수 있을까요?
- 먼저, 물건의 개수가 몇 개인지 알아야 합니다. 이는 \(n\)이고, 이를 비트로 표현하면 총 \( O( \log n) \) 비트가 필요합니다.
- 다음은 배낭의 최대 하중 \(B\)를 표현해야 합니다. 이는 \( O( \log B) \) 비트면 충분히 가능합니다.
- 마지막으로 각 물건의 무게와 가치를 입력 받아야 합니다. 무게의 최댓값을 \(w_\mathsf{max}\), 가치의 최댓값을 \(v_\mathsf{max}\)라고 하였을 때, 각 물건의 무게와 가치는 \( O(\log w_\mathsf{max} + \log v_\mathsf{max}) \)의 비트가 필요하며, 따라서 모든 물건의 무게와 가치는 \( O(n \log w_\mathsf{max} + n \log v_\mathsf{max}) \)가 필요합니다.
따라서 문제의 입력은 총 \( O( \log n + \log B + n \log w_\mathsf{max} + n \log v_\mathsf{max}) \)의 비트로 표현할 수 있습니다. 여기서 무게의 최댓값은 \(B\)를 넘지 않는다고 가정했기에 \( w_\mathsf{max} \leq B \)를 얻을 수 있고, \(V\)는 모든 가치의 합이므로 \( v_\mathsf{max} \leq V \)도 쉽게 얻을 수 있습니다. 또한 \( \log n = O(n)\)이라는 사실도 자명합니다. 따라서 이를 정리하면 \( O(n (\log B + \log V)) \) 정도의 비트 수가 필요하다는 것을 알 수 있습니다.
여기서 \(B\)가 가질 수 있는 크기가 (크기는 하지만) 엄청 크지는 않다고 가정해 봅시다. 예를 들어, 64 비트 컴퓨터라면 \(B \leq 2^{64}\) 정도 되는 정수로 보는 것이죠. 그러면 \(\log_2 B \leq 64\) 정도 되므로 입력의 크기에서 제외하여 생각할 수 있습니다. 다시 말해, 입력의 크기가 \( O( n \log V ) \) 비트 정도 된다고 가정할 수 있는 것이죠. 이 가정이 그리 나쁘지는 않은 이유를 말씀드리겠습니다. 만약 \(B \gg 2^{64} \)인 엄청 무지막지하게 큰 정수라면 컴퓨터의 입장에서는 이를 표현하기 위해서 많은 양의 비트가 필요할 것입니다. 동시에 상수 시간에 동작할 수 있을 것이라고 가정한 덧셈이나 뺄셈과 같은 단순 작업(basic operation)도 더이상 간단히 할 수 있는 작업이 되지 않습니다.
지금까지 논의한 것을 종합해 보죠. 입력의 크기는 \( O(n \log V) \)인데 반해, 알고리즘의 수행 시간은 \( O(n V) \)입니다. \(V = 2^{\log V} \)이므로, 이를 통해 우리는 크기 대비 수행 시간이 지수적으로(exponentially) 증가한다는 것을 알 수 있습니다. 따라서 알고리즘 1은 엄밀히 말해 지수 시간 알고리즘입니다.
이렇게 겉으로 보기에는 다항 시간 알고리즘처럼 보이지만 실지로는 지수 시간에 동작하는 알고리즘들을 부르는 이름이 있습니다. 바로 의사 다항 시간 알고리즘(pseudopolynomial-time algorithm)입니다. 이 알고리즘들에 대해서 좀더 정확히 정의를 내리기 위해서는 문제의 입력을 다르게 표현해야 합니다. 우리가 사용하는 컴퓨터는 대개 이진법을 사용하므로 \(n\)의 값을 표현하기 위해서는 \( O(\log n) \) 정도의 비트가 필요했습니다. 그런데 만약 일진법(unary system)을 사용하는 컴퓨터라면 어떨까요? 이때는 \(n\)의 값을 표현하기 위해서 \( \Omega (n) \) 비트가 필요할 겁니다. 따라서 위 문제의 입력을 일진법으로 표현한다면 \( \Omega (n(B+V)) \) 정도의 비트가 필요하게 되고, 이는 알고리즘의 수행 시간인 \(O(nV)\)와 크게 차이가 나지 않게 됩니다. 이 성질을 토대로 의사 다항 시간 알고리즘을 정의할 수 있습니다.
정의 1. 의사 다항 시간 알고리즘(Pseudopolynomial-time algorithm)
어떤 문제의 입력을 일진법으로 표현(unary representation)하였을 때의 크기에 대한 다항 시간에 동작하는 알고리즘을 의사 다항 시간 알고리즘(pseudopolynmial-time algorithm)이라고 부른다.
입력 크기 줄이기
알고리즘 1이 다항 시간에 동작하지 않은 가장 근본적인 이유는 입력으로 주어지는 가치 \(v_i\)가 물건의 개수 \(n\)과 무관하기 때문입니다. 하지만, 만약 모든 \(v_i\)의 값을 \(n\)의 다항식으로 표현할 수 있다면, 알고리즘이 다항 시간에 동작한다고 말할 수 있게 될 것입니다. 예를 들어 \( v_\mathsf{max} = O(n) \)이라면, \(V := \sum_{i \in I} v_i = O(n^2)\)가 될 것이고, 그러면 알고리즘 1의 수행 시간이 \( O(nV) = O(n^3) \)이 됩니다.
어떻게 하면 모든 가치 \(v_i\)를 \(n\)의 다항식으로 표현할 수 있을까요? 방법은 간단합니다. 서로의 비율을 맞추면서 줄여버리는 것이죠. 예를 들어, 가치가 다음과 같이 각각 \[ 1623, 1577, 4255, 7623, 513, 9932, 3942, 7501, 8301, 10000 \tag{1} \]인 물건 열 개가 입력으로 들어왔다고 합시다. 여기서 가치의 최댓값 \(v_\mathsf{max} = 10000\)입니다. 물건의 개수는 \(10\)이니 가치의 최댓값을 \(10\)으로 맞춰 봅시다. 이를 위해서는 모든 가치를 \( 1000 \)으로 나누면 됩니다. 그러면 각 물건이 각각 \[ 1.623, 1.577, 4.255, 7.623, 0.513, 9.932, 3.942, 7.501, 8.301, 10 \]의 가치를 갖는다고 말할 수 있습니다. 하지만 이 값들은 정수가 아니라는 문제점이 있죠. 이를 해결하는 방법은 간단합니다. 다음과 같이 소수점 아래를 버려 버리면 됩니다. \[ 1, 1, 4, 7, 0, 9, 3, 7, 8, 10 \tag{2} \] 이렇게 하면 오차는 생길 수 있겠지만, 모든 가치 값이 정수이면서 그 최댓값이 물건의 개수에 비해 그리 크지 않은 새로운 입력이 된다는 것을 알 수 있습니다.
이번에는 \( 1000 \) 대신 \(100\)으로 나눈 후 소수점 아래를 버리도록 해봅시다. 그러면 \[ 16, 15, 42, 76, 5, 99, 39, 75, 83, 100 \tag{3} \]의 가치를 갖는 새로운 입력을 얻을 수 있습니다. 이는 수열 2보다 원래의 수열 1을 더 잘 표현한다는 것을 확인할 수 있습니다. 하지만 대신 가치의 최댓값이 기존보다 열 배 증가하게 되죠.
이 아이디어를 일반화하면 다음과 같습니다. 원래 입력에서의 각 물건 \(i \in I\)의 가치를 \(v_i\)라고 하고, 그중 가장 큰 값을 \(v_\mathsf{max}\)라고 하겠습니다. 제 목표는 \( \{v_i\}_{i \in I} \)에 (약간의 오차가 있는 상태로) 비례하면서 어떤 \(\epsilon > 0\)에 대해 \[ v^\prime_\mathsf{max} \leq \frac{1}{\epsilon} n \]가 되도록 하는 정수 \( \{ v^\prime_i \}_{i \in I} \)를 만드는 것입니다. 방법은 간단합니다. \[ \mu := \frac{\epsilon}{n} v_\mathsf{max} \]으로 정의한 후, \[ v^\prime_i := \left\lfloor \frac{v_i}{\mu} \right\rfloor \]를 취해주는 것입니다. 다음은 수의 버림에서 오는 간단한 사실을 보여줍니다.
정리 2. 만든 입력의 크기의 상한과 하한
임의의 입력에서 각 물건 \(i \in I\)의 가치를 \(v_i \in \mathbb{Z}_+ \)라고 하자. 모든 물건 \(i \in I\)에 대해 위 방식으로 얻은 \(v^\prime_i\)는 \[ \frac{v_i}{\mu} - 1 \leq v^\prime_i \leq \frac{v_i}{\mu}\]를 만족하는 정수의 값을 갖는다.
증명은 버림의 성질만 잘 사용하면 쉽게 구할 수 있으니 생략하도록 하겠습니다.
근사해 구하기
위 절에서 우리는 문제의 입력에서 가치의 크기를 물건의 개수의 다항식으로 줄이는 방법에 대해서 알아보았습니다. 이를 활용하면 다음의 알고리즘을 만들 수 있겠습니다. 어떤 작은 양수 \(\epsilon\)은 정해졌다고 하죠.
알고리즘 2. A polynomial-time approximation scheme for the knapsack problem
입력: 물건의 집합 \(I = \{1, \cdots, n\}\), 배낭의 최대 하중 \(B\)
출력: 최대 하중을 만족하는 \( S \subseteq I \)
- \( \mu \gets \frac{\epsilon}{n} v_\mathsf{max} \)
- \( v^\prime_i \gets \left\lfloor \frac{v_i}{\mu} \right\rfloor \quad \forall i \in I\)
- 무게와 최대 하중은 동일하되 가치는 \( \{v^\prime_i \}_{i \in I}\)인 입력에 대해 알고리즘 1을 수행하여 얻은 결과를 \(S\)라고 하자.
- \(S\)를 반환한다.
먼저 이 알고리즘의 출력이 올바르다는 것을 보이죠. 알고리즘 2에서는 각 물건마다 동일한 무게에 대해 알고리즘 1을 수행합니다. 알고리즘 1이 최대 하중을 만족하는 올바른 해를 출력한다는 것을 이미 알고 있으므로, 알고리즘 2의 출력도 자연스럽게 올바르다는 것을 입증할 수 있습니다.
다음은 이 알고리즘의 수행 시간을 분석해 봅시다. 단계 1과 2는 모두 \( O(n) \)의 시간에 가능합니다. 따라서 단계 3이 얼마큼의 시간을 사용하는지가 관건이죠. 단계 3에서 알고리즘 1에 입력되는 물건의 가치는 \( \{ v^\prime_i \}_{i \in I} \)입니다. 따라서 \( V^\prime := \sum_{i \in I} v^\prime_i \)라고 정의했을 때, 단계 3은 \( O(n V^\prime) \)의 시간을 소요하게 됩니다. 한편 수정된 가치의 최댓값은 \[ v^\prime_\mathsf{max} \leq \frac{v_\mathsf{max}}{\mu} = \frac{n}{\epsilon} \]을 만족하며, 따라서 \[ V^\prime \leq n v^\prime_\mathsf{max} \leq \frac{n^2}{\epsilon} \]이라는 사실을 알 수 있게 됩니다. 이를 활용하면 다음의 정리를 얻을 수 있습니다.
정리 3. 알고리즘 2의 시간 복잡도
임의의 \( \epsilon > 0 \)에 대해, 알고리즘 2는 \( O(\frac{n^3}{\epsilon}) \)에 동작한다.
마지막으로 증명할 것은 이 알고리즘이 적절한 근사해를 출력하는지입니다.
정리 4. 알고리즘 2의 근사성
원래 입력에서의 어떤 최적해를 \( O \)라고 하고, 알고리즘 2가 출력하는 결과를 \(S\)라고 하자. 그러면 \[ \sum_{i \in S} v_i \geq (1 - \epsilon) \sum_{i \in O} v_i \]를 만족한다.
[증명] 먼저, 정리 2에서 \( v^\prime_i \leq \frac{v_i}{\mu} \)에 의해, \[ \sum_{i \in S} v_i \geq \mu \sum_{i \in S} v^\prime_i \]를 이끌어낼 수 있습니다.
알고리즘 1은 항상 최적해를 출력합니다. 알고리즘 2에서 \( \{ v^\prime_i \}_{i \in I} \)에 대해 알고리즘 1을 수행하므로 \(S\)는 \( \{ v^\prime_i \}_{i \in I} \)를 가치로 갖는 입력에서는 최적해가 됩니다. 반대로 물건의 무게를 건들지는 않았으므로 \( O \)는 해당 입력에서 한 가지 가능한 해가 됩니다. 따라서, \[ \mu \sum_{i \in S} v^\prime_i \geq \mu \sum_{i \in O} v^\prime_i \]임을 이끌어낼 수 있습니다.
여기서, 이번에는 정리 2의 \( v^\prime_i \geq \frac{v_i}{\mu} - 1 \)을 통해, \[ \mu \sum_{i \in O} v^\prime_i \geq \mu \left[ \sum_{i \in O} \frac{v_i}{\mu} - |O| \right] = \sum_{i \in O} v_i - \mu |O| \]를 얻을 수 있습니다. 물건의 개수를 넘어서는 개수를 고를 수는 없으므로 \( |O| \leq n \)가 되고, 여기에 \(\mu\)의 정의를 함께 써주면 \[ \sum_{i \in O} v_i - \mu |O| \geq \sum_{i \in O} v_i - n \mu = \sum_{i \in O} v_i - \epsilon v_\mathsf{max}\]임을 알 수 있습니다.
원래 문제에서 \( v_\mathsf{max} \)의 가치를 갖는 물건 하나를 고르는 것도 한 가지 가능한 방법이므로 \( \sum_{i \in O} v_i \geq v_\mathsf{max} \)를 이끌어낼 수 있고, 이를 통해 \[ \sum_{i \in O} v_i - \epsilon v_\mathsf{max} \geq (1 - \epsilon) \sum_{i \in O} v_i \]를 얻을 수 있습니다. 위에서부터 차례로 식을 적용하면 정리의 부등식을 보일 수 있습니다. □
다항 시간 근사 해법
이로써 우리는 알고리즘 2가 임의의 \(\epsilon > 0\)에 대해서 \( (1 - \epsilon) \)-근사 알고리즘이 된다는 사실을 알 수 있습니다. 놀랍게도 이는 \( \epsilon \)의 값이 작아지면 작아질 수록 더욱 정확한 해에 근사하는 결과를 출력하는 알고리즘입니다. 이러한 성질을 갖는 알고리즘을 통틀어 다음과 같이 이름을 붙여주었습니다.
정의 2. 다항 시간 근사 해법(Polynomial-time Approximation Scheme, PTAS)
임의의 \(\epsilon > 0\)에 대해, 어떤 maximization problem[ㄴ]을 해결하는 \( (1-\epsilon) \)-근사 알고리즘 \(\mathcal{A}_\epsilon\)이 존재한다면, 그러한 알고리즘의 군집(family) \( \{ \mathcal{A}_\epsilon \} \)을 통틀어서 다항 시간 근사 해법(polynomial-time approximation scheme, PTAS)이라고 부른다.
이 정의에 따르면 수행 시간이 \(\epsilon\)에 크게 의존하지 않는다는 것을 알 수 있습니다. 예를 들면 \( O(n^{1/\epsilon}) \)과 같이 \( \frac{1}{\epsilon} \)에 지수적으로 증가하는 수행시간을 갖는 알고리즘도 PTAS의 정의에 부합합니다. 이렇게 정의해도 괜찮은 이유는 \( \epsilon \)은 하나의 상수로 취급할 것이고, 그러면 \( n \)의 다항 시간에 동작한다고 말할 수 있기 때문입니다.
하지만, 정리 3에서 우리는 위 알고리즘이 \( O(\frac{n^3}{\epsilon}) \)에 동작한다고 보였습니다. 이는 \(n\)은 물론 \( \frac{1}{\epsilon} \)의 다항식이기도 합니다. 이러한 알고리즘들은 위 알고리즘보다 어쩌면 더 좋다고 말할 수 있겠습니다. 따라서 이러한 알고리즘을 모아서 따로 또 이름을 지어줬습니다.
정의 3. 완전 다항 시간 근사 해법 (Fully Polynomial-time Approximation Scheme, FPTAS)
임의의 \(\epsilon > 0\)에 대해, 수행 시간이 \(\frac{1}{\epsilon}\)의 다항식이기도 한 다항 시간 근사 해법을 완전 다항 시간 근사 해법(fully polynomial-time approximation scheme, FPTAS)라고 부른다.
이로써 알고리즘 2는 배낭 문제를 해결하는 완전 다항 시간 근사 해법이 됩니다.
마치며
이번 시간에는 유명한 NP-난해 문제인 배낭 문제에 대해 좀더 깊이 공부해 보았습니다. 놀랍게도 이 문제를 거의 정확히 해결할 수 있는 방법이 존재한다는 것을 알 수 있었습니다. 구체적으로는 임의의 \(\epsilon\)에 대해서 \(1-\epsilon\)의 근사비를 갖는 알고리즘의 군집을 일컫는 다항 시간 근사 해법이 존재한다는 것을 함께 보였습니다.
이렇게 좋은 성질을 보이는 PTAS가 존재하는 문제들이 여럿 있습니다. 대표적인 예시로는 이번에 본 배낭 문제와 더불어 유클리드 외판원 문제(Euclidean traveling salesman problem)가 있습니다. 개인적으로 아직은 잘 모르는 내용이기는 합니다만, 나중에 공부해서 적어볼 수 있도록 하겠습니다.
혹시 잘못된 점이 있다면 알려주시기 바랍니다. 궁금한 점이 있으시다면 언제든지 질문해주세요. 고맙습니다.
참조
[1] David P. Williamson and David B. Shmoys. The design of approximation algorithms. Cambridge university press, 2011. Available online: https://www.designofapproxalgs.com/download.php.
주석
[ㄱ] 무리수는 유한의 비트로는 완벽하게 표현할 수 없으므로 \( v_i, w_i \in \mathbb{Q}_+ \)라고 가정하겠습니다. 아래에서는 물건의 가치에 대해서만 보일 예정이나 동일한 기법을 무게에도 적용할 수 있습니다. 각 물건의 가치가 유리수라면 어떤 정수 \( q_i, p_i \in \mathbb{Z}_+ \)에 대해 \(v_i = \frac{q_i}{p_i}\)로 표현할 수 있습니다. 모든 \(v_i\)의 분모를 통일한다면 입력이 분자의 정수로만 이루어졌다고 생각할 수 있습니다. 이를 위해서는 분모의 최소공배수 \(P\)를 구해야 합니다. 이 값은 \( P \leq p_1 \times \cdots p_n \leq p_\mathsf{max}^n \)입니다.(단, \(p_\mathsf{max}\)는 \(p_1, \cdots, p_n\) 중 최댓값) 따라서 \(P\)는 총 \( O(n \log p_\mathsf{max}) \)의 비트로 표현할 수 있습니다. 총 \(n\) 개의 가치에 \(P\)를 곱할 것이므로 크기는 원래에 비해 \( O(n^2 \log p_\mathsf{max}) \) 정도로 늘어나게 됩니다. 이는 여전히 본래 입력의 다항식으로 표현됩니다.
[ㄴ] 비슷하게, minimization problem에 대해서는 임의의 \(\epsilon > 0\)에 대해 \( (1+\epsilon)\)-근사 알고리즘의 군집으로 정의됩니다.
'근사 알고리즘 > Knapsack' 카테고리의 다른 글
| [배낭문제 / Knapsack Problem] 0.5-근사 알고리즘 (0) | 2020.06.17 |
|---|
