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

Partition problem

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

Существует версия оптимизации проблемы разделения, которая заключается в разделении мультимножества S на два подмножества S1, S2 такая, что разница между суммой элементов в S1 и сумма элементов в S2 сводится к минимуму. Версия оптимизации 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}, допустимым решением проблемы разбиения являются два множества S1 = {1,1,1,2} и S2 = {2,3}. Сумма обоих наборов равна 5, и они раздел S. Обратите внимание, что это решение не уникально. S1 = {3,1,1} и S2 = {2,2,1} - другое решение.

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

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

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

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

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

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

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

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

  • Горовиц и Санхи - бежит во времени , но требует Космос.
  • Шроппель и Шамир - бежит во времени , и требует гораздо меньше места - .
  • Хоугрейв-Грэм и Жу - бежит во времени , но это рандомизированный алгоритм это решает только проблему решения (не проблему оптимизации).

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

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

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

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

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

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

Приложения

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

Примечания

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

Рекомендации

  • Гент, Ян; Уолш, Тоби (август 1996 г.), Вольфганг Вальстер (редактор), Фазовые переходы и отожженные теории: числовое разбиение как пример, John Wiley and Sons, стр. 170–174, CiteSeerX 10.1.1.2.4475
  • Гент, Ян; Уолш, Тоби (1998), "Анализ эвристики для разделения чисел", Вычислительный интеллект, 14 (3): 430–451, CiteSeerX 10.1.1.149.4980, Дои:10.1111/0824-7935.00069
  • Мертенс, Стефан (ноябрь 1998 г.), "Фазовый переход в проблеме разделения чисел", Письма с физическими проверками, 81 (20): 4281–4284, arXiv:cond-mat / 9807077, Bibcode:1998ПхРвЛ..81.4281М, Дои:10.1103 / PhysRevLett.81.4281