파티션 문제

숫자 이론과 컴퓨터 과학에서, 분할 문제 또는 숫자 ^[1]분할은 S에 있는 숫자의 합이 S에 있는₁₂ 숫자의 합과 같도록 양의 정수로 이루어진 주어진 다중 집합 S가 두 개의 부분₁ 집합 S와₂ S로 분할될 수 있는지 여부를 결정하는 작업이다.파티션 문제는 NP-완전이지만 의사 다항 시간 동적 프로그래밍 솔루션이 있으며, 최적 또는 대략적으로 문제를 해결하는 휴리스틱스도 있습니다.그래서 '가장 쉬운 어려운 문제'^[2]^[3]로 불린다.

파티션 문제의 최적화 버전이 있는데, 이는 멀티셋 S를 2개의 서브셋₁ S, S로₂ 분할하여 S의 요소의₁ 합과 S의 요소의₂ 합의 차이를 최소화하는 것이다.최적화 버전은 NP-hard이지만 ^[4]실제로는 효율적으로 해결할 수 있습니다.

파티션 문제는 다음 두 가지 관련 문제의 특수한 경우입니다.

부분집합 문제에서는 입력으로 주어진 특정 목표수 T인 S의 부분집합을 찾는 것이 목표입니다(분할 문제는 T가 S의 절반인 특수한 경우입니다).
다원 번호 분할에서는 정수 매개변수 k가 존재하며, 목표는 S를 동일한 합계의 k개의 부분 집합으로 분할할 수 있는지 여부를 결정하는 것입니다(분할 문제는 k = 2인 특수한 경우입니다).
단, 이 문제는 3차원 문제와는 상당히 다릅니다.이 문제에서는 서브셋의 수가 사전에 고정되어 있지 않습니다.각 서브셋이 정확히 3개의 요소를 가져야 하는 S/3이어야 합니다.3차원 문제는 파티션보다 훨씬 어렵습니다.^[5]P = NP가 아닌 한 의사 차분 시간 알고리즘은 없습니다.

예

S = {3,1,1,2,1,1}이면 파티션 문제에 대한 유효한 해결책은 S = {1,1,2,2} 및₂ S = {2,3} 두 집합입니다₁.두 집합의 합은 5가 되고 S를 분할합니다.이 솔루션은 고유하지 않습니다.S₁ = {3,1,1} 및₂ S = {2,2,1}도 다른 솔루션입니다.

양의 정수로 이루어진 모든 다중 집합이 동일한 합을 갖는 두 개의 부분 집합으로 분할되는 것은 아닙니다.이러한 집합의 예는 S = {2,5}입니다.

계산 경도

파티션의 문제는 NP하드.이것은 부분집합 문제의 ^[6]감소로 증명될 수 있다.부분집합합은 양의 정수 집합 S와 목표합 T로 구성됩니다. 목표는 정확히 합이 T인 S의 부분집합이 있는지 확인하는 것입니다.

이러한 경우 입력 세트에 z = sum(S₂) 및 z = 2T의₁ 두 요소 외에₂ 원래 세트가₁ 포함된 파티션 인스턴스를 구성합니다.이 입력 세트의 합계는 sum(S) + z₁ + z₂ = 2 sum(S) + 2T이므로 파티션의 목표 합계는 sum(S) + T입니다.

SubsetSum 인스턴스에 대한 솔루션 S'가 존재한다고 가정합니다.그런 다음 sum(Sµ) = T이므로 sum(Sµ u₁ {z}) = sum(S) + T이므로 Sµ u₁ {z}은(는) 파티션 인스턴스에 대한 솔루션입니다.
반대로 파티션인스턴스에 대한 솔루션S''가 존재한다고 가정합니다.그 후, S'는 z 또는₂ z 중 하나를₁ 포함해야 하지만, 둘 다 포함해서는 안 된다. S'가 z를 포함하는₁ 경우, S'에서₁ 정확히 T의 합을 갖는 원소를 포함해야 하므로 S' - z는 SubsetSum 인스턴스에 대한 해이다.S"가 z를 포함하는₂ 경우 S"의 요소를 정확히 합(S) - T의 합으로 포함해야 하므로 S의 다른 개체는 SubsetSum 인스턴스에 대한 솔루션이 됩니다.

근사 알고리즘

위에서 설명한 바와 같이 파티션 문제는 멀티웨이 파티션과 서브셋섬의 특수한 경우입니다.따라서 이러한 문제 각각을 위해 개발된 알고리즘으로 해결할 수 있습니다.멀티웨이 번호 분할용으로 개발된 알고리즘은 다음과 같습니다.

Gready number partitioning – 숫자를 루프하여 현재 합계가 가장 작은 집합에 각 숫자를 넣습니다.숫자가 정렬되지 않은 경우 실행시간은 O(n)이고 근사비는 최대 3/2입니다('근사비'는 알고리즘 출력의 큰 합을 최적 파티션의 큰 합으로 나눈 것을 의미합니다).숫자를 정렬하면 실행 시간이 O(n log n)로 증가하고 근사 비율이 7/6으로 향상됩니다.숫자가 [0,1]에서 균일하게 분포되어 있는 경우 근사비는 최대 $1+O(\log {\log {n}}/n)$ + $1+O(\log {\log {n}}/n)$ log $1+O(\log {\log {n}}/n)$ n / $1+O(\log {\log {n}}/n)$ $)(\log {n}$ / $n)$ 이며 $1+O(\log {\log {n}}/n)$ , $예상치$ 는 1 $1+O(1/n)$ + $1+O(1/n)$ ${$ $n$ } / n $)$ 입니다 $1+O(1/n)$ .
최대 차이점 처리 방식(Karmarkar-Karp 알고리즘이라고도 함)은 숫자를 내림차순으로 정렬하고 숫자를 차이에 따라 반복적으로 바꿉니다.실행 시 복잡도는 O(n log n)입니다.최악의 경우 근사 비율은 비슷합니다. 많아야 7/6입니다.단, 평균적인 경우 Gready 알고리즘보다 훨씬 뛰어난 성능을 발휘합니다.[0,1]에서 숫자가 균일하게 분포되어 있는 경우 $1+1/n^{\Theta (\log {n})}$ 는 최대 $1+1/n^{\Theta (\log {n})}$ 1 + $1+1/n^{\Theta (\log {n})}$ / $1+1/n^{\Theta (\log {n})}$ $1+1/n^{\Theta (\log {n})}$ ( log $1+1/n^{\Theta (\log {n})}$ n $){$ $displaystyle$ 1 + 1 / $n^$ { $\Theta(\log {n})}}$ 이 $1+1/n^{\Theta (\log {n})}$ (가) 필요합니다.시뮬레이션 실험에서도 더 나은 성능을 발휘합니다.
Multiit 알고리즘은 bin packing 알고리즘과 결합된 이진 검색을 사용합니다.최악의 경우 근사비는 8/7입니다.
서브셋 합계 문제에는 FPTAS가 있어, 목표 합계를 sum(S)/2로 설정함으로써 파티션 문제에도 사용할 수 있습니다.

정확한 알고리즘

항상 최적의 파티션을 찾는 정확한 알고리즘이 있습니다.문제는 NP-hard이기 때문에 이러한 알고리즘은 일반적으로 기하급수적인 시간이 걸릴 수 있지만 경우에 따라서는 실제로 사용할 수 있습니다.멀티웨이 번호 분할용으로 개발된 알고리즘은 다음과 같습니다.

의사 다중 시간 번호 분할에는 $O(nm)$ O ( $O(nm)$ m $O(nm)$ ) \ $displaystyle$ O ( $nm )$ 메모리가 $O(nm)$ $O(nm)$ 됩니다. $여기$ 서 m은 입력에서 가장 큰 숫자입니다.
CGA(Complete Gready Algorithm)는 이진 트리를 구성하여 모든 파티션을 고려합니다.트리의 각 레벨은 입력번호에 대응하며, 여기서 루트는 최대수에 대응하고, 아래 레벨은 다음 최대수에 대응합니다.각 브랜치는 현재 번호를 넣을 수 있는 다른 세트에 대응합니다.트리를 깊이 우선 순서로 이동하려면 O $O(n)$ ( $O(n)$ ) \ $displaystyle$ O ( $n$ )공간만 $O(n)$ $O(n)$ 한데 O ( $O(2^{n})$ $O(2^{n})$ ) $O(2^{n})$ \ $displaystyle$ O ( 2 $O(2^{n})$ ^ { n ) $}$ 시간이 $O(2^{n})$ $O(2^{n})$ 수 있습니다.실행 시간은 탐욕적 휴리스틱을 사용하여 개선할 수 있습니다. 각 레벨에서 가장 작은 합으로 현재 숫자를 집합에 넣는 분기를 먼저 개발하십시오.이 알고리즘은 먼저 그리디 번호 분할에 의해 발견된 솔루션을 찾아낸 후 더 나은 솔루션을 찾습니다.이 아이디어의 일부 변형은 부분집합 문제와 분할 문제에 ^[7]^[8]대한 완전한 다항식 시간 근사 체계이다.
Complete Karmarkar-Karp 알고리즘(CKK)은 바이너리 트리를 생성하여 모든 파티션을 고려합니다.각 레벨은 숫자의 쌍에 대응합니다.왼쪽 가지는 다른 서브셋에 배치(즉, 차이에 의해 치환)하는 것에 대응하고 오른쪽 가지는 동일한 서브셋에 배치(즉, 합계에 의해 치환)하는 것에 대응합니다.이 알고리즘은 가장 큰 차이점 보관 방법에 의해 발견된 솔루션을 먼저 찾지만 더 나은 솔루션을 찾기 위해 계속 진행합니다.랜덤 인스턴스에서는 CGA보다 훨씬 빠르게 실행됩니다.균일한 파티션이 존재할 경우 장점이 훨씬 더 크며, 크기가 여러 개일 수 있습니다.실제로 임의의 크기의 문제는 숫자가 ^[9]최대 12자리일 경우 CKK로 해결할 수 있다.CKK는 임의의 알고리즘으로서도 실행할 수 있습니다.KK 솔루션을 먼저 찾은 후 시간이 허락하면 점진적으로 더 나은 솔루션을 찾습니다(최악의 ^[1]경우 최적성에 도달하려면 기하급수적인 시간이 필요할 수 있습니다).O $O(n)$ ( $O(n)$ ) $O(n)$ \ $displaystyle$ O ( $n$ )스페이스가 $O(n)$ $O(n)$ 하지만 최악의 경우 O $O(2^{n})$ ( $O(2^{n})$ n $)\$ $displaystyle$ O ( $2$ ^ { $n$ )시간이 $O(2^{n})$ $O(2^{n})$ 수 있습니다.

서브셋 합계를 위해 개발된 알고리즘은 다음과 같습니다.

Horowitz 및 Sanhi – $시간$ O ( $O(2^{n/2}\cdot (n/2))$ n / 2 $O(2^{n/2}\cdot (n/2))$ ( $n$ / $O(2^{n/2}\cdot (n/2))$ ) $O(2^{n/2}\cdot (n/2))$ \ $cdot ( n$ / $2$ ) $O(2^{n/2}\cdot (n/2))$ 。단, O $O(2^{n/2})$ ( $O(2^{n/2})$ / $O(2^{n/2})$ ) $O(2^{n/2})$ \ $display style$ O ( 2 $O(2^{n/2})$ ^ { $O(2^{n/2}\cdot (n/2))$ $n$ / 2 $)$ 공간이 $O(2^{n/2})$ $O(2^{n/2})$ 합니다.
Schroppel 및 Shamir – 시간 $O(2^{n/2}\cdot (n/4))$ O ( $O(2^{n/2}\cdot (n/4))$ $O(2^{n/2}\cdot (n/4))$ / $O(2^{n/2}\cdot (n/4))$ ( $O(2^{n/2}\cdot (n/4))$ / $O(2^{n/2}\cdot (n/4))$ 4 ) $O(2^{n/2}\cdot (n/4))$ \ $display style$ O ( $2$ ^ { $O(2^{n/2}\cdot (n/4))$ $n$ / $2$ ) \ $cdot$ ( $n$ / 4 ) $O(2^{n/2}\cdot (n/4))$ , 、 requires much much much much much much much much much much $muchO$ ( $O(2^{n/4})$ / $O(2^{n/4})$ 4 ) $O(2^{n/4})$ 。 $필요$ 한 공간은 훨씬 $O(2^{n/4})$
Howgrave-Graham and Joux – $O(2^{n/3})$ O ( $O(2^{n/3})$ n / $O(2^{n/3})$ $){$ $displaystyle$ O ( $2$ ^ { $n$ / $3$ ) $O(2^{n/3})$ 는 실행되지만, 이 알고리즘은 결정 문제(최적화 문제가 아님)만을 해결하는 랜덤 알고리즘입니다.

하드 인스턴스 및 단계 전환

파티션이 1개만 있거나 파티션이 없는 세트는 입력 크기에 비해 해결하기가 가장 어렵거나 비용이 많이 드는 경향이 있습니다.값이 세트의 크기에 비해 작을 경우 완벽한 파티션이 발생할 가능성이 높습니다.이 문제는 "상 전이"를 겪는 것으로 알려져 있는데, 일부 세트에서는 가능성이 높고 다른 세트에서는 가능성이 낮습니다.m이 세트 내의 임의의 숫자를 표현하기 위해 필요한 비트 수이고 n이 세트의 크기인 $m/n<1$ m $m/n<1$ $m/n>1$ $m/n<1$ \ $displaystyle$ m/n $< 1$ $m/n>1$ > $m/n>1$ \ $displaystyle$ m $/n > 1$ 은 $m/n>1$ 이 $m/n>1$ 적거나 아예 없는 경향이 있습니다.n과 m이 커질수록 완벽한 분할 확률은 각각 1 또는 0이 됩니다.이것은 원래 Gent와 Walsh에 ^[10]의해 경험적 증거에 기초하고, ^[11]^[12]Mertens에 의해 통계 물리학에서 나온 방법들을 사용하였고, 후에 Borgs, Chayes, Pittel에 ^[13]의해 증명되었다.

확률적 버전

생일 역설과 다소 유사한 관련 문제는 집합의 각 요소가 1과 주어진 값 사이에서 균일한 분포로 무작위로 선택된다고 가정할 때 솔루션이 있을 확률이 1/2이 되도록 입력 집합의 크기를 결정하는 것입니다.이 문제에 대한 해결책은 생일 역설처럼 직관에 반할 수 있습니다.

변종과 일반화

균등 카디널리티 파티션은 두 부분이 동일한 합계를 가질 뿐만 아니라 동일한 수의 항목을 가져야 하는 변형입니다.이 변종도 ^[5]^{: SP12}NP-hard입니다.증명. 표준 파티션인스턴스에 n개의 번호를 지정하면 n개의 0을 추가하여 Equal-Cardinality-Partition 인스턴스를 만듭니다.원래 인스턴스가 등가합 파티션을 가지고 있는 경우 새로운 인스턴스는 등가합 파티션을 가지고 있습니다.자세한 내용은 균형 잡힌 번호 분할을 참조하십시오.

고유 파티션은 모든 입력 정수가 다른 변형입니다.이 변종도 ^{[citation needed]}NP-hard입니다.

제품 분할은 (같은 합계가 아니라) 동일한 곱을 사용하여 정수 집합을 두 집합으로 분할하는 문제입니다.이 문제는 매우 NP-hard입니다.^[14]

Kovalyov와 Pesch는^[15] 분할형 문제의 NP-hardness를 증명하기 위한 일반적인 접근방식을 논의한다.

적용들

칸막이 문제의 한 가지 적용은 선거를 조작하는 것이다.세 가지 후보(A, B 및 C)가 있다고 가정합니다.단일 후보는 채점에 기초한 투표 규칙(예: 거부권 규칙)을 사용하여 선출해야 합니다(각 투표자는 단일 후보에 대해 거부권을 행사하고 거부권이 가장 적은 후보가 승리합니다).연합이 C의 당선을 확실히 하고 싶다면, 그들은 A와 B로 그들의 표를 나눠서 그들이 얻는 거부권을 최대화해야 한다.투표에 가중치를 부여하면 문제가 분할 문제로 축소되어 CKK를 사용하여 효율적으로 해결할 수 있다.채점에 ^[16]기초한 다른 투표 규칙도 마찬가지입니다.

메모들

^ ^a ^b Korf 1998.
^ Hayes, Brian (March–April 2002), "The Easiest Hard Problem" (PDF), American Scientist, Sigma Xi, The Scientific Research Society, vol. 90, no. 2, pp. 113–117, JSTOR 27857621
^ Mertens 2006, 125페이지
^ Korf, Richard E. (2009). Multi-Way Number Partitioning (PDF). IJCAI.
^ ^a ^b Garey, Michael; Johnson, David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5.
^ Goodrich, Michael. "More NP complete and NP hard problems" (PDF).{{cite web}}: CS1 maint :url-status (링크)
^ Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). Knapsack problems. Springer. p. 97. ISBN 9783540402862.
^ Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 978-0-471-92420-3. MR 1086874.
^ Korf, Richard E. (1995-08-20). "From approximate to optimal solutions: a case study of number partitioning". Proceedings of the 14th International Joint Conference on Artificial Intelligence. IJCAI'95. Vol. 1. Montreal, Quebec, Canada: Morgan Kaufmann Publishers. pp. 266–272. ISBN 978-1-55860-363-9.
^ Gent & Walsh 1996.
^ 1998년 메르텐스
^ Mertens 2001, 130페이지
^ Borgs, Chayes & Pittel 2001.
^ Ng, C. T.; Barketau, M. S.; Cheng, T. C. E.; Kovalyov, Mikhail Y. (2010-12-01). ""Product Partition" and related problems of scheduling and systems reliability: Computational complexity and approximation". European Journal of Operational Research. 207 (2): 601–604. doi:10.1016/j.ejor.2010.05.034. ISSN 0377-2217.
^ Kovalyov, Mikhail Y.; Pesch, Erwin (2010-10-28). "A generic approach to proving NP-hardness of partition type problems". Discrete Applied Mathematics. 158 (17): 1908–1912. doi:10.1016/j.dam.2010.08.001. ISSN 0166-218X.
^ Walsh, Toby (2009-07-11). "Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule" (PDF). Written at Pasadena, California, USA. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. San Francisco, California, USA: Morgan Kaufmann Publishers Inc. pp. 324–329. Archived (PDF) from the original on 2020-07-10. Retrieved 2021-10-05.

레퍼런스

Borgs, Christian; Chayes, Jennifer; Pittel, Boris (2001), "Phase transition and finite-size scaling for the integer partitioning problem", Random Structures and Algorithms, 19 (3–4): 247–288, CiteSeerX 10.1.1.89.9577, doi:10.1002/rsa.10004
Gent, Ian; Walsh, Toby (August 1996). "Phase Transitions and Annealed Theories: Number Partitioning as a Case Study". In Wolfgang Wahlster (ed.). Proceedings of 12th European Conference on Artificial Intelligence. ECAI-96. John Wiley and Sons. pp. 170–174. CiteSeerX 10.1.1.2.4475.
Gent, Ian; Walsh, Toby (1998), "Analysis of Heuristics for Number Partitioning", Computational Intelligence, 14 (3): 430–451, CiteSeerX 10.1.1.149.4980, doi:10.1111/0824-7935.00069, S2CID 15344203
Korf, Richard E. (1998), "A complete anytime algorithm for number partitioning", Artificial Intelligence, 106 (2): 181–203, CiteSeerX 10.1.1.90.993, doi:10.1016/S0004-3702(98)00086-1, ISSN 0004-3702
Mertens, Stephan (November 1998), "Phase Transition in the Number Partitioning Problem", Physical Review Letters, 81 (20): 4281–4284, arXiv:cond-mat/9807077, Bibcode:1998PhRvL..81.4281M, doi:10.1103/PhysRevLett.81.4281, S2CID 119541289
Mertens, Stephan (2001), "A physicist's approach to number partitioning", Theoretical Computer Science, 265 (1–2): 79–108, arXiv:cond-mat/0009230, doi:10.1016/S0304-3975(01)00153-0, S2CID 16534837
Mertens, Stephan (2006). "The Easiest Hard Problem: Number Partitioning". In Allon Percus; Gabriel Istrate; Cristopher Moore (eds.). Computational complexity and statistical physics. USA: Oxford University Press. pp. 125–140. arXiv:cond-mat/0310317. Bibcode:2003cond.mat.10317M. ISBN 9780195177374.
Mertens, Stephan (1999), "A complete anytime algorithm for balanced number partitioning", arXiv:cs/9903011

[FOOTNOTEKorf1998-1] Korf 1998.

[hayes-2] Hayes, Brian (March–April 2002), "The Easiest Hard Problem" (PDF), American Scientist, Sigma Xi, The Scientific Research Society, vol. 90, no. 2, pp. 113–117, JSTOR 27857621

[FOOTNOTEMertens2006[httpsbooksgooglecombooksid4YD6AxV95zECpgPA125_125]-3] Mertens 2006, 125페이지

[multi-4] Korf, Richard E. (2009). Multi-Way Number Partitioning (PDF). IJCAI.

[Garey_&_Johnson-5] Garey, Michael; Johnson, David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5.

[6] Goodrich, Michael. "More NP complete and NP hard problems" (PDF).{{cite web}}: CS1 maint :url-status (링크)

[7] Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). Knapsack problems. Springer. p. 97. ISBN 9783540402862.

[8] Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 978-0-471-92420-3. MR 1086874.

[9] Korf, Richard E. (1995-08-20). "From approximate to optimal solutions: a case study of number partitioning". Proceedings of the 14th International Joint Conference on Artificial Intelligence. IJCAI'95. Vol. 1. Montreal, Quebec, Canada: Morgan Kaufmann Publishers. pp. 266–272. ISBN 978-1-55860-363-9.

[FOOTNOTEGentWalsh1996-10] Gent & Walsh 1996.

[FOOTNOTEMertens1998-11] 1998년 메르텐스

[FOOTNOTEMertens2001130-12] Mertens 2001, 130페이지

[FOOTNOTEBorgsChayesPittel2001-13] Borgs, Chayes & Pittel 2001.

[14] Ng, C. T.; Barketau, M. S.; Cheng, T. C. E.; Kovalyov, Mikhail Y. (2010-12-01). ""Product Partition" and related problems of scheduling and systems reliability: Computational complexity and approximation". European Journal of Operational Research. 207 (2): 601–604. doi:10.1016/j.ejor.2010.05.034. ISSN 0377-2217.

[15] Kovalyov, Mikhail Y.; Pesch, Erwin (2010-10-28). "A generic approach to proving NP-hardness of partition type problems". Discrete Applied Mathematics. 158 (17): 1908–1912. doi:10.1016/j.dam.2010.08.001. ISSN 0166-218X.

[Walsh_324–329-16] Walsh, Toby (2009-07-11). "Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule" (PDF). Written at Pasadena, California, USA. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. San Francisco, California, USA: Morgan Kaufmann Publishers Inc. pp. 324–329. Archived (PDF) from the original on 2020-07-10. Retrieved 2021-10-05.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Search