Упаковка множеств

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

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

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

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

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

Формулировка задачи линейного программирования

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

максимизировать	<math>\sum_{S \in \mathcal S} x_S</math>		(найти максимальное множество подмножеств)
при условиях	<math>\sum_{S\colon e \in S} x_S \leqslant 1 </math>	для всех <math>e\in \mathcal U</math>	(выбранные множества должны попарно не пересекаться)
	<math>x_S \in \{0,1\}</math>	для всех <math>S\in \mathcal S</math>.	(любое множество либо в упаковке, либо нет)

Примеры

В качестве примера представим, что на вашей кухне имеется набор различных продуктов (<math>\mathcal{U}</math>), и у вас есть поваренная книга с коллекцией рецептов блюд ( <math>\mathcal{S}</math>). Каждый рецепт требует наличия некоторого набора продуктов. Вы хотите приготовить максимальное количество блюд из поваренной книги (в предположении, что продукт используется только в одном блюде). В этом случае вы ищете упаковку множеств (<math>\mathcal{C}</math>) на (<math>\mathcal{U},\mathcal{S}</math>) – набор рецептов, в котором продукт не входит в два разных рецепта.

В качестве другого примера представим встречу иностранных представителей, каждый из которых говорит на английском и ещё нескольких других языках. Вы хотите объявить некоторое решение некоторой группе представителей, но вы им не доверяете и не хотите, чтобы они обсуждали решение между собой на языке, который вы не понимаете. Чтобы добиться этого, вы выбираете группу таким образом, что никакие два представителя не говорят на языке, отличном от английского. С другой стороны, вы хотите донести ваше решение максимальному количеству представителей. В этом случае элементами множества являются языки, отличные от английского, а подмножества – языки, на которых говорят конкретные представители. Если два множества не пересекаются, представители не могут разговаривать на языке, отличном от английского. Максимальная упаковка выберет наибольшее возможное число представителей при приведённых ограничениях. Хотя задача в общем виде трудноразрешима, в данном примере хорошим эвристическим подходом будет выбор представителей, говорящих на одном языке (отличном от английского), так что не придётся исключить многих других.

Взвешенная версия

Существует взвешенная версия задачи об упаковке множеств, в которой каждому подмножеству приписан некоторый вес (вещественное число) и мы хотим максимизировать суммарный вес: <math>\sum_{S \in \mathcal S} w(S) \cdot x_S</math>

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

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

Эвристика

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

Сложность

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

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

Эквивалентные задачи

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

• Если дана задача упаковки множеств на наборе <math>\mathcal{S}</math>, создаём граф, в котором каждое множество <math>S \in \mathcal{S}</math> представляет вершину <math>v_S</math>, и существует дуга между <math>v_S</math> и <math>v_T</math> тогда и только тогда, когда <math>S \cap T \neq \phi</math>. Теперь каждое независимое множество вершин в полученном графе соответствует упаковке множеств в <math>\mathcal{S}</math>.
• Если дана задача поиска независимого множества вершина графе <math>G(V,E)</math>, создадим набор множеств, в котором каждой вершине <math>v</math> соответствует множество в <math>S_v</math>, содержащее все рёбра, смежные <math>v</math>. Теперь каждая упаковка в полученном наборе соответствует независимому множеству вершин в <math>G(V,E)</math>.

Сведение является двусторонним PTAS-сведением и это показывает, что две задачи одинаково трудно аппроксимировать.

Специальные случаи

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

Другие связанные задачи

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

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

Карп (Karp) показал NP-полноту задачи упаковки множеств путём сведения к ней задачи о клике.

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

Литература

• [www.nada.kth.se/~viggo/wwwcompendium/node144.html Maximum Set Packing], Viggo Kann.
• "[www.nist.gov/dads/HTML/setpacking.html set packing]". Dictionary of Algorithms and Data Structures, Редактор Paul E. Black, National Institute of Standards and Technology. Заметьте, что определение здесь несколько отличается.
• Стивен С. Скиена. 18.2 Задача укладки множества // Алгоритмы. Руководство по разработке. — 2. — Санкт-Петербург: «БХВ-Петербург», 2011. — С. 635-638. — ISBN 978-5-9775-0560-4.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger. "[www.nada.kth.se/~viggo/wwwcompendium/node144.html Maximum Set Packing]". [www.nada.kth.se/%7Eviggo/wwwcompendium/ A compendium of NP optimization problems].
• М.Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. — М.: «Мир», 1982. A3.1: SP3, стр.279.
• Vijay V. Vazirani. Approximation Algorithms. — Springer-Verlag, 2003. — ISBN 3-540-65367-8.
• Elad Hazan, Shmuel Safra, Oded Schwartz On the complexity of approximating k-set packing // Computational Complexity. — 2006. — Т. 15, вып. 1. — С. 20–39. — DOI:10.1007/s00037-006-0205-6.
• Magnus M. Halldórsson, Jan Kratochvíl, Jan Arne Telle 25th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1998. — Т. 1443. — С. 176–185.
• Magnus M. Halldórsson 5th Annual International Conference on Computing and Combinatorics. — Springer-Verlag, 1999. — Т. 1627. — С. 261–270.

Ссылки

• [www.cs.sunysb.edu/~algorith/implement/syslo/implement.shtml Программа на Паскале для решения задачи]. Из книги Discrete Optimization Algorithms with Pascal Programs (MacIej M. Syslo, ISBN 0-13-215509-5).
• [www.nlsde.buaa.edu.cn/~kexu/benchmarks/set-benchmarks.htm Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination]
• [www.phpqa.in/2010/10/solving-packaging-problem-in-php.html Solving packaging problem in PHP]

Отрывок, характеризующий Упаковка множеств

Господа! Кто хочет со мною пари? Я то же сделаю, – вдруг крикнул он. – И пари не нужно, вот что. Вели дать бутылку. Я сделаю… вели дать.
– Пускай, пускай! – сказал Долохов, улыбаясь.
– Что ты? с ума сошел? Кто тебя пустит? У тебя и на лестнице голова кружится, – заговорили с разных сторон.
– Я выпью, давай бутылку рому! – закричал Пьер, решительным и пьяным жестом ударяя по столу, и полез в окно.
Его схватили за руки; но он был так силен, что далеко оттолкнул того, кто приблизился к нему.
– Нет, его так не уломаешь ни за что, – говорил Анатоль, – постойте, я его обману. Послушай, я с тобой держу пари, но завтра, а теперь мы все едем к***.
– Едем, – закричал Пьер, – едем!… И Мишку с собой берем…
И он ухватил медведя, и, обняв и подняв его, стал кружиться с ним по комнате.


Князь Василий исполнил обещание, данное на вечере у Анны Павловны княгине Друбецкой, просившей его о своем единственном сыне Борисе. О нем было доложено государю, и, не в пример другим, он был переведен в гвардию Семеновского полка прапорщиком. Но адъютантом или состоящим при Кутузове Борис так и не был назначен, несмотря на все хлопоты и происки Анны Михайловны. Вскоре после вечера Анны Павловны Анна Михайловна вернулась в Москву, прямо к своим богатым родственникам Ростовым, у которых она стояла в Москве и у которых с детства воспитывался и годами живал ее обожаемый Боренька, только что произведенный в армейские и тотчас же переведенный в гвардейские прапорщики. Гвардия уже вышла из Петербурга 10 го августа, и сын, оставшийся для обмундирования в Москве, должен был догнать ее по дороге в Радзивилов.
У Ростовых были именинницы Натальи, мать и меньшая дочь. С утра, не переставая, подъезжали и отъезжали цуги, подвозившие поздравителей к большому, всей Москве известному дому графини Ростовой на Поварской. Графиня с красивой старшею дочерью и гостями, не перестававшими сменять один другого, сидели в гостиной.
Графиня была женщина с восточным типом худого лица, лет сорока пяти, видимо изнуренная детьми, которых у ней было двенадцать человек. Медлительность ее движений и говора, происходившая от слабости сил, придавала ей значительный вид, внушавший уважение. Княгиня Анна Михайловна Друбецкая, как домашний человек, сидела тут же, помогая в деле принимания и занимания разговором гостей. Молодежь была в задних комнатах, не находя нужным участвовать в приеме визитов. Граф встречал и провожал гостей, приглашая всех к обеду.
«Очень, очень вам благодарен, ma chere или mon cher [моя дорогая или мой дорогой] (ma сherе или mon cher он говорил всем без исключения, без малейших оттенков как выше, так и ниже его стоявшим людям) за себя и за дорогих именинниц. Смотрите же, приезжайте обедать. Вы меня обидите, mon cher. Душевно прошу вас от всего семейства, ma chere». Эти слова с одинаковым выражением на полном веселом и чисто выбритом лице и с одинаково крепким пожатием руки и повторяемыми короткими поклонами говорил он всем без исключения и изменения. Проводив одного гостя, граф возвращался к тому или той, которые еще были в гостиной; придвинув кресла и с видом человека, любящего и умеющего пожить, молодецки расставив ноги и положив на колена руки, он значительно покачивался, предлагал догадки о погоде, советовался о здоровье, иногда на русском, иногда на очень дурном, но самоуверенном французском языке, и снова с видом усталого, но твердого в исполнении обязанности человека шел провожать, оправляя редкие седые волосы на лысине, и опять звал обедать. Иногда, возвращаясь из передней, он заходил через цветочную и официантскую в большую мраморную залу, где накрывали стол на восемьдесят кувертов, и, глядя на официантов, носивших серебро и фарфор, расставлявших столы и развертывавших камчатные скатерти, подзывал к себе Дмитрия Васильевича, дворянина, занимавшегося всеми его делами, и говорил: «Ну, ну, Митенька, смотри, чтоб всё было хорошо. Так, так, – говорил он, с удовольствием оглядывая огромный раздвинутый стол. – Главное – сервировка. То то…» И он уходил, самодовольно вздыхая, опять в гостиную.
– Марья Львовна Карагина с дочерью! – басом доложил огромный графинин выездной лакей, входя в двери гостиной.
Графиня подумала и понюхала из золотой табакерки с портретом мужа.
– Замучили меня эти визиты, – сказала она. – Ну, уж ее последнюю приму. Чопорна очень. Проси, – сказала она лакею грустным голосом, как будто говорила: «ну, уж добивайте!»
Высокая, полная, с гордым видом дама с круглолицей улыбающейся дочкой, шумя платьями, вошли в гостиную.
«Chere comtesse, il y a si longtemps… elle a ete alitee la pauvre enfant… au bal des Razoumowsky… et la comtesse Apraksine… j'ai ete si heureuse…» [Дорогая графиня, как давно… она должна была пролежать в постеле, бедное дитя… на балу у Разумовских… и графиня Апраксина… была так счастлива…] послышались оживленные женские голоса, перебивая один другой и сливаясь с шумом платьев и передвиганием стульев. Начался тот разговор, который затевают ровно настолько, чтобы при первой паузе встать, зашуметь платьями, проговорить: «Je suis bien charmee; la sante de maman… et la comtesse Apraksine» [Я в восхищении; здоровье мамы… и графиня Апраксина] и, опять зашумев платьями, пройти в переднюю, надеть шубу или плащ и уехать. Разговор зашел о главной городской новости того времени – о болезни известного богача и красавца Екатерининского времени старого графа Безухого и о его незаконном сыне Пьере, который так неприлично вел себя на вечере у Анны Павловны Шерер.
– Я очень жалею бедного графа, – проговорила гостья, – здоровье его и так плохо, а теперь это огорченье от сына, это его убьет!
– Что такое? – спросила графиня, как будто не зная, о чем говорит гостья, хотя она раз пятнадцать уже слышала причину огорчения графа Безухого.
– Вот нынешнее воспитание! Еще за границей, – проговорила гостья, – этот молодой человек предоставлен был самому себе, и теперь в Петербурге, говорят, он такие ужасы наделал, что его с полицией выслали оттуда.
– Скажите! – сказала графиня.
– Он дурно выбирал свои знакомства, – вмешалась княгиня Анна Михайловна. – Сын князя Василия, он и один Долохов, они, говорят, Бог знает что делали. И оба пострадали. Долохов разжалован в солдаты, а сын Безухого выслан в Москву. Анатоля Курагина – того отец как то замял. Но выслали таки из Петербурга.
– Да что, бишь, они сделали? – спросила графиня.
– Это совершенные разбойники, особенно Долохов, – говорила гостья. – Он сын Марьи Ивановны Долоховой, такой почтенной дамы, и что же? Можете себе представить: они втроем достали где то медведя, посадили с собой в карету и повезли к актрисам. Прибежала полиция их унимать. Они поймали квартального и привязали его спина со спиной к медведю и пустили медведя в Мойку; медведь плавает, а квартальный на нем.
– Хороша, ma chere, фигура квартального, – закричал граф, помирая со смеху.
– Ах, ужас какой! Чему тут смеяться, граф?
Но дамы невольно смеялись и сами.
– Насилу спасли этого несчастного, – продолжала гостья. – И это сын графа Кирилла Владимировича Безухова так умно забавляется! – прибавила она. – А говорили, что так хорошо воспитан и умен. Вот всё воспитание заграничное куда довело. Надеюсь, что здесь его никто не примет, несмотря на его богатство. Мне хотели его представить. Я решительно отказалась: у меня дочери.
– Отчего вы говорите, что этот молодой человек так богат? – спросила графиня, нагибаясь от девиц, которые тотчас же сделали вид, что не слушают. – Ведь у него только незаконные дети. Кажется… и Пьер незаконный.
Гостья махнула рукой.
– У него их двадцать незаконных, я думаю.
Княгиня Анна Михайловна вмешалась в разговор, видимо, желая выказать свои связи и свое знание всех светских обстоятельств.
– Вот в чем дело, – сказала она значительно и тоже полушопотом. – Репутация графа Кирилла Владимировича известна… Детям своим он и счет потерял, но этот Пьер любимый был.
– Как старик был хорош, – сказала графиня, – еще прошлого года! Красивее мужчины я не видывала.
– Теперь очень переменился, – сказала Анна Михайловна. – Так я хотела сказать, – продолжала она, – по жене прямой наследник всего именья князь Василий, но Пьера отец очень любил, занимался его воспитанием и писал государю… так что никто не знает, ежели он умрет (он так плох, что этого ждут каждую минуту, и Lorrain приехал из Петербурга), кому достанется это огромное состояние, Пьеру или князю Василию. Сорок тысяч душ и миллионы. Я это очень хорошо знаю, потому что мне сам князь Василий это говорил. Да и Кирилл Владимирович мне приходится троюродным дядей по матери. Он и крестил Борю, – прибавила она, как будто не приписывая этому обстоятельству никакого значения.
– Князь Василий приехал в Москву вчера. Он едет на ревизию, мне говорили, – сказала гостья.
– Да, но, entre nous, [между нами,] – сказала княгиня, – это предлог, он приехал собственно к графу Кирилле Владимировичу, узнав, что он так плох.
– Однако, ma chere, это славная штука, – сказал граф и, заметив, что старшая гостья его не слушала, обратился уже к барышням. – Хороша фигура была у квартального, я воображаю.
И он, представив, как махал руками квартальный, опять захохотал звучным и басистым смехом, колебавшим всё его полное тело, как смеются люди, всегда хорошо евшие и особенно пившие. – Так, пожалуйста же, обедать к нам, – сказал он.


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