Balicí sady

Sbalování množin je klasickým NP-úplným problémem v teorii výpočetní složitosti a kombinatorice a je jedním z 21 Karpových NP-úplných problémů .

Představte si, že máme konečnou množinu S a seznam podmnožin množiny S . Problém s balením se ptá, zda je v seznamu k podmnožin, které jsou párově nesouvislé.

Formálněji, pokud jsou dány množina a rodina podmnožin množiny , pak je balení podrodinou množin, takže všechny množiny z jsou párově disjunktní a nazývá se velikost balení. V problému řešitelnosti balení je vstupem dvojice a číslo . Otázkou je určit, zda existuje balení velikosti nebo více. V problému optimalizace balení je vstupem pár a úkolem je najít balení pomocí co největšího počtu sad. ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {U}}$ ${\mathcal {C}}\subseteq {\mathcal {S}}$ ${\mathcal {C}}$ $|{\mathcal {C}}|$ $({\mathcal {U}),{\mathcal {S)))$ $k$ $k$ $({\mathcal {U}),{\mathcal {S)))$

Je jasné, že problém patří do NP , protože daných k podmnožin můžeme jednoduše zkontrolovat, že jsou párově disjunktní v polynomiálním čase .

Optimalizační verze problému, maximální sbalení množin , se ptá na maximální počet párově disjunktních množin ze seznamu. Tento problém lze přirozeně formulovat jako celočíselný problém lineárního programování , patří do třídy problémů s balením a jeho problém duálního lineárního programování je problém pokrývající množiny [1] .

Příkaz k problému lineárního programování

Problém nalezení maximálního balení lze formulovat jako následující celočíselný problém lineárního programování .

maximalizovat	$\sum _{S\in {\mathcal {S}}}x_{S}$		(najít maximální sadu podmnožin)
za podmínek	$\sum _{S\dvojtečka e\in S}x_{S}\leqslant 1$	pro všechny $e\in {\mathcal {U}}$	(vybrané sady musí být párově disjunktní)
	$x_{S}\in \{0,1\}$	pro všechny . $S\in {\mathcal {S}}$	(jakákoli sada je buď zabalená, nebo ne)

Příklady

Řekněme, že máte ve své kuchyni sbírku různých potravin ( ) a máte kuchařku se sbírkou receptů ( ). Každý recept vyžaduje určitou sadu produktů. Chcete uvařit maximální počet pokrmů z kuchařky (za předpokladu, že produkt je použit pouze v jednom pokrmu). V tomto případě hledáte sadu balení ( ) podle ( ) - sadu receptů, kde produkt není zahrnut ve dvou různých receptech. ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {C}}$ ${\mathcal {U}}, {\mathcal {S}}$

Jako další příklad si představme setkání zahraničních zástupců, z nichž každý hovoří anglicky a několika dalšími jazyky. Chcete oznámit rozhodnutí nějaké skupině zastupitelů, ale nevěříte jim a nechcete, aby o rozhodnutí diskutovali mezi sebou v jazyce, kterému nerozumíte. Abyste toho dosáhli, vyberete skupinu tak, aby žádní dva zástupci nemluvili jiným jazykem než angličtinou. Na druhou stranu chcete své rozhodnutí sdělit maximálnímu počtu zastupitelů. V tomto případě jsou prvky sady jiné jazyky než angličtina a podmnožiny jsou jazyky, kterými mluví konkrétní zástupci. Pokud se tyto dva soubory nepřekrývají, nemohou zástupci mluvit jiným jazykem než anglicky. Maximální balení vybere největší možný počet zástupců za daných omezení. Ačkoli je problém obecně neřešitelný, v tomto příkladu by dobrou heuristikou bylo vybrat zástupce, kteří mluví jedním jazykem (jiným než angličtinou), takže mnoho dalších nemusí být vyloučeno.

Vážená verze

Existuje vážená verze problému s balením sady, kde je každé podmnožině přiřazena určitá váha (skutečné číslo) a my chceme maximalizovat celkovou hmotnost: $\sum _{S\in {\mathcal {S}}}w(S)\cdot x_{S}$

V prvním příkladu můžeme receptu přiřadit váhu rovnou počtu přátel, kterým jídlo chutná, takže večeře potěší maximální počet přátel.

Zdá se, že váha dělá problém těžší, ale většina známých výsledků pro problém bez závaží platí i pro vážený problém.

Heuristika

Problém balení může být pro některé k obtížný , ale nemusí být obtížné najít k , pro které je pro určité vstupy snadné jej vyřešit. Můžeme například použít greedy algorithm , ve kterém najdeme množinu, která se protíná s nejmenším počtem dalších množin, přidáme ji k řešení a odstraníme množiny, se kterými se protíná. Pokračujeme v tom, dokud existují sady. Dostaneme balíček nějaké velikosti, i když ne nutně maximální velikosti. Ačkoli žádný algoritmus nemůže vždy poskytnout blízko maximálnímu výsledku (viz další část), v mnoha praktických aplikacích dává tento heuristický algoritmus dobré výsledky.

Obtížnost

Nejenže je problém s balením sady NP-úplný, ale ukázalo se, že optimalizační verze je stejně těžko aproximovatelná jako problém maximální kliky . Zejména ji nelze aproximovat žádným konstantním faktorem [2] . Nejznámější algoritmus aproximuje faktorem [3] . Ve stejném rozsahu lze aproximovat i váženou variantu [4] . $O({\sqrt {|U|}})$

Problém má však variantu, která je tvárnější - pokud nepřipustíme, aby podmnožiny měly více než k ≥ 3 prvků, lze odpověď aproximovat faktorem k / 2 + ε pro libovolné ε > 0. problém s 3prvkovými množinami lze aproximovat koeficientem blízkým 50 %. V další poddajnější variantě s podmínkou, že žádný prvek není ve více než k podmnožinách, lze odpověď aproximovat faktorem k . Totéž platí pro váženou verzi.

Ekvivalentní problémy

Mezi problémem nezávislé množiny a problémem sbalení množiny dochází ke zkrácení polynomiálního času jedna ku jedné:

Vzhledem k problému se zabalením množiny na množině vytvoříme graf, ve kterém každá množina představuje vrchol a mezi a pokud a pouze tehdy je oblouk . Nyní každá nezávislá množina vrcholů ve výsledném grafu odpovídá shluku množin v . $\mathcal{S}$ $S\in {\mathcal {S}}$ $v_{S}$ $v_{S}$ $v_{T}$ $S\cap T\neq \phi$ $\mathcal{S}$
Dáme-li za úkol najít nezávislou množinu ve vrcholu grafu , vytvoříme množinu množin, ve kterých každý vrchol odpovídá množině v , obsahující všechny hrany sousedící s . Nyní každé balení ve výsledné množině odpovídá nezávislé množině vrcholů v . $G(V,E)$ $proti$ ${\displaystyle S_{v))$ $proti$ $G(V,E)$

Redukce je dvoucestná redukce PTAS a ukazuje, že oba problémy je stejně obtížné aproximovat.

Zvláštní příležitosti

Párování a 3D párování jsou speciální případy balení sady. Shoda maximální velikosti může být nalezena v polynomiálním čase, ale nalezení největší 3-rozměrné shody nebo největší nezávislé množiny jsou NP-těžké problémy.

Další související úkoly

Balení sady patří do rodiny problémů zakrývání nebo oddělování prvků sady. Jedním ze souvisejících problémů je problém zakrytí sestavy . Zde máme také množinu S a seznam množin, ale úkolem je určit, zda můžeme vybrat k množin, které dohromady obsahují všechny prvky množiny S . Tyto sady se mohou překrývat. Optimalizační verze hledá minimální počet takových sad. Problém maximálního balení nevyžaduje pokrytí všech prvků bez výjimky.

Problém NP-kompletního přesného pokrytí na druhé straně vyžaduje, aby každý prvek byl obsažen v přesně jedné podmnožině. Najít takové přesné pokrytí, bez ohledu na velikost, je NP-úplný úkol.

Karp ukázal NP-úplnost problému s balením sady snížením problému kliky na něj .

Viz také: Balení hypergrafů .

Poznámky

↑ Vazirani, 2001 .
↑ Hazan, Safra, Schwartz, 2006 . Viz zejména str. 21 — "Maximální klik (a tedy maximální nezávislá množina a maximální balení množin) nelze aproximovat, pokud není NP ⊂ ZPP." $O(n^{1-\epsilon })$
↑ Halldórsson, Kratochvíl, Telle, 1998 , str. 176–185.
↑ Halldorsson, 1999 , s. 261–270.

Literatura

Maximální balení sady , Viggo Kann.
„ balení sady “. Slovník algoritmů a datových struktur , editoval Paul E. Black, National Institute of Standards and Technology. Všimněte si, že zde se definice mírně liší.
Stephen S. Skiena. 18.2 Problém skládání množiny // Algoritmy. Průvodce rozvojem. - 2. - Petrohrad: "BHV-Petersburg", 2011. - S. 635-638. - ISBN 978-5-9775-0560-4 .
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger. " Maximální balení sady ". Přehled úloh optimalizace NP .
M. Gary, D. Johnson. Výpočetní stroje a složité problémy. - M .: "Mir", 1982. A3.1: SP3, s.279.
Vidžaj V. Vazirani. Aproximační algoritmy. - Springer-Verlag, 2001. - ISBN 3-540-65367-8 .
Elad Hazan, Shmuel Safra, Oded Schwartz. O složitosti aproximace k -set packingu // Computational Complexity . - 2006. - T. 15 , no. 1 . — S. 20–39 . - doi : 10.1007/s00037-006-0205-6 .
Magnus M. Halldorsson. 5. výroční mezinárodní konference o počítačích a kombinatorice. - Springer-Verlag, 1999. - T. 1627 . — S. 261–270 .

Odkazy

Program Pascal pro řešení problému . Od diskrétních optimalizačních algoritmů s programy Pascal (MacIej M. Syslo, ISBN 0-13-215509-5 ).
Srovnávací testy se skrytými optimálními řešeními pro krytí sady, balení sady a určení vítěze
Řešení problému s balením v PHP

Balicí úkoly
Balící kruhy	V kruhu / v pravoúhlém trojúhelníku / v rovnoramenném pravoúhlém trojúhelníku / ve čtverci Koberec Apollonius Věta o balení kruhu Tammesův problém (na sféře)
Balení balónků	Apolloniev v kouli husté balení kontaktní číslo Sférická hranice balení (Hamming)
Další balíčky	Do kontejnerů Tetraedry Sady
Hádanka	Conway Slotobera - Graatsma