부분집합 합 문제

3. 지수 시간 알고리즘

부분집합 합 문제는 ''n''에 대해 지수 시간 내에 해결하는 여러 방법이 있다.^[5]

• 포함-배제: 가장 단순한 알고리즘은 ''n''개의 모든 부분 집합을 순회하면서 각 부분 집합의 합이 조건을 만족하는지 확인하는 것이다. 이 알고리즘은 $O(2^n\; \backslash cdot\; n)$의 시간 복잡도를 가지며, 깊이 우선 탐색으로 구현할 수 있다.^[5]
• 호로비츠와 사흐니 알고리즘: 1974년에 발표된 알고리즘으로, $O(\; 2^\{n/2\}\backslash cdot\; (n/2))$ 시간과 $O(\; 2^\{n/2\})$ 공간 복잡도를 가진다. 입력 집합을 둘로 나누어 각 부분집합의 합을 계산하고 정렬한 후, 합이 ''T''가 되는 원소 쌍을 찾는다. (two-sum 문제)^[6][7]
• 슈뢰펠과 샤미르 알고리즘: 1981년에 제시된 알고리즘으로, 호로비츠와 사니 알고리즘과 실행 시간은 비슷하지만 공간 사용량을 $O(2^\{n/4\})$로 줄였다. 원소를 4개의 집합으로 분할하고 최소 힙을 사용한다.^[8]
• Howgrave-Graham and Joux: 2010년에 제시된 확률적 알고리즘으로, 이전 알고리즘들보다 빠르다. 시간 복잡도는 O(2^0.337n)이고 공간 복잡도는 O(2^0.256n)이다.^[9]

3. 1. 포함-배제 (Inclusion-Exclusion)

• 입력 숫자를 내림차순으로 처리한다.
• 주어진 노드에 포함된 정수가 지금까지 찾은 최적해의 합을 초과하면 해당 노드를 가지치기한다.
• 주어진 노드에 포함된 정수와 나머지 모든 정수의 합이 지금까지 찾은 최적해의 합보다 작으면 해당 노드를 가지치기한다.

3. 2. 호로비츠와 사니 (Horowitz and Sahni)

3. 3. 슈뢰펠과 샤미르 (Schroeppel and Shamir)

3. 4. Howgrave-Graham and Joux

4. 유사 다항 시간 동적 프로그래밍 해법

부분 집합 합 문제는 동적 프로그래밍을 사용하여 유사 다항 시간 내에 해결할 수 있다. 주어진 원소들의 수열 $x\_1,\backslash ldots,\; x\_N$에 대해, 정수 쌍 (''i'', ''s'')을 ''상태''로 정의한다. 이 상태는 "$x\_1,\backslash ldots,\; x\_i$의 합이 s인 공집합이 아닌 부분 집합이 존재한다"는 것을 나타낸다.

각 상태 (''i'', ''s'')는 다음 두 가지 상태로 전이될 수 있다.

• (''i''+1, ''s''): $x\_\{i+1\}$이 부분 집합에 포함되지 않음.
• (''i''+1, ''s''+$x\_\{i+1\}$): $x\_\{i+1\}$이 부분 집합에 포함됨.

5. 다항 시간 근사 알고리즘

모든 입력이 양수라고 가정할 때, 부분집합 합 문제(SSP)에 대한 근사 알고리즘은 ''S''의 부분 집합 중에서 합이 최대 ''T''이고 최적 합의 최소 ''r''배가 되는 집합을 찾는 것을 목표로 한다. 여기서 ''r''은 ''근사 비율''이라고 하며 0과 1 사이의 값을 갖는다.^[17]

5. 1. 단순 1/2-근사

• 입력을 내림차순으로 정렬한다.
• 가장 큰 다음 입력을 부분집합에 넣는다(공간이 허락하는 한).

5. 2. 완전 다항 시간 근사해법 (FPTAS)

• ''U_i''를 ''L''의 모든 요소 ''y''와, ''L''의 모든 ''y''에 대한 모든 합 ''x_i'' + ''y''를 포함하는 리스트로 설정한다.
• ''U_i''를 오름차순으로 정렬한다.
• ''L''을 비운다.
• ''y''를 ''U_i''의 가장 작은 요소로 설정한다.
• ''y''를 ''L''에 추가한다.
• ''U_i''의 요소를 증가하는 순서대로 각 요소 ''z''에 대해 반복한다.
• 만약 ''y'' + ''εT''/''n'' < ''z'' ≤ ''T'' 이면
• ''y'' = ''z''
• ''z''를 ''L''에 추가한다.

• ''L''에 남아 있는 모든 합이 ''T'' 미만이 되도록 하여 부분 집합 합 문제에 대한 실행 가능한 해가 되도록 한다.
• 리스트 L이 "희소"하도록 보장한다. 즉, 각 두 개의 연속적인 부분 합의 차이는 최소 εT/n이다.

참조

_[1] 서적 Algorithm Design https://archive.org/[...]
_[2] 웹사이트 More NP complete and NP hard problems https://www.ics.uci.[...]
_[3] 서적 Computers and Intractability: A Guide to the Theory of NP-Completeness W. H. Freeman and Company
_[4] 문서 Answer to: "Is there a known, fast algorithm for counting all subsets that sum to below a certain number?" 2016-01-30
_[5] 웹사이트 Optimal Sequential Multi-Way Number Partitioning https://www.cs.uic.e[...] 2014
_[6] 간행물 Computing partitions with applications to the knapsack problem https://ecommons.cor[...]
_[7] 웹사이트 The Two-Sum Problem https://www3.cs.uic.[...]
_[8] 간행물 A {{math|''T'' {{=}} ''O''(2^''n''/2)}}, {{math|''S'' {{=}} ''O''(2^''n''/4)}} algorithm for certain NP-complete problems https://epubs.siam.o[...] 1981-08-01
_[9] 서적 Advances in Cryptology – EUROCRYPT 2010 Springer 2010
_[10] 서적 Advances in Cryptology – EUROCRYPT 2011 Springer 2011
_[11] 서적 Advances in Cryptology - ASIACRYPT 2020 Springer 2020
_[12] 간행물 Linear time algorithms for knapsack problems with bounded weights
_[13] arXiv A Faster Pseudopolynomial Time Algorithm for Subset Sum 2015-07-08
_[14] conference Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) SIAM
_[15] 간행물 An efficient solution to the subset-sum problem on GPU: An efficient solution to the subset-sum problem on GPU 2016-01
_[16] 간행물 A low-space algorithm for the subset-sum problem on GPU 2017-07
_[17] 간행물 The Multiple Subset Sum Problem https://doi.org/10.1[...] 2000-02-01
_[18] 간행물 An efficient fully polynomial approximation scheme for the Subset-Sum Problem 2003-03-01
_[19] 서적 Knapsack problems https://books.google[...] Springer