分區問題

分區問題（英語：Partition problem）是數論和計算機科學領域的問題，^[1]目的是把一個多重集${\displaystyle S}$分為${\displaystyle S_{1}}$和${\displaystyle S_{2}}$兩個子集，要求${\displaystyle S_{1}}$和${\displaystyle S_{2}}$這兩個集合中所有數的和相等。儘管分區問題屬於NP完全問題，但是依然存在偽多項式時間的動態規劃解法，而且在很多情況下也存在啟發式的解法，能夠求出最優解或近似最優解。正是基於這一點，這類問題也被稱為「最簡單的難題」。^[2][3]

分區問題存在一個最佳化問題，該問題是將${\displaystyle S}$分為${\displaystyle S_{1}}$和${\displaystyle S_{2}}$，要求${\displaystyle S_{1}}$中元素的和與${\displaystyle S_{2}}$中元素的和相差最小。這一問題屬於NP困難問題，但在實踐中依舊存在高效的解法。^[4]

分區問題是以下兩個相關問題的特殊情況：

• 子集和問題：從集合${\displaystyle S}$找到一個子集，使其所有元素的和等於一給定值${\displaystyle T}$（分區問題就是T為${\displaystyle S}$所有元素之和的${\displaystyle {\frac {1}{2}}}$時的特殊情況）
• 多路數字分區：將集合${\displaystyle S}$分為${\displaystyle k}$個子集，要求每個子集的元素之和都相等（分區問題就是${\displaystyle k=2}$時的特殊情況）
• 但是需要注意的是，三分區問題與分區問題有很大不同，三分區問題要求每個子集中都有3個元素。三分區問題比分區問題更難，甚至連偽多項式時間算法都不存在，除非滿足P=NP。^[5]

5 sources

實例

現有多重集${\displaystyle S={3,1,1,2,2,1}}$，可以被分為${\displaystyle S_{1}={1,1,1,2}}$以及${\displaystyle S_{2}={2,3}}$，兩者元素之和皆為5。

注釋

1. Korf 1998.
2. Hayes, Brian, The Easiest Hard Problem (PDF), American Scientist, vol. 90 no. 2 (Sigma Xi, The Scientific Research Society), March–April 2002: 113–117 [2022-03-01], JSTOR 27857621, （原始內容存檔 (PDF)於2012-09-16）
3. Mertens 2006，第125頁.
4. Korf, Richard E. Multi-Way Number Partitioning (PDF). IJCAI. 2009 [2022-03-01]. （原始內容存檔 (PDF)於2014-11-27）.
5. Garey, Michael; Johnson, David. Computers and Intractability; A Guide to the Theory of NP-Completeness. 1979: 96–105. ISBN 978-0-7167-1045-5.

參考文獻

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