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

редактировать

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

Существует оптимизационная версия задачи разбиения, которая состоит в том, чтобы разделить мультимножество S на два подмножества S 1, S 2 таким образом, чтобы разница между суммой элементов в S 1 и суммой элементов в S 2 была минимальной. Вариант оптимизации NP-сложен, но может быть эффективно решен на практике.

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

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

СОДЕРЖАНИЕ

1 Примеры
2 Вычислительная сложность
3 Аппроксимационные алгоритмы
4 Точные алгоритмы
5 Жесткие инстансы и фазовый переход
6 Вероятностная версия
7 Варианты и обобщения
8 приложений
9 Примечания
10 Ссылки

Примеры

Для S = {3,1,1,2,2,1} допустимым решением проблемы разбиения являются два множества S 1 = {1,1,1,2} и S 2 = {2,3}. Оба набора просуммировать до 5, и они разметить S. Обратите внимание, что это решение не уникально. S 1 = {3,1,1} и S 2 = {2,2,1} - другое решение.

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

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

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

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

Предположим, что существует решение S 'для экземпляра SubsetSum. Тогда sum (S ') = T, поэтому sum (S' u { z 1 }) = sum (S) + T, поэтому S 'u { z 1 } является решением экземпляра Partition.
И наоборот, предположим, что существует решение S '' для экземпляра Partition. Тогда S '' должен содержать либо z 1, либо z 2, но не оба, поскольку их сумма больше суммы (S) + T. Если S '' содержит z 1, то он должен содержать элементы из S с суммой ровно T, поэтому S '' минус z 1 является решением экземпляра SubsetSum. Если S '' содержит z 2, тогда он должен содержать элементы из S с суммой ровно sum (S) -T, поэтому другие объекты в S являются решением для экземпляра SubsetSum.

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

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

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

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

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

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

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

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

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

Наборы только с одним разделом или без него, как правило, труднее (или дороже всего) решать по сравнению с их входными размерами. Когда значения малы по сравнению с размером набора, идеальные разделы более вероятны. Известно, что проблема претерпевает « фазовый переход »; вероятно для одних наборов и маловероятно для других. Если m - это количество битов, необходимых для выражения любого числа в наборе, а n - это размер набора, то имеет тенденцию иметь много решений и имеет тенденцию иметь мало или не иметь решений. Чем больше n и m, тем больше вероятность идеального разбиения до 1 или 0 соответственно. Это было первоначально утверждал, на основе эмпирических данных по Генте и Уолша, а затем с помощью методов статистической физики на Мертенс, а затем доказывается Borgs, Чайес и Pittel. ${\ Displaystyle м / п lt;1}$ $м / п lt;1$ ${\ displaystyle m / ngt; 1}$ $м / пgt; 1$

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

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

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

Равномерное разделение - это вариант, в котором обе части должны иметь равное количество элементов, помимо равной суммы. Этот вариант тоже NP-сложен, что доказано в задаче [SP12]. См. Раздел Сбалансированное разделение номеров.

Отдельное разделение - это вариант, в котором все входные целые числа различны. Этот вариант тоже NP-сложен.

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

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

Приложения

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

Примечания

использованная литература

Боргс, Кристиан; Чайес, Дженнифер; Питтель, Борис (2001), "Фазовый переход и масштабирование конечного размера для задачи целочисленного разбиения", Случайные структуры и алгоритмы, 19 (3–4): 247–288, CiteSeerX 10.1.1.89.9577, doi : 10.1002 / rsa.10004
Гент, Ян; Уолш, Тоби (август 1996). «Фазовые переходы и отожженные теории: числовое разбиение в качестве примера». В Вольфганге Вальстере (ред.). Материалы 12-й Европейской конференции по искусственному интеллекту. ECAI-96. Джон Уайли и сыновья. С. 170–174. CiteSeerX 10.1.1.2.4475.
Гент, Ян; Уолш, Тоби (1998), "Анализ эвристики для чисел Partitioning", вычислительный интеллект, 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
Мертенс, Стефан (2006). «Самая легкая трудная задача: разделение номеров». В Аллоне Перкусе; Габриэль Истрате; Кристофер Мур (ред.). Вычислительная сложность и статистическая физика. США: Издательство Оксфордского университета. С. 125–140. arXiv : cond-mat / 0310317. Bibcode : 2003 second.mat.10317M. ISBN 9780195177374.
Мертенс, Стефан (1999), «Полный алгоритм в любое время для сбалансированного разделения чисел», arXiv : cs / 9903011