分區問題(英語: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. 

參考文獻

編輯