分区问题

分区问题(英语:Partition problem)是数论计算机科学领域的问题,[1]目的是把一个多重集分为两个子集,要求这两个集合中所有数的和相等。尽管分区问题属于NP完全问题,但是依然存在伪多项式时间的动态规划解法,而且在很多情况下也存在启发式的解法,能够求出最优解或近似最优解。正是基于这一点,这类问题也被称为“最简单的难题”。[2][3]

分区问题存在一个最佳化问题,该问题是将分为,要求中元素的和与中元素的和相差最小。这一问题属于NP困难问题,但在实践中依旧存在高效的解法。[4]

分区问题是以下两个相关问题的特殊情况:

  • 子集和问题:从集合找到一个子集,使其所有元素的和等于一给定值(分区问题就是T为所有元素之和的时的特殊情况)
  • 多路数字分区:将集合分为个子集,要求每个子集的元素之和都相等(分区问题就是时的特殊情况)
  • 但是需要注意的是,三分区问题与分区问题有很大不同,三分区问题要求每个子集中都有3个元素。三分区问题比分区问题更难,甚至连伪多项式时间算法都不存在,除非满足P=NP[5]

实例

现有多重集 ,可以被分为 以及 ,两者元素之和皆为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. 

参考文献