Проблема с разделом

NP-полная задача в информатике

В теории чисел и информатике задача разбиения или разбиение чисел [ ^1] — это задача определения, можно ли разбить заданное множество S положительных целых чисел на два подмножества S ₁ и S ₂ так, чтобы сумма чисел в S ₁ была равна сумме чисел в S ₂ . Хотя задача разбиения является NP-полной , существует решение динамического программирования за псевдополиномиальное время , и существуют эвристики, которые решают эту задачу во многих случаях, либо оптимально, либо приблизительно. По этой причине ее называют «самой легкой сложной задачей». ^{[2] [3]}

Существует оптимизационная версия задачи разбиения, которая заключается в разбиении мультимножества S на два подмножества S ₁ , S ₂ таким образом, чтобы разница между суммой элементов в S ₁ и суммой элементов в S ₂ была минимизирована. Оптимизационная версия является NP-трудной , но может быть эффективно решена на практике. ^[4]

Задача о разбиении является частным случаем двух связанных задач:

• В задаче о сумме подмножеств цель состоит в том, чтобы найти подмножество S , сумма которого равна определенному целевому числу T, заданному в качестве входных данных (задача о разбиении является частным случаем, в котором T равно половине суммы S ).
• При многофакторном разбиении чисел имеется целочисленный параметр k , и цель состоит в том, чтобы решить, можно ли разбить S на k подмножеств равной суммы (задача разбиения является частным случаем, в котором k = 2).

Однако это сильно отличается от задачи 3-разбиения : в этой задаче количество подмножеств заранее не фиксировано — оно должно быть | S |/3, где каждое подмножество должно иметь ровно 3 элемента. 3-разбиение намного сложнее, чем разбиение — у него нет алгоритма псевдополиномиального времени, если только P = NP . ^[5]

Примеры

При условии S = ​​{3,1,1,2,2,1} допустимым решением задачи разбиения являются два множества S ₁ = {1,1,1,2} и S ₂ = {2,3}. Оба множества в сумме дают 5, и они разбивают S . Обратите внимание, что это решение не является единственным. S ₁ = {3,1,1} и S ₂ = {2,2,1} — еще одно решение.

Не каждое мультимножество положительных целых чисел имеет разбиение на два подмножества с равной суммой. Примером такого множества является S = {2,5}.

Вычислительная сложность

Задача разбиения является NP-сложной. Это можно доказать путем сведения к задаче суммы подмножества . ^[6] Экземпляр SubsetSum состоит из множества S положительных целых чисел и целевой суммы T ; цель состоит в том, чтобы решить , существует ли подмножество S с суммой, равной точно  T.

Учитывая такой экземпляр, постройте экземпляр Partition, в котором входной набор содержит исходный набор плюс два элемента: z ₁ и z ₂ , где z ₁  = sum(S) и z ₂ = 2 T . Сумма этого входного набора равна sum( S ) +  z ₁  +  z ₂ = 2 sum( S ) + 2 T , поэтому целевая сумма для Partition равна sum( S ) +  T .

• Предположим, что существует решение S ′ для экземпляра SubsetSum. Тогда sum( S ′) =  T , поэтому sum(S′ ∪ z_1) = sum( S ) +  T , поэтому S ′ ∪ z_1 является решением для экземпляра Partition.
• Наоборот, предположим, что существует решение S ′′ для экземпляра Partition. Тогда S ′′ должно содержать либо z ₁ , либо z ₂ , но не оба, так как их сумма больше, чем sum( S ) +  T . Если S'' содержит z ₁ , то оно должно содержать элементы из S с суммой ровно  T , поэтому S'' минус z ₁ является решением экземпляра SubsetSum. Если S'' содержит z ₂ , то оно должно содержать элементы из S с суммой ровно sum( S ) −  T , поэтому другие объекты в S являются решением экземпляра SubsetSum.

Алгоритмы аппроксимации

Как упоминалось выше, проблема разбиения является частным случаем многоходового разбиения и подмножества-суммы. Поэтому ее можно решить с помощью алгоритмов, разработанных для каждой из этих задач. Алгоритмы, разработанные для многоходового разбиения чисел, включают:

• Жадное разбиение чисел – цикл по числам и помещает каждое число в набор, текущая сумма которого наименьшая. Если числа не отсортированы, то время выполнения составляет O( n ), а коэффициент аппроксимации составляет не более 3/2 («коэффициент аппроксимации» означает большую сумму в выходных данных алгоритма, деленную на большую сумму в оптимальном разбиении). Сортировка чисел увеличивает время выполнения до O( n  log  n ) и улучшает коэффициент аппроксимации до 7/6. Если числа распределены равномерно в [0,1], то коэффициент аппроксимации составляет не более почти наверняка ив ожидание. ${\textstyle 1+O\left({\frac {\log \log n}{n}}\right)}$ ${\textstyle 1+O\left({\frac {1}{n}}\right)}$
• Метод наибольшей разности (также называемый алгоритмом Кармаркара–Карпа ) сортирует числа в порядке убывания и многократно заменяет числа их разностями. Сложность выполнения составляет O( n  log  n ). В худшем случае его коэффициент аппроксимации аналогичен — не более 7/6 . Однако в среднем случае он работает намного лучше, чем жадный алгоритм: когда числа распределены равномерно в [0,1], его коэффициент аппроксимации не превышаетожидаемого. Он также работает лучше в имитационных экспериментах. ${\textstyle 1+1/n^{\Theta (\log n)}}$
• Алгоритм multifit использует бинарный поиск в сочетании с алгоритмом bin packing . В худшем случае его коэффициент аппроксимации составляет 8/7 .
• Задача о сумме подмножеств имеет FPTAS , который можно использовать и для задачи о разбиении, установив целевую сумму равной sum( S )/2.

Точные алгоритмы

Существуют точные алгоритмы , которые всегда находят оптимальное разбиение. Поскольку задача NP-трудная, такие алгоритмы могут занять экспоненциальное время в общем случае, но могут быть практически применимы в определенных случаях. Алгоритмы, разработанные для многоканального разбиения чисел, включают:

• Разбиение псевдополиномиального времени занимает память, где m — наибольшее число во входных данных. ${\textstyle O(nm)}$
• Полный жадный алгоритм (CGA) рассматривает все разделы, строя двоичное дерево . Каждый уровень в дереве соответствует входному числу, где корень соответствует наибольшему числу, уровень ниже — следующему по величине числу и т. д. Каждая ветвь соответствует разному набору, в который можно поместить текущее число. Обход дерева в глубину требует только пространства, но может занять время. Время выполнения можно улучшить, используя жадную эвристику: на каждом уровне сначала разрабатывайте ветвь, в которой текущее число помещается в набор с наименьшей суммой. Этот алгоритм сначала находит решение, найденное жадным разбиением чисел , но затем переходит к поиску лучших решений. Некоторые вариации этой идеи представляют собой полностью полиномиальные схемы приближения для задачи подмножества-суммы, а следовательно, и для задачи разбиения. ^{[7] [8]} ${\textstyle O(n)}$ ${\textstyle O(2^{n})}$
• Полный алгоритм Кармаркара–Карпа (CKK) рассматривает все разбиения, строя двоичное дерево. Каждый уровень соответствует паре чисел. Левая ветвь соответствует размещению их в разных подмножествах (т. е. замене их разностью), а правая ветвь соответствует размещению их в том же подмножестве (т. е. замене их суммой). Этот алгоритм сначала находит решение, найденное методом наибольшей разности , но затем переходит к поиску лучших решений. Он работает существенно быстрее, чем CGA на случайных экземплярах. Его преимущество намного больше, когда существует равное разбиение, и может быть на несколько порядков величины. На практике задачи произвольного размера могут быть решены с помощью CKK, если числа имеют не более 12 значащих цифр . ^[9] CKK также может работать как алгоритм anytime : он сначала находит решение KK, а затем находит все более лучшие решения по мере того, как позволяет время (возможно, требуя экспоненциального времени для достижения оптимальности, для худших экземпляров). ^[1] Он требует пространства, но в худшем случае может занять время. $O(n)$ $O(2^{n})$

Разработанные алгоритмы для подмножественной суммы включают:

• Горовиц и Санхи – действие происходит во времени , но требует пространства. $O(2^{n/2}\cdot (n/2))$ $O(2^{n/2})$
• Шрёппель и Шамир – работает во времени и требует гораздо меньше места – . $O(2^{n/2}\cdot (n/4))$ ${\textstyle O(2^{n/4})}$
• Howgrave-Graham and Joux – работает во времени , но это рандомизированный алгоритм , который решает только задачу принятия решения (а не задачу оптимизации). ${\textstyle O(2^{n/3})}$

Твердые случаи и фазовый переход

Наборы только с одним или без разделов, как правило, сложнее всего (или дороже всего) решать по сравнению с их размерами входных данных. Когда значения малы по сравнению с размером набора, идеальные разделы более вероятны. Известно, что проблема претерпевает « фазовый переход »; будучи вероятным для некоторых наборов и маловероятным для других. Если m — это количество бит, необходимых для выражения любого числа в наборе, а n — размер набора, то имеет тенденцию иметь много решений и имеет тенденцию иметь мало или не иметь решений. По мере того, как n и m становятся больше, вероятность идеального раздела стремится к 1 или 0 соответственно. Первоначально это утверждалось на основе эмпирических данных Джентом и Уолшем ^[10] , затем с использованием методов статистической физики Мертенсом ^{[11] [12]} и позже доказано Боргсом , Чейесом и Питтелем ^[13] . ${\displaystyle m/n<1}$ ${\displaystyle m/n>1}$

Вероятностная версия

Связанная проблема, несколько похожая на парадокс дня рождения , заключается в определении размера входного набора таким образом, чтобы у нас была вероятность в половину того, что есть решение, при условии, что каждый элемент в наборе выбирается случайным образом с равномерным распределением между 1 и некоторым заданным значением. Решение этой проблемы может быть контринтуитивным, как парадокс дня рождения.

Варианты и обобщения

Равномощное разбиение — это вариант, в котором обе части должны иметь равное количество элементов, в дополнение к равной сумме. Этот вариант также NP-трудный. ^{[5] : SP12} Доказательство . Дано стандартное разбиение с некоторыми n числами, постройте экземпляр равномощного разбиения, добавив n нулей. Очевидно, что новый экземпляр имеет равномощное разбиение с равной суммой, если и только если исходный экземпляр имеет равносуммовое разбиение. См. также Сбалансированное разбиение чисел .

Разбиение продукта — это проблема разбиения набора целых чисел на два набора с одинаковым произведением (а не одинаковой суммой). Эта задача сильно NP-трудна . ^[14]

Ковалёв и Пеш ^[15] обсуждают общий подход к доказательству NP-трудности задач типа разбиения.

Приложения

Одно из применений проблемы разделения — манипулирование выборами . Предположим, что есть три кандидата (A, B и C). Один кандидат должен быть избран с использованием правила голосования, основанного на подсчете очков, например, правила вето (каждый избиратель накладывает вето на одного кандидата, и кандидат с наименьшим количеством вето побеждает). Если коалиция хочет обеспечить избрание C, она должна разделить свои голоса между A и B так, чтобы максимизировать наименьшее количество вето, которое получает каждый из них. Если голоса взвешены, то проблему можно свести к проблеме разделения, и, таким образом, ее можно эффективно решить с помощью CKK. То же самое верно для любого другого правила голосования, основанного на подсчете очков. ^[16]

Примечания

1. Корф 1998.
2. Хейс, Брайан (март–апрель 2002 г.), «Самая простая трудная проблема» (PDF) , American Scientist , т. 90, № 2, Sigma Xi, Научно-исследовательское общество, стр. 113–117, JSTOR  27857621
3. Мертенс 2006, стр. 125.
4. Корф, Ричард Э. (2009). Многоканальное разбиение чисел (PDF) . IJCAI .
5. Garey, Michael; Johnson, David (1979). Компьютеры и неразрешимость; Руководство по теории NP-полноты . стр. 96–105. ISBN 978-0-7167-1045-5.
6. Гудрич, Майкл. «Больше NP-полных и NP-трудных задач» (PDF) .
7. Ганс Келлерер; Ульрих Пферши; Дэвид Пизингер (2004). Проблемы с рюкзаком. Спрингер. п. 97. ИСБН 9783540402862.
8. Мартелло, Сильвано; Тот, Паоло (1990). "4 Subset-sum problem". Задачи о ранце: алгоритмы и компьютерные интерпретации . Wiley-Interscience. стр. 105–136. ISBN 978-0-471-92420-3. МР  1086874.
9. Корф, Ричард Э. (1995-08-20). «От приближенных к оптимальным решениям: пример разбиения чисел». Труды 14-й Международной объединенной конференции по искусственному интеллекту . IJCAI'95. Том 1. Монреаль, Квебек, Канада: Morgan Kaufmann Publishers. С. 266–272. ISBN 978-1-55860-363-9.
10. Гент и Уолш 1996.
11. Мертенс 1998.
12. Мертенс 2001, стр. 130.
13. Боргс, Чайес и Питтель 2001.
14. Ng, CT; Barketau, MS; Cheng, TCE; Kovalyov, Michael Y. (2010-12-01). ""Product Partition" и связанные с этим проблемы планирования и надежности систем: вычислительная сложность и аппроксимация". European Journal of Operational Research . 207 (2): 601–604. doi :10.1016/j.ejor.2010.05.034. ISSN  0377-2217.
15. Ковалёв, Михаил Ю.; Пеш, Эрвин (28.10.2010). «Общий подход к доказательству NP-трудности задач типа разбиения». Дискретная прикладная математика . 158 (17): 1908–1912. doi : 10.1016/j.dam.2010.08.001 . ISSN  0166-218X.
16. Уолш, Тоби (2009-07-11). «Где действительно сложные проблемы манипуляции? Фазовый переход в манипулировании правилом вето» (PDF) . Написано в Пасадене, Калифорния, США. Труды Двадцать первой международной совместной конференции по искусственному интеллекту . Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc. стр. 324–329. Архивировано (PDF) из оригинала 2020-07-10 . Получено 2021-10-05 .

Ссылки

• Borgs, Christian; Chayes, Jennifer; Pittel, Борис (2001), «Фазовый переход и конечномерное масштабирование для задачи целочисленного разбиения», Случайные структуры и алгоритмы , 19 (3–4): 247–288, CiteSeerX  10.1.1.89.9577 , doi :10.1002/rsa.10004, S2CID  6819493
• Gent, Ian; Walsh, Toby (август 1996 г.). «Фазовые переходы и отожженные теории: разбиение чисел как пример исследования». В Wolfgang Wahlster (ред.). Труды 12-й Европейской конференции по искусственному интеллекту . ECAI-96. John Wiley and Sons. стр. 170–174. CiteSeerX  10.1.1.2.4475 .
• Гент, Ян; Уолш, Тоби (1998), «Анализ эвристики для разбиения чисел», Computational Intelligence , 14 (3): 430–451, CiteSeerX  10.1.1.149.4980 , doi :10.1111/0824-7935.00069, S2CID  15344203
• Корф, Ричард Э. (1998), «Полный алгоритм разбиения чисел на разделы в любое время», Искусственный интеллект , 106 (2): 181–203, CiteSeerX  10.1.1.90.993 , doi :10.1016/S0004-3702(98)00086-1, ISSN  0004-3702
• Мертенс, Стефан (ноябрь 1998 г.), «Фазовый переход в задаче разбиения чисел», Physical Review Letters , 81 (20): 4281–4284, arXiv : cond-mat/9807077 , Bibcode : 1998PhRvL..81.4281M, doi : 10.1103/PhysRevLett.81.4281, S2CID  119541289
• Мертенс, Стефан (2001), «Физический подход к разбиению чисел», Теоретическая информатика , 265 (1–2): 79–108, arXiv : cond-mat/0009230 , doi :10.1016/S0304-3975(01)00153-0, S2CID  16534837
• Mertens, Stephan (2006). "The Easiest Hard Problem: Number Partitioning". В Allon Percus; Gabriel Istrate; Cristopher Moore (ред.). Computational difficulty and statistics physics . USA: Oxford University Press. стр. 125–140. arXiv : cond-mat/0310317 . Bibcode :2003cond.mat.10317M. ISBN 9780195177374.
• Мертенс, Стефан (1999), «Полный алгоритм для сбалансированного разбиения чисел», arXiv : cs/9903011