Перегляд вихідного коду сторінки Задача про розбиття

У [[Теорія чисел|теорії чисел]] та [[Інформатика|інформатиці]], задачею про розбиття (або розбиття числа<ref>{{Harvnb|Korf|1998}}</ref>) є визначення того, чи можна дану [[Множина|множину]] ''S'' [[Натуральні числа|натуральних чисел]] розбити на дві підмножини ''S''<sub>1</sub> і ''S''<sub>2</sub> так, щоб сума чисел у ''S''<sub>1</sub> дорівнювала сумі чисел в ''S''<sub>2</sub>. Хоча задача про розбиття [[NP-повна задача|NP-повна]], існує псевдо-поліноміальне рішення динамічного програмування часу, і є евристики, які вирішують цю задачу оптимально або приблизно. З цієї причини її назвали «найлегшою [[NP-складна задача|NP-важкою]] задачею» <ref name=hayes>{{Harvnb|Hayes|2002}}</ref>.

Існує версія [[Оптимізація (математика)|оптимізації]] задачі про розбиття, яка полягає в розбитті мультимножини S на дві підмножини ''S''<sub>1</sub>, ''S''<sub>2</sub>, так що різниця між сумою елементів в ''S''<sub>1</sub> і сумою елементів в ''S''<sub>2</sub> мінімізована. Оптимізаційна версія 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 |accessdate=18 травня 2017 |archive-date=27 листопада 2014 |archive-url=https://web.archive.org/web/20141127074630/http://www.ijcai.org/papers09/Papers/IJCAI09-096.pdf }}</ref>

Задача про розбиття є окремим випадком [[Задача про суму підмножини|задачі про суми підмножин]], тому її можна точно розв'язати за час O(2<sup>S/2</sup>).

== Приклади ==
Якщо ''S'' = {3,1,1,2,2,1}, дійсним рішенням задачі розподілу є дві множини ''S''<sub>1</sub> = {1,1,1,2} and ''S''<sub>2</sub> = {2,3}. Обидва набори мають суму 5, та утворюють [[розбиття множини]] ''S''. Зверніть увагу, що це рішення не є унікальним. ''S''<sub>1</sub> = {3,1,1} and ''S''<sub>2</sub> = {2,2,1} - інше рішення. Не кожну [[Множина|множину]] позитивних цілих чисел можна розбити на дві частини з однаковою сумою. Прикладом такого набору є ''S'' = {2,5}.

== Алгоритм псевдо-поліноміального часу ==
Задача може бути вирішена за допомогою [[Динамічне програмування|динамічного програмування]], коли розмір набору і розмір суми цілих чисел в наборі не надто великі, щоб зробити вимоги до зберігання недосяжними.

Припустимо, що вхідним значенням для алгоритму є список форми: 
''S = x''<sub>1</sub>, ..., ''x''<sub>''n''</sub>

Нехай ''N'' - кількість елементів в ''S''. Нехай ''K'' - сума всіх елементів в ''S''. Тобто: ''K'' = ''x''<sub>1</sub> + ... + ''x''<sub>''n''</sub>. Ми побудуємо алгоритм, який визначає, чи існує підмножина ''S'', яка додається до <math>\lfloor K/2 \rfloor </math>. Якщо є підмножина, то:

Якщо сума ''K'' парна, залишок ''S'' також підсумовується до <math>\lfloor K/2 \rfloor </math>

Якщо сума ''K'' непарна, то залишок ''S'' підсумовується з <math>\lceil K/2 \rceil </math>. Це найкраще рішення.

=== Рекурентне відношення ===
Ми хочемо визначити, чи існує підмножина ''S,'' котра дорівнює <math>\lfloor K/2 \rfloor </math>.  Нехай:
:''p''(''i'', ''j'') буде ''Істина'' (''True),'' якщо мультимножина { ''x''<sub>1</sub>, ..., ''x''<sub>''j''</sub> } дорівнює ''i'' , та ''Хибно'' (''False),'' якщо навпаки.

Тоді ''p''(<math>\lfloor K/2 \rfloor </math>, ''n'') - це ''Істина'' тоді та тільки тоді, коли існує мультимножина ''S,'' котра дорівнює <math>\lfloor K/2 \rfloor </math>. Метою нашого алгоритму буде обчислення ''p''(<math>\lfloor K/2 \rfloor </math>, ''n''). Для цього ми маємо наступне [[рекурентне співвідношення]]:
: ''p''(''i'', ''j'') істинно, якщо ''p''(''i'', ''j'' − 1) істинно або ''p''(''i'' − ''x''<sub>''j''</sub>, ''j'' − 1) істинно,
: ''p''(''i'', ''j'') хибне, навпаки.

Це пояснюється наступним чином: є деяка підмножина S, яке підсумовує з ''i'', використовуючи числа
: ''x''<sub>1</sub>, ..., ''x''<sub>''j''</sub>

Тоді та тільки тоді, коли виконано одну з наступних умов:
: Існує підмножина { ''x''<sub>1</sub>, ..., ''x''<sub>''j-1''</sub> } , котра дорівнює ''i'';
: Існує підмножина { ''x''<sub>1</sub>, ..., ''x''<sub>''j-1''</sub> } котра дорівнює ''i'' − ''x''<sub>''j''</sub>, коли ''x''<sub>''j''</sub> + сума підмножини = ''i''.

===Псевдо-поліноміальний алгоритм===
[[Алгоритм]] полягає в тому, щоб створити таблицю розміру <math>\lfloor K/2 \rfloor </math> по ''n'' , що містить значення повторення. Пам'ятайте, що K - це розмір суми, а N - це . кількість елементів. Коли вся таблиця заповнена, поверніть ''P''(<math>\lfloor K/2 \rfloor </math>, ''n''). Нижче наведено зображення таблиці ''P''. Існує синя стрілка від одного блоку до іншого, якщо значення цільового блоку може залежати від значення вихідного блоку. Ця залежність є властивістю рекурентного співвідношення.

[[File:Partition Problem DP table showing dependencies.png|thumb|none|300px|Залежність записів у таблиці (''i'', ''j'')]]

 INPUT:  A list of integers ''S''
 OUTPUT: True if ''S'' can be partitioned into two subsets that have equal sum
 1 '''function''' ''find_partition''(''S''):
 2     n ← |S|
 3     ''K'' ← ''sum(S)''
 4     ''P'' ← empty boolean table of size ''(<math>\lfloor K/2 \rfloor </math> + 1)'' by ''(n + 1)''
 5     '''initialize''' top row (''P(0,x)'') of ''P'' to True
 6     '''initialize''' leftmost column (''P(x, 0)'') of ''P'', except for ''P(0, 0)'' to False
 7     '''for''' ''i'' '''from''' 1 '''to''' <math>\lfloor K/2 \rfloor </math>
 8         '''for''' ''j'' '''from''' 1 '''to''' n
 9             '''if''' ''(i-S[j-1])'' ''>='' 0
 10               ''P(i, j)'' ← ''P(i, j-1)'' '''or''' ''P(i-S[j-1], j-1)''
 11            '''else'''
 12               ''P(i, j)'' ← ''P(i, j-1)''
 13    '''return''' ''P(<math>\lfloor K/2 \rfloor </math>, n)''

===Приклад===
Нижче наведена таблиця ''P'' для прикладу, що використовується вище ''S'' = {3, 1, 1, 2, 2, 1}:
[[File:Partition Prob DP table example.jpg|thumb|none|300px|Результат виконання прикладу алгоритму на таблиці P]]

=== Аналіз ===

Цей алгоритм працює з часом {{math|''O''(''K N'')}}, де {{mvar|N}} - кількість елементів у наборі вхідних даних та {{mvar|K}} - сума елементів у вхідній множині.

Алгоритм може бути розширений до {{mvar|k}}-задачі багаторозбиття, але потім приймає {{math|''O''(''n''(''k'' − 1)''m''<sup>''k'' − 1</sup>)}} пам'ять, де {{mvar|m}}  - найбільше число на вході, що робить його непрактичним навіть для {{math|''k'' {{=}} 3}} , якщо входи не є дуже маленькими числами. {{r|multi}}

Цей алгоритм можна узагальнити для вирішення [[Задача про суму підмножини|задачі про суми підмножин]].

== Апроксимаційні алгоритми ==
{{Докладніше|Апроксимаційний алгоритм}}
Існує кілька евристичних алгоритмів для отримання наближень до задачі оптимізації розбиття. Вони можуть бути розширені до точних алгоритмів [[Векторний простір|лінійного простору]].{{r|multi}}

=== Жадібний алгоритм ===
Один з підходів до задачі, що імітує те, як діти вибирають команди для гри, — це жадібний алгоритм, який виконує ітерацію за номерами в порядку убування, привласнюючи кожному з них те, що підмножина має меншу суму. Цей підхід має [[Час Роботи|час роботи]]  {{math|''O''(''n'' log ''n'')}}. Ця евристика добре працює на практиці, коли цифри в наборі приблизно того ж розміру, що і потужність, або менше, але не гарантується, що буде створений найкращий розділ. Наприклад, якщо ввести ''S'' = {4, 5, 6, 7, 8} як вхідні дані, цей жадібний алгоритм розбив би {{mvar|S}} на підмножини {4, 5, 8} та {6, 7}; однак, ''S'' має точно збалансоване розбиття на підмножини {7, 8} та {4, 5, 6}.

Відомо, що цей жадібний підхід дає {{frac|7|6}}-[[Апроксимація|наближення]] до оптимального рішення версії оптимізації; Тобто, якщо жадібний алгоритм виводить два набори {{mvar|A}} та {{mvar|B}}, то {{math|max(∑A, ∑B) ≤ {{sfrac|7|6}} OPT}}, де {{math|OPT}} це розмір більшого набору в найкращому можливому розділі.<ref name="Graham">{{cite news | author = Ron L. Graham | title=Bounds on multiprocessor timing anomalies | journal = SIAM J. Appl. Math. | volume = 17 | number = 2 | year = 1969 | pages = 416–429 | ref = harv}}</ref>Нижче наведено приклад (написаний на мові [[Python]]) для жадібного алгоритму..

<syntaxhighlight lang="python">
def find_partition(int_list):
    "returns: An attempt at a partition of `int_list` into two sets of equal sum"
    A = set()
    B = set()
    for n in sorted(int_list, reverse=True):
        if sum(A) < sum(B):
           A.add(n)
        else:
           B.add(n)
    return (A, B)
</syntaxhighlight>

Цей алгоритм може бути поширений на випадок {{math|''k'' > 2}} множин: для того, щоб узяти {{mvar|k}} найбільших елементів і для кожного розбиття їх розширює розділ, послідовно додаючи інші елементи в залежності від того, який набір менше. (Проста версія вище відповідає {{math|''k'' {{=}} 2}}.) Ця версія працює в часі {{math|''O''(2<sup>''k''</sup> ''n''<sup>2</sup>)}} і, як відомо, дає {{math|{{sfrac|(''k'' + 2)|(''k'' + 1)}}}} [[Апроксимація|наближення]].<ref name="Graham" /> Таким чином, ми маємо [[Схема наближення до поліноміального часу|схему наближення поліноміального часу (PTAS)]] для завдання про розбиття чисел, хоча це не повністю поліноміальна схема наближення часу (час роботи є експоненціальним у гарантованій задачі наближення). Однак існують варіанти цієї ідеї, які є повністю поліноміальними схемами апроксимації для завдання підмножини, а отже, і для завдання розбиття.<ref name="MartelloToth">{{cite book|chapter=4 Subset-sum problem|pages=[https://archive.org/details/knapsackproblems0000mart/page/105 105–136]|title=Knapsack problems: Algorithms and computer interpretations|last1=Martello|first1=Silvano|last2=Toth|first2=Paolo|publisher=Wiley-Interscience|year=1990|isbn=0-471-92420-2|mr=1086874|ref=harv|url=https://archive.org/details/knapsackproblems0000mart/page/105}}</ref>

=== Метод найбільшої різниці ===
Іншою евристикою є метод найбільшої різниці (''largest differencing method'', ''LDM''),<ref>{{cite journal |last1=Michiels |first1=Wil |first2=Jan |last2=Korst |first3=Emile |last3=Aarts |title=Performance ratios for the Karmarkar–Karp differencing method |journal=Electronic Notes in Discrete Mathematics |volume=13 |year=2003 |pages=71–75}}</ref> що також має назву евристика [[Нарендра Кармаркар|Кармаркара]] — [[Річард Карп|Карпа]], за прізвищами пари вчених, що опублікували роботу по цій темі в 1982 році.<ref>{{Harvnb|Karmarkar|Karp|1982}}</ref> LDM працює в два етапи. Перша фаза алгоритму приймає два найбільших числа від входу і замінює їх їхньою різницею. Це повторюється до тих пір, поки не залишиться тільки одне число. Заміна є рішення розмістити два числа в різних наборах, не вдаючись до негайного визначення того, в якому з них встановлено. В кінці першого етапу єдиним числом, що залишилося, буде різниця двох сум підмножини. Друга фаза реконструює фактичне рішення.{{r|hayes}}

Евристика різниць працює краще, ніж жадібна, але все ще погано для випадків, коли числа є експоненційними за розміром набору.{{r|hayes}}

Наступна програма на [[Java]] реалізує перший етап Кармаркара — Карпа. Він використовує [[Купа|купу]], щоб знайти пару найбільших чисел, які залишилися.

<syntaxhighlight lang="java">
int karmarkarKarpPartition(int[] baseArr) {	
    // create max heap	
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>(baseArr.length, REVERSE_INT_CMP);

    for (int value : baseArr) {		
        heap.add(value);	
    }

    while(heap.size() > 1) {
        int val1 = heap.poll();	
        int val2 = heap.poll();	
        heap.add(val1 - val2);
    }

    return heap.poll();
}
</syntaxhighlight>

=== Інші підходи ===
Існують також {{Нп|Anytime algorithm|алгоритми будь-якого часу}}, засновані на евристичному різницевої аналізі, які спочатку знаходять рішення, повернене евристикою разностного аналізу, потім знаходять прогресивно кращі рішення в міру того, як дозволяє час (можливо, вимагаючи експоненціального часу для досягнення оптимальності для найгірших випадків).<ref>{{Harvnb|Korf|1998}}, {{Harvnb|Mertens|1999}}</ref>

== Жорсткі інстанції ==
Набори з одним або без поділу, як правило, складніше (або найбільш дорогі) вирішувати в порівнянні з їх розмірами введення. Коли значення малі в порівнянні з розміром набору, більш досконалі розділи більш вірогідні. Відомо, що задача зазнає «фазовий перехід»; Ймовірно, для деяких наборів і малоймовірно для інших. Якщо m — число біт, необхідне для вираження будь-якого числа в наборі, а n — розмір набору, то <math>m/n < 1</math> має багато рішень і <math>m/n > 1</math>, як правило, мало або взагалі не має рішень. У міру того як n і m стають більше, ймовірність вчиненого розбиття дорівнює 1 або 0 відповідно. Це спочатку стверджувалося на основі емпіричних даних Гента і Уолша<ref>{{Harvnb|Gent|Walsh|1996}}</ref>, потім використовуючи методи статистичної фізики Мертенса<ref>{{Harvnb|Mertens|1998}}</ref>, а потім довів Боргс, Чайс і Піттель.<ref>{{Harvnb|Borgs|Chayes|Pittel|2001}}</ref>

== Варіанти та узагальнення ==
Існує задача, звана {{Нп|задача про трирозбиття|||3-partition problem}}, яка полягає в розбитті множини ''S'' до |''S''|/3 трійок з однаковою сумою. Ця задача суттєво відрізняється від задачі розділу і не має псевдо-поліноміального алгоритму часу, якщо '''[[Рівність класів P і NP|P = NP]]'''.<ref name="Garey & Johnson">{{cite book|pages=[https://archive.org/details/computersintract0000gare/page/96 96–105]|title=Computers and Intractability; A Guide to the Theory of NP-Completeness|last1=Garey|first1=Michael|last2=Johnson|first2=David|year=1979|isbn=0-7167-1045-5|url=https://archive.org/details/computersintract0000gare/page/96}}</ref>

Задача багатосторінкового розділу узагальнює оптимізаційну версію задачі про розбиття. Тут мета полягає в тому, щоб розбити безліч або [[мультимножина|мультимножину]] з {{mvar|n}} цілих чисел на задане число {{mvar|k}} підмножин, мінімізуючи різницю між найменшою і найбільшою сумою підмножини.{{r|multi}}

Для подальших узагальнень задачі про розбиття див. [[Задача про пакування в ємності|задачі про пакування в ємності]].

=== Імовірнісна версія ===
Пов'язана з цим задача, в чомусь схожа на [[парадокс днів народження]], полягає у визначенні розміру вхідної множини так, щоб ймовірність існування розв'язку була 50%, за припущення, що кожен елемент в наборі вибирається випадково за рівномірним розподілом між 1 і деяким заданим значенням.

Вирішення цієї задачі може бути нелогічним, як парадокс дня народження. Наприклад, якщо елементи вибираються випадковим чином в межах від 1 до 1 мільйона, інтуїція багатьох людей полягає в тому, що відповідь знаходиться в тисячах, десятках або навіть в сотнях тисяч, тоді як правильна відповідь становить приблизно 23 (див. [[Парадокс днів народження]] § апроксимація).{{джерело|дата=серпень 2020}}

== Нотатки ==
* {{citation |url=http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-problem |title=The Easiest NP Hard Problem |magazine=[[American Scientist]] |last=Hayes |first=Brian |authorlink=Brian Hayes (scientist) |date=May–June 2002 |accessdate=23 травня 2017 |archive-date=21 травня 2017 |archive-url=https://web.archive.org/web/20170521121234/http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-problem }}
*{{Citation
| last = Karmarkar
| first = Narenda
| last2= Karp
| first2 = Richard M
| title = The Differencing Method of Set Partitioning
| journal = Technical Report UCB/CSD 82/113
| publisher = Computer Science Division (EECS)
| location = University of California at Berkeley
| year = 1982
}}
*{{Citation
 |last         = Gent
 |first        = Ian
 |last2        = Walsh
 |first2       = Toby
 |title        = Phase Transitions and Annealed Theories: Number Partitioning as a Case Study
 |url          = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.4475
 |date         = August 1996
 |conference   = ECAI-96
 |editor       = Wolfgang Wahlster
 |booktitle    = Proceedings of 12th European Conference on Artificial Intelligence
 |publisher    = John Wiley and Sons
 |pages        = 170–174
 |accessdate   = 23 травня 2017
 |archive-date = 4 березня 2016
 |archive-url  = https://web.archive.org/web/20160304112234/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.4475
}}
*{{Citation
| last = Gent
| first	= Ian
| last2 = Walsh
| first2 = Toby
| title     = Analysis of Heuristics for Number Partitioning
| url =	http://dx.doi.org/10.1111/0824-7935.0006
| year = 1998
| journal = Computational Intelligence
| volume = 14
| issue = 3
| pages = 430–451
| doi =	10.1111/0824-7935.00069
}}
*{{Citation
| doi = 10.1103/PhysRevLett.81.4281
| volume = 81
| issue = 20
| pages = 4281
| last = Mertens
| first = Stephan
| title = Phase Transition in the Number Partitioning Problem
| journal = Physical Review Letters
| accessdate = 2009-10-03
| date = November 1998
| url = http://link.aps.org/abstract/PRL/v81/p4281
| bibcode=1998PhRvL..81.4281M
|arxiv = cond-mat/9807077 }}

* {{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
}}
*{{citation | 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=[[Cris Moore|Cristopher Moore]] | publisher=Oxford University Press US | isbn=9780195177374 | page=125 | url=https://books.google.com/books?id=4YD6AxV95zEC&pg=PA125 | arxiv=cond-mat/0310317 | bibcode=2003cond.mat.10317M | accessdate=23 травня 2017 | archive-date=5 квітня 2017 | archive-url=https://web.archive.org/web/20170405181738/https://books.google.com/books?id=4YD6AxV95zEC&pg=PA125 }}
*{{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
| accessdate = 2009-10-04
| year = 2001
| url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.9577
| archive-date = 29 вересня 2012
| archive-url = https://web.archive.org/web/20120929040442/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.9577
}}
* {{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
| accessdate = 2009-10-04
| year = 1998
| url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.993
| archive-date = 29 вересня 2012
| archive-url = https://web.archive.org/web/20120929040525/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.993
}}
*{{Citation
| last = Mertens
| first = Stephan
| title = A complete anytime algorithm for balanced number partitioning| year = 1999
| arxiv = cs/9903011
|bibcode = 1999cs........3011M }}

== Примітки ==
{{reflist}}

[[Категорія:NP-повні задачі]]
[[Категорія:Динамічне програмування]]
[[Категорія:Рендеринг]]
[[Категорія:Статті з прикладами коду мовою Python]]
[[Категорія:Статті з прикладами коду мовою Java]]