Csomagoló készletek

A halmazcsomagolás egy klasszikus NP-teljes probléma a számítási komplexitáselméletben és a kombinatorikában , és egyike Karp 21 NP-teljes problémájának .

Képzeljük el, hogy van egy véges S halmazunk és az S halmaz részhalmazainak listája . A csomagolási probléma azt kérdezi, hogy van-e k olyan részhalmaz egy listában, amelyek páronként diszjunktak.

Formálisabban, ha egy halmaz és a halmaz részhalmazainak családja adott , akkor a csomagolás a halmazok olyan alcsaládja , amelyben az összes halmaz páronként diszjunkt, és a csomagolás méretének nevezzük. A csomagolási megoldhatósági feladatban a bemenet egy pár és egy szám . A kérdés annak meghatározása, hogy van-e nagyobb vagy nagyobb csomag. A csomagolásoptimalizálási feladatban a bemenet egy pár , és a feladat az, hogy minél több készlet felhasználásával találjunk egy csomagolást. ${\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)))$

Nyilvánvaló, hogy a probléma NP -hez tartozik , mivel adott k részhalmazt egyszerűen ellenőrizhetjük, hogy azok páronként diszjunktak-e polinomidőben .

A probléma optimalizálási változata , a halmazok maximális pakolása felteszi a kérdést, hogy a listából hány páronként diszjunkt halmazok maximális száma. Ez a probléma természetesen egészszámú lineáris programozási feladatként is megfogalmazható, a csomagolási feladatok osztályába tartozik, kettős lineáris programozási problémája pedig halmazfedő feladat [1] .

A lineáris programozási probléma megállapítása

A maximális tömörítés megtalálásának problémája a következő egész lineáris programozási feladatként fogalmazható meg .

maximalizálni	$\sum _{S\in {\mathcal {S}}}x_{S}$		(keresse meg a részhalmazok maximális halmazát)
feltételek mellett	$\sum _{S\colon e\in S}x_{S}\leqslant 1$	mindenkinek $e\in {\mathcal {U}}$	(a kiválasztott halmazoknak páronként diszjunktnak kell lenniük)
	$x_{S}\in \{0,1\}$	mindenkinek . $S\in {\mathcal {S}}$	(bármely készlet be van csomagolva vagy nincs)

Példák

Példaként tegyük fel, hogy van egy gyűjteménye különböző ételekből a konyhájában ( ), és van egy szakácskönyve receptgyűjteményével ( ). Minden recepthez egy bizonyos termékkészlet szükséges. A szakácskönyvből a lehető legtöbb ételt szeretné elkészíteni (feltételezve, hogy a terméket csak egy ételben használják fel). Ebben az esetben egy készletcsomagolást ( ) keres ( ) - olyan receptkészletet, ahol a termék nem szerepel két különböző receptben. ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {C}}$ ${\mathcal {U}},{\mathcal {S}}$

Egy másik példaként képzeljük el a külföldi képviselők találkozóját, akik mindegyike beszél angolul és több más nyelven is. Határozatot szeretne bejelenteni a képviselők valamelyik csoportjának, de nem bízik bennük, és nem akarja, hogy olyan nyelven beszéljék meg a döntést, amelyet Ön nem ért. Ennek eléréséhez úgy kell kiválasztani egy csoportot, hogy két képviselő ne beszéljen az angolon kívül más nyelven. Másrészt döntését a lehető legtöbb képviselőhöz szeretné eljuttatni. Ebben az esetben a halmaz elemei az angoltól eltérő nyelvek, az alhalmazok pedig az egyes képviselők által beszélt nyelvek. Ha a két halmaz nem fedi egymást, a képviselők nem beszélhetnek az angolon kívül más nyelven. A maximális csomagolás a lehető legnagyobb számú képviselőt választja az adott korlátozások mellett. Bár a probléma általában megoldhatatlan, ebben a példában jó heurisztika az lenne, ha olyan képviselőket választanánk ki, akik egyetlen nyelvet beszélnek (az angolon kívül), így nem kell sok mást kizárni.

Súlyozott verzió

A halmazcsomagolási problémának létezik egy súlyozott változata, ahol minden részhalmazhoz hozzá van rendelve valamilyen súly (valós szám), és szeretnénk maximalizálni a teljes súlyt: $\sum _{S\in {\mathcal {S}}}w(S)\cdot x_{S}$

Az első példában olyan súlyt rendelhetünk a recepthez, amely megegyezik az ételt kedvelő barátok számával, így a vacsora a legtöbb barátnak fog tetszeni.

Úgy tűnik, hogy a súly nehezíti a problémát, de a súlyok nélküli probléma ismert eredményeinek többsége a súlyozott problémára is vonatkozik.

Heurisztika

A csomagolási probléma nehéz lehet néhány k esetében, de nem biztos, hogy olyan k -t találni , amelyre bizonyos bemenetek esetén könnyen megoldható. Használhatjuk például a mohó algoritmust , amelyben megkeressük azt a halmazt, amelyik a legkevesebb más halmazzal metszik, hozzáadjuk a megoldáshoz, és eltávolítjuk azokat a halmazokat, amelyekkel metszi. Ugyanezt folytatjuk, amíg vannak készletek. Valamilyen méretű csomagot kapunk, bár nem feltétlenül a maximális méretet. Bár egyetlen algoritmus sem mindig képes a maximális eredmény közelébe adni (lásd a következő részt), sok gyakorlati alkalmazásban ez a heurisztikus algoritmus jó eredményeket ad.

Nehézség

Nem csak a beállított csomagolási probléma NP-teljes, de az optimalizálási verzióról is bebizonyosodott, hogy ugyanolyan nehezen közelíthető meg, mint a maximális kattintás problémájával . Különösen nem közelíthető semmilyen állandó tényezővel [2] . A legismertebb algoritmus egy tényezővel közelít [3] . A súlyozott változat ugyanilyen mértékben közelíthető [4] . $O({\sqrt {|U|}})$

A problémának azonban van egy képlékenyebb változata – ha nem engedjük meg, hogy a részhalmazoknak több mint k ≥ 3 elemük legyen, a válasz k / 2 + ε tényezővel közelíthető bármely ε > 0 esetén. probléma 3 elemű halmazokkal közel 50%-os együtthatóval közelíthető. Egy másik képlékenyebb változatban, azzal a feltétellel, hogy egyetlen elem sem szerepel több mint k részhalmazban, a válasz k faktorral közelíthető . Ugyanez igaz a súlyozott változatra is.

Egyenértékű problémák

A független halmazprobléma és a halmazcsomagolási probléma között egy az egyhez csökken a polinomiális idő :

Adott egy halmazcsomagolási probléma egy halmazon , létrehozunk egy gráfot, amelyben minden halmaz egy csúcsot reprezentál , és van egy ív között , és akkor és csak akkor, ha . Most az eredményül kapott gráf minden független csúcskészlete megfelel a halmazok csomagjának . $\mathcal{S}$ $S\in {\mathcal {S}}$ $v_{S}$ $v_{S}$ $v_{T}$ $S\cap T\neq \phi$ $\mathcal{S}$
Adva azt a feladatot, hogy a gráf egy csúcsában keressünk egy független halmazt, létrehozunk egy halmazhalmazt, amelyben minden csúcs megfelel egy halmaznak -ben , amely tartalmazza az összes szomszédos élt . Most a kapott halmazban minden egyes csomagolás egy független csúcskészletnek felel meg a -ben . $G(V,E)$ $v$ ${\displaystyle S_{v))$ $v$ $G(V,E)$

A redukció egy kétirányú PTAS redukció , és azt mutatja, hogy a két problémát egyformán nehéz közelíteni.

Különleges alkalmak

Az egyeztetés és a 3D illesztés a készletcsomagolás speciális esetei. A maximális méretű illesztés megtalálható polinomidőben, de a legnagyobb 3 dimenziós illesztés vagy a legnagyobb független halmaz megtalálása NP-nehéz feladat.

Egyéb kapcsolódó feladatok

A készletcsomagolás a készlet elemeinek letakarásával vagy szétválasztásával kapcsolatos problémák családjába tartozik. Az egyik kapcsolódó probléma a halmaz lefedésének problémája . Itt is kapunk egy S halmazt és egy halmazlistát, de a kihívás annak meghatározása, hogy választhatunk -e k olyan halmazt, amelyek együtt tartalmazzák S összes elemét . Ezek a készletek átfedhetik egymást. Az optimalizálási verzió a minimális számú ilyen készletet keresi. A maximális csomagolási probléma nem igényli kivétel nélkül az összes elem lefedését.

Az NP-teljes pontos fedő probléma viszont megköveteli, hogy minden elem pontosan egy részhalmazban legyen. Egy ilyen pontos lefedettség megtalálása mérettől függetlenül NP-teljes feladat.

Karp megmutatta a halmazcsomagolási probléma NP-teljességét a klikkprobléma redukálásával .

Lásd még: Hipergráfok csomagolása .

Jegyzetek

↑ Vazirani, 2001 .
↑ Hazan, Safra, Schwartz, 2006 . Lásd különösen a 21. oldalt – "A maximális klikket (és ennélfogva a maximális független halmazt és a halmazok maximális csomagját) nem lehet közelíteni, hacsak NP ⊂ ZPP." $O(n^{1-\epsilon })$
↑ Halldórsson, Kratochvíl, Telle, 1998 , p. 176–185.
↑ Halldorsson, 1999 , p. 261–270.

Irodalom

Maximum Set Packing , Viggo Kann.
" készlet csomagolás ". Dictionary of Algorithms and Data Structures , szerkesztette: Paul E. Black, National Institute of Standards and Technology. Vegye figyelembe, hogy a definíció itt kissé eltér.
Stephen S. Skiena. 18.2 A halmaz egymásra helyezésének problémája // Algoritmusok. Fejlesztési útmutató. - 2. - Szentpétervár: "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ális készletcsomagolás ". Az NP optimalizálási problémák összefoglalója .
M. Gary, D. Johnson. Számítógépek és nehéz problémák. - M. : "Mir", 1982. A3.1: SP3, 279. o.
Vijay V. Vazirani. Közelítő algoritmusok. - Springer-Verlag, 2001. - ISBN 3-540-65367-8 .
Elad Hazan, Shmuel Safra, Oded Schwartz. A k - halmazos tömörítés közelítésének összetettségéről // Computational Complexity . - 2006. - T. 15 , sz. 1 . – S. 20–39 . - doi : 10.1007/s00037-006-0205-6 .
Magnus M. Halldorsson. 5. éves nemzetközi konferencia a számítástechnikáról és a kombinatorikáról. - Springer-Verlag, 1999. - T. 1627 . – S. 261–270 .

Linkek

Pascal program a probléma megoldására . Discrete Optimization Algorithms with Pascal Programs ( MacIej M. Syslo, ISBN 0-13-215509-5 ).
Referenciaértékek rejtett optimális megoldásokkal a készletek lefedésére, a készlet csomagolására és a nyertes meghatározására
Csomagolási probléma megoldása PHP-ben

Csomagolási feladatok
Csomagolási körök	Körben / derékszögű háromszögben / egyenlő szárú derékszögű háromszögben / négyzetben Apollonius szőnyeg Körcsomagolási tétel Tammes probléma (a szférában)
Léggömb csomagolás	Apolloniev egy bálban sűrű csomagolás elérhetőség Gömb alakú csomagolási határ (Hamming)
Egyéb csomagok	A konténerekhez Tetraéder Készletek
Kirakós játék	Conway Slotobera - Graatsma