Упаковка комплекта

Упаковка множеств — это классическая NP-полная задача теории сложности вычислений и комбинаторики , а также одна из 21 NP-полной задачи Карпа . Предположим, у вас есть множество S и список подмножеств S конечное . Затем задача упаковки множеств спрашивает, являются ли некоторые k подмножеств в списке попарно непересекающимися (другими словами, никакие два из них не имеют общего элемента).

Более формально, учитывая вселенную ${\mathcal {U}}$ и семья ${\mathcal {S}}$ подмножеств ${\mathcal {U}}$, упаковка — это подсемейство ${\mathcal {C}}\subseteq {\mathcal {S}}$ множеств таких, что все множества в ${\mathcal {C}}$ попарно не пересекаются. Размер упаковки составляет $|{\mathcal {C}}|$. В задаче об упаковке множества входными данными является пара $({\mathcal {U}},{\mathcal {S}})$ и целое число $t$; вопрос в том, является лиесть комплектная упаковка нужного размера $t$ или больше. упаковки наборов В задаче оптимизации входными данными является пара $({\mathcal {U}},{\mathcal {S}})$, и задача состоит в том, чтобы найти упаковку множеств, в которой используется наибольшее количество множеств.

Проблема явно в NP , поскольку, учитывая $t$ подмножеств, мы можем легко проверить, что они попарно не пересекаются за полиномиальное время .

Оптимизационная версия задачи — упаковка максимального набора — требует максимального количества попарно непересекающихся множеств в списке. Это задача максимизации, которую естественным образом можно сформулировать как целочисленную линейную программу , принадлежащую классу задач упаковки .

Формулировка целочисленной линейной программы

Задачу упаковки максимального множества можно сформулировать в виде следующей целочисленной линейной программы .

максимизировать	$\sum _{S\in {\mathcal {S}}}x_{S}$		(максимизировать общее количество подмножеств)
при условии	$\sum _{S\colon e\in S}x_{S}\leqslant 1$	для всех $e\in {\mathcal {U}}$	(выбранные множества должны быть попарно непересекающимися)
	$x_{S}\in \{0,1\}$	для всех $S\in {\mathcal {S}}$.	(каждый комплект либо в комплектной упаковке, либо нет)

Сложность

Задача упаковки множеств не только NP-полна, но ее оптимизационная версия (общая задача упаковки максимального множества) оказалась столь же трудной для аппроксимации, как и задача максимальной клики ; в частности, его нельзя аппроксимировать с точностью до какого-либо постоянного коэффициента. Самый известный алгоритм аппроксимирует его с точностью до коэффициента $O({\sqrt {|U|}})$. Взвешенный вариант также может быть аппроксимирован.

Упаковка наборов ограниченного размера

У проблемы есть более разрешимый вариант. Для любого положительного целого числа k ≥3 k проблема упаковки -множеств представляет собой вариант упаковки множеств, в котором каждый набор содержит не более k элементов.

Когда k =1, проблема тривиальна. Когда k = 2, проблема эквивалентна поиску паросочетания максимальной мощности , которое можно решить за полиномиальное время.

Для любого k ≥3 проблема является NP-сложной, поскольку она более общая, чем трехмерное сопоставление . Однако существуют алгоритмы аппроксимации с постоянным коэффициентом :

• Cygan представил алгоритм, который для любого ε>0 достигает аппроксимации ( k +1+ε)/3. Время выполнения является полиномиальным по количеству множеств и элементов, но дважды экспоненциальным по 1/ε.
• Furer and Yu представил алгоритм, который достигает того же приближения, но с одноэкспонентой времени выполнения от 1/ε.

Упаковочные множества ограниченной степени

В другом, более удобном варианте, если ни один элемент не встречается более чем в d подмножеств, ответ можно аппроксимировать с точностью до d . Это справедливо и для взвешенной версии.

Связанные проблемы

Эквивалентные проблемы

Сопоставление гиперграфов эквивалентно упаковке множеств: множества соответствуют гиперребрам.

Задача независимом множестве о также эквивалентна упаковке множеств — между ними происходит полиномиальное сокращение времени один к одному:

• Учитывая заданную проблему упаковки в коллекции ${\mathcal {S}}$, построим график, где для каждого набора $S\in {\mathcal {S}}$ есть вершина $v_{S}$, и есть грань между $v_{S}$ и $v_{T}$ если только $S\cap T\neq \varnothing$. Каждому независимому набору вершин в сгенерированном графе соответствует упаковка множеств в ${\mathcal {S}}$.
• Дана независимая задача о множестве вершин на графе $G(V,E)$, создайте коллекцию множеств, где для каждой вершины $v$ есть набор $S_{v}$ содержащий все ребра, примыкающие к $v$. Каждая упаковка множеств в сгенерированной коллекции соответствует независимому множеству вершин в $G(V,E)$.

Это также двунаправленное сокращение PTAS , и оно показывает, что обе проблемы одинаково трудно аппроксимировать.

В частном случае, когда каждое множество содержит не более k элементов ( проблема упаковки k-множеств ), граф пересечений ( k +1) -свободен от клешней . Это связано с тем, что если множество пересекает некоторые k +1 множеств, то по крайней мере два из этих множеств пересекаются, поэтому не может быть ( k +1)-клешни. Итак, максимальное независимое множество в графах без когтей можно рассматривать как обобщение максимальной упаковки k -множеств.

Особые случаи

Сопоставление графов — это частный случай упаковки множеств, при котором размер всех множеств равен 2 (множества соответствуют ребрам). В этом особом случае совпадение максимального размера может быть найдено за полиномиальное время.

Трехмерное сопоставление — это частный случай, когда размер всех наборов равен 3, кроме того, элементы разбиты на 3 цвета и каждый набор содержит ровно по одному элементу каждого цвета. Этот частный случай по-прежнему NP-труден, хотя в нем используются лучшие алгоритмы аппроксимации с постоянным коэффициентом, чем в общем случае.

Другие сопутствующие проблемы

В задаче о множестве покрытий нам дано семейство ${\mathcal {S}}$ подмножеств вселенной ${\mathcal {U}}$, и цель состоит в том, чтобы определить, можем ли мы выбрать t наборов, которые вместе содержат каждый элемент ${\mathcal {U}}$. Эти наборы могут перекрываться. Версия оптимизации находит минимальное количество таких наборов. Упаковка максимального комплекта не обязательно должна охватывать все возможные элементы.

В задаче о точном покрытии каждый элемент ${\mathcal {U}}$ должно содержаться ровно в одном из подмножеств. Нахождение такого точного покрытия является NP-полной задачей даже в особом случае, когда размер всех множеств равен 3 (этот особый случай называется точным 3-покрытием или X3C ). Однако если мы создадим одиночный набор для каждого элемента S и добавим их в список, возникшая проблема будет такой же простой, как и упаковка набора.

Первоначально Карп показал NP-полную упаковку множеств посредством редукции задачи о клике .

См. также: Упаковка в гиперграф.

Ссылки

• Упаковка максимального набора , Вигго Канн.
• « набор упаковки ». Словарь алгоритмов и структур данных , редактор Пол Э. Блэк, Национальный институт стандартов и технологий. Обратите внимание, что определение здесь несколько иное.
• Стивен С. Скиена. « Упаковка комплекта ». Руководство по проектированию алгоритмов .
• Пьерлуиджи Крещенци, Вигго Канн, Магнус Халлдорссон, Марек Карпински и Герхард Вегингер . « Упаковка максимального комплекта ». Сборник задач оптимизации NP . Последнее изменение 20 марта 2000 г.
• Майкл Р. Гари и Дэвид С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN  978-0-7167-1045-5 . А3.1: СП3, стр.221.
• Vazirani, Vijay V. (2001). Approximation Algorithms . Springer-Verlag. ISBN  978-3-540-65367-7 .

Внешние ссылки

• [1] : Программа на языке Паскаль для решения проблемы. Из «Алгоритмов дискретной оптимизации с программами на языке Паскаль» , Макей М. Сысло, ISBN   0-13-215509-5 .
• Тесты со скрытыми оптимальными решениями для покрытия сетов, упаковки сетов и определения победителей
• Решение проблемы упаковки в PHP
• Оптимизация трехмерной упаковки в контейнеры