Проблема с разделом - Partition problem

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

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

Проблема разделения - это частный случай двух связанных проблем:

в проблема суммы подмножества, цель - найти подмножество S чья сумма - определенное число W задано в качестве входных данных (проблема разбиения - это частный случай, когда W это половина суммы S).
В многостороннее разделение номеров, есть целочисленный параметр k, и цель - решить, S можно разделить на k подмножества равной суммы (проблема разбиения - частный случай, когда k = 2).
Однако это совсем не то, что Проблема с 3 разделами: в этой задаче количество подмножеств заранее не фиксируется - оно должно быть |S| / 3, где каждое подмножество должно иметь ровно 3 элемента. 3-разбиение намного сложнее, чем разбиение - у него нет алгоритма псевдополиномиального времени, если только P = NP.^[4]

Примеры

Данный 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}.

Алгоритмы приближения

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

Жадное разбиение чисел - перебирает числа и помещает каждое число в набор, текущая сумма которого наименьшая. Если числа не отсортированы, время выполнения - O (п), а коэффициент аппроксимации не превосходит 3/2 («коэффициент аппроксимации» означает большую сумму на выходе алгоритма, деленную на большую сумму в оптимальном разделе). Сортировка чисел увеличивает время выполнения до O (п бревно п ) и улучшает коэффициент аппроксимации до 7/6. Если числа распределены равномерно в [0,1], то коэффициент аппроксимации не превосходит ${ Displaystyle 1 + О ( журнал { журнал {п}} / п)}$ почти наверняка , и ${ Displaystyle 1 + О (1 / п)}$ в ожидании.
Метод наибольшей разности (также называемый Алгоритм Кармаркара-Карпа ) сортирует числа в порядке убывания и многократно заменяет числа на их разности. Сложность выполнения - O (п бревно п ). В худшем случае его коэффициент аппроксимации аналогичен - не более 7/6. Однако в среднем случае он работает намного лучше, чем жадный алгоритм: когда числа распределены равномерно в [0,1], его коэффициент аппроксимации не превышает ${ displaystyle 1 + 1 / n ^ { Theta ( log {n})}}$ в ожидании. Он также лучше работает в имитационных экспериментах.
В Алгоритм Multifit использует двоичный поиск в сочетании с алгоритмом для упаковка бункера . В худшем случае его коэффициент аппроксимации равен 8/7.

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

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

В псевдополиномиальное разбиение на временные числа берет ${ Displaystyle O (нм)}$ память, где $м$ - наибольшее число во входных данных.
В Полный жадный алгоритм (CGA) рассматривает все перегородки путем построения двоичное дерево. Каждый уровень в дереве соответствует входному числу, где корень соответствует наибольшему числу, нижний уровень - следующему наибольшему числу и т. Д. Каждая ветвь соответствует разному набору, в который можно поместить текущее число. Обход дерева в в глубину для заказа требуется только ${ Displaystyle О (п)}$ пространство, но может занять ${ Displaystyle О (2 ^ {п})}$ время. Среду выполнения можно улучшить, используя жадную эвристику: на каждом уровне сначала разработайте ветвь, в которой текущее число помещается в набор с наименьшей суммой. Этот алгоритм сначала находит решение, найденное жадное разделение чисел, но затем переходит к поиску лучших решений. Некоторые варианты этой идеи находятся полностью полиномиальные схемы аппроксимации для задачи о сумме подмножеств, а следовательно, и для задачи о разбиении.^[5]^[6]
В Полный алгоритм Кармаркара-Карпа (CKK) рассматривает все разделы путем построения двоичного дерева. Каждому уровню соответствует пара цифр. Левая ветвь соответствует помещению их в разные подмножества (т. Е. Замене их разницей), а правая ветвь соответствует помещению их в одно подмножество (т. Е. Замене их суммой). Этот алгоритм сначала находит решение, найденное метод наибольшей разности, но затем переходит к поиску лучших решений. На случайных экземплярах он работает значительно быстрее, чем CGA. Его преимущество намного больше, когда существует равное разделение, и может составлять несколько порядков. На практике задачи произвольного размера могут быть решены CKK, если в числах не более 12 значащие цифры.^[7] CKK также может работать как алгоритм в любое время : сначала он находит решение KK, а затем находит все более лучшие решения по мере того, как позволяет время (возможно, для достижения оптимальности в худших случаях требуется экспоненциальное время).^[8] Это требует ${ Displaystyle О (п)}$ место, но в худшем случае может занять ${ Displaystyle О (2 ^ {п})}$ время.

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

Горовиц и Санхи - бежит во времени ${ Displaystyle О (2 ^ {п / 2} cdot (п / 2))}$ , но требует ${ Displaystyle О (2 ^ {п / 2})}$ Космос.
Шроппель и Шамир - бежит во времени ${ Displaystyle О (2 ^ {п / 2} cdot (п / 4))}$ , и требует гораздо меньше места - ${ Displaystyle О (2 ^ {п / 4})}$ .
Хоугрейв-Грэм и Жу - бежит во времени ${ Displaystyle О (2 ^ {п / 3})}$ , но это рандомизированный алгоритм это решает только проблему решения (не проблему оптимизации).

Жесткие экземпляры и фазовый переход

Наборы только с одним разделом или без него, как правило, труднее (или дороже всего) решать по сравнению с их входными размерами. Когда значения малы по сравнению с размером набора, идеальные разделы более вероятны. Известно, что проблема "фаза перехода "; вероятно для одних наборов и маловероятно для других. Если m - количество битов, необходимых для выражения любого числа в наборе, а n - размер набора, то ${ Displaystyle м / п <1}$ имеет много решений и ${ displaystyle m / n> 1}$ имеет мало решений или вообще не имеет их. Чем больше n и m, тем больше вероятность идеального разбиения до 1 или 0 соответственно. Первоначально это утверждалось на основе эмпирических данных Гента и Уолша,^[9] затем, используя методы статистической физики Мертенса,^[10]^:130 и позже доказано Борги, Chayes, и Питтель.^[11]

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

Ограничение, требующее, чтобы раздел имел одинаковый размер или чтобы все входные целые числа были разными, также является NP-трудным.^{[нужна цитата ]}

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

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

Приложения

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

Примечания

^ Корф 1998
^ Хейс, Брайан (Март – апрель 2002 г.), «Самая легкая трудная задача», Американский ученый, Сигма Си, Общество научных исследований, т. 90 нет. 2. С. 113–117. JSTOR 27857621
^ Корф, Ричард Э. (2009). Многостороннее разделение номеров (PDF). IJCAI.
^ Гарей, Майкл; Джонсон, Дэвид (1979). Компьютеры и труднодоступность; Руководство по теории NP-полноты. стр.96–105. ISBN 978-0-7167-1045-5.
^ Ханс Келлерер; Ульрих Пферши; Дэвид Писингер (2004), Проблемы с рюкзаком, Springer, стр. 97, ISBN 9783540402862
^ Мартелло, Сильвано; Тот, Паоло (1990). «Проблема 4-х подмножеств». Задачи о ранце: алгоритмы и компьютерные интерпретации. Wiley-Interscience. стр.105–136. ISBN 978-0-471-92420-3. МИСТЕР 1086874.
^ Корф, Ричард Э. (1995-08-20). «От приближенных к оптимальным решениям: пример разделения чисел». Материалы 14-й совместной международной конференции по искусственному интеллекту - Том 1. IJCAI'95. Монреаль, Квебек, Канада: Morgan Kaufmann Publishers Inc .: 266–272. ISBN 978-1-55860-363-9.
^ Корф, Ричард Э. (1998-12-01). «Полный в любое время алгоритм для разделения номеров». Искусственный интеллект. 106 (2): 181–203. Дои:10.1016 / S0004-3702 (98) 00086-1. ISSN 0004-3702.
^ Гент и Уолш 1996
^ Мертенс 1998, Мертенс 2001
^ Боргс, Чайес и Питтель 2001
^ Уолш, Тоби (11 июля 2009 г.). «Где действительно сложные проблемы манипулирования? Фазовый переход в манипулировании правилом вето». Материалы 21-й международной конференции по искусственному интеллекту. IJCAI'09. Пасадена, Калифорния, США: Morgan Kaufmann Publishers Inc .: 324–329.