Комплект упаковки

Упаковка множеств - это классическая NP-полная задача в теории сложности вычислений и комбинаторике и одна из 21 NP-полных задач Карпа .

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

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

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

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

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

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

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

Сложность [ править ]

Проблема упаковки множеств не только NP-полная, но и ее оптимизационная версия (общая задача упаковки максимального множества) оказалась столь же трудной для аппроксимации, как и проблема максимальной клики ; в частности, его нельзя аппроксимировать каким-либо постоянным множителем. ^[1] Самый известный алгоритм приближает его с точностью до множителя . ^[2] Весовой вариант также может быть аппроксимирован. ^[3]${\displaystyle O({\sqrt {|U|}})}$

Однако у проблемы есть вариант, который более разрешим: если мы предположим, что ни одно подмножество не превышает k ≥3 элементов, ответ можно аппроксимировать с точностью до коэффициента k / 2 + ε для любого ε> 0; в частности, проблема с трехэлементными наборами может быть приближена с точностью до 50%. В другом, более гибком варианте, если ни один элемент не встречается более чем в k из подмножеств, ответ можно аппроксимировать с точностью до k . Это также верно для взвешенной версии.

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

Существует взаимно однозначное полиномиальное сведение между задачей независимого множества и проблемой упаковки множеств:

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

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

Особые случаи [ править ]

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

Другие связанные проблемы [ править ]

Упаковка набора - одна из проблем, связанных с закрытием или разделением элементов набора. Одна тесно связанная проблема - проблема набора обложек . Здесь мы также дали множество S и список наборов, но цель состоит в том, чтобы определить , можно ли выбрать K наборы , которые вместе содержат каждый элемент S . Эти наборы могут перекрываться. Версия оптимизации находит минимальное количество таких наборов. Максимально установленная упаковка не обязательно должна охватывать все возможные элементы.

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

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

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

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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