查看“︁分区问题”︁的源代码

{{Expand language|1=en|time=2022-03-01T05:21:12+00:00}}
'''分区问题'''（{{lang-en|Partition problem}}）是[[数论]]和[[计算机科学]]领域的问题，{{sfn|Korf|1998}}目的是把一个多重集<math>S</math>分为<math>S_1</math>和<math>S_2</math>两个子集，要求<math>S_1</math>和<math>S_2</math>这两个集合中所有数的和相等。尽管分区问题属于[[NP完全]]问题，但是依然存在[[伪多项式时间]]的动态规划解法，而且在很多情况下也存在启发式的解法，能够求出最优解或近似最优解。正是基于这一点，这类问题也被称为“最简单的难题”。<ref name=hayes>{{citation |jstor=27857621 |title=The Easiest Hard Problem |volume=90 |issue=2 |pages=113–117 |magazine=[[American Scientist]] |last=Hayes |first=Brian |author-link=Brian Hayes (scientist) |date=March–April 2002 |publisher=Sigma Xi, The Scientific Research Society |url=http://bit-player.org/bph-publications/AmSci-2002-03-Hayes-NPP.pdf |accessdate=2022-03-01 |archive-date=2012-09-16 |archive-url=https://web.archive.org/web/20120916170626/http://bit-player.org/bph-publications/AmSci-2002-03-Hayes-NPP.pdf |dead-url=no }}</ref>{{sfn|Mertens|2006|p=[https://books.google.com/books?id=4YD6AxV95zEC&pg=PA125 125]}}

分区问题存在一个[[最佳化問題]]，该问题是将<math>S</math>分为<math>S_1</math>和<math>S_2</math>，要求<math>S_1</math>中元素的和与<math>S_2</math>中元素的和相差最小。这一问题属于[[NP困难]]问题，但在实践中依旧存在高效的解法。<ref name="multi">{{cite conference |last=Korf |first=Richard E. |title=Multi-Way Number Partitioning |conference=[[IJCAI]] |year=2009 |url=http://ijcai.org/papers09/Papers/IJCAI09-096.pdf |access-date=2022-03-01 |archive-date=2014-11-27 |archive-url=https://web.archive.org/web/20141127074630/http://www.ijcai.org/papers09/Papers/IJCAI09-096.pdf |dead-url=no }}</ref>

分区问题是以下两个相关问题的特殊情况：
*[[子集和问题]]：从集合<math>S</math>找到一个子集，使其所有元素的和等于一给定值<math>T</math>（分区问题就是T为<math>S</math>所有元素之和的<math>\frac{1}{2}</math>时的特殊情况）
*[[多路数字分区]]：将集合<math>S</math>分为<math>k</math>个子集，要求每个子集的元素之和都相等（分区问题就是<math>k=2</math>时的特殊情况）
*但是需要注意的是，三分区问题与分区问题有很大不同，三分区问题要求每个子集中都有3个元素。三分区问题比分区问题更难，甚至连伪多项式时间算法都不存在，除非满足[[P=NP]]。<ref name="Garey & Johnson">{{cite book|last1=Garey|first1=Michael|url=https://archive.org/details/computersintract0000gare|title=Computers and Intractability; A Guide to the Theory of NP-Completeness|last2=Johnson|first2=David|year=1979|isbn=978-0-7167-1045-5|pages=[https://archive.org/details/computersintract0000gare/page/96 96–105]}}</ref>

==实例==
现有多重集<math>S={3,1,1,2,2,1}</math>，可以被分为<math>S_1={1,1,1,2}</math>以及<math>S_2={2,3}</math>，两者元素之和皆为5。

==注释==
{{reflist}}
==参考文献==
*{{Citation
| doi = 10.1002/rsa.10004
| volume = 19
| issue = 3–4
| pages = 247–288
| last1 = Borgs
| first1 = Christian
| last2 = Chayes
| first2 = Jennifer
| last3 = Pittel
| first3 = Boris
| title = Phase transition and finite-size scaling for the integer partitioning problem
| journal = Random Structures and Algorithms
| year = 2001
| citeseerx = 10.1.1.89.9577
}}
*{{cite conference
| last1 = Gent
| first1 = Ian
| last2 = Walsh
| first2 = Toby
| title = Phase Transitions and Annealed Theories: Number Partitioning as a Case Study
|date=August 1996
| editor = Wolfgang Wahlster
| book-title = Proceedings of 12th European Conference on Artificial Intelligence |conference=ECAI-96
| publisher = John Wiley and Sons
| pages = 170–174
| citeseerx	= 10.1.1.2.4475
}}
*{{Citation
| last1 = Gent
| first1 = Ian
| last2 = Walsh
| first2 = Toby
| title = Analysis of Heuristics for Number Partitioning
| year = 1998
| journal = Computational Intelligence
| volume = 14
| issue = 3
| pages = 430–451
| doi =	10.1111/0824-7935.00069
| citeseerx	= 10.1.1.149.4980
| s2cid	= 15344203
}}
* {{Citation
| doi = 10.1016/S0004-3702(98)00086-1
| issn = 0004-3702
| volume = 106
| issue = 2
| pages = 181–203
| last = Korf
| first = Richard E.
| title = A complete anytime algorithm for number partitioning
| journal = Artificial Intelligence
| year = 1998
| citeseerx = 10.1.1.90.993
}}
*{{Citation
| doi = 10.1103/PhysRevLett.81.4281
| volume = 81
| issue = 20
| pages = 4281–4284
| last = Mertens
| first = Stephan
| title = Phase Transition in the Number Partitioning Problem
| journal = Physical Review Letters
| date = November 1998
| bibcode=1998PhRvL..81.4281M
|arxiv = cond-mat/9807077 | s2cid = 119541289
}}
* {{Citation
| doi = 10.1016/S0304-3975(01)00153-0
| last = Mertens
| first = Stephan
| title = A physicist's approach to number partitioning
| journal = Theoretical Computer Science
| volume = 265
| issue = 1–2
| pages = 79–108| year = 2001
| arxiv = cond-mat/0009230
| s2cid = 16534837
}}
*{{cite book |year=2006 |chapter=The Easiest Hard Problem: Number Partitioning |last=Mertens |first=Stephan |title=Computational complexity and statistical physics |editor1=Allon Percus |editor2=Gabriel Istrate |editor3=Cristopher Moore |editor3-link=Cris Moore |publisher=Oxford University Press |place=USA |isbn=9780195177374 |pages=125–140 |chapter-url=https://books.google.com/books?id=4YD6AxV95zEC&pg=PA125 |arxiv=cond-mat/0310317 |bibcode=2003cond.mat.10317M |access-date=2022-03-01 |archive-date=2017-04-05 |archive-url=https://web.archive.org/web/20170405181738/https://books.google.com/books?id=4YD6AxV95zEC&pg=PA125 |dead-url=no }}
*{{cite arXiv
| last = Mertens
| first = Stephan
| title = A complete anytime algorithm for balanced number partitioning| pages = 
| year = 1999
| eprint = cs/9903011
| mode = cs2
}}

[[Category:NP完全问题]]