Pakkaussarjat

Joukkopakkaus on klassinen NP-täydellinen ongelma laskennallisen monimutkaisuuden teoriassa ja kombinatoriikassa , ja se on yksi Karpin 21:stä NP-täydestä tehtävästä .

Kuvittele, että meillä on äärellinen joukko S ja lista joukon S osajoukoista . Pakkausongelma kysyy, onko luettelossa k osajoukkoa, jotka ovat pareittain hajallaan.

Muodollisemmin, jos joukko ja joukon osajoukkojen perhe annetaan , pakkaus on joukkojen alaperhe siten, että kaikki joukot alkaen ovat pareittain hajallaan, ja sitä kutsutaan pakkauksen kooksi. Pakkauksen ratkaistavuusongelmassa syöte on pari ja luku . Kysymys on selvittää, onko paketissa kokoa tai enemmän. Pakkauksen optimointitehtävässä syöte on pari ja tehtävänä on löytää pakkaus käyttämällä mahdollisimman montaa joukkoa. ${\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)))$

On selvää, että ongelma kuuluu NP :lle , koska annettuna k osajoukkoa voidaan yksinkertaisesti tarkistaa, että ne ovat pareittain disjunktia polynomiajassa .

Tehtävän optimointiversio , joukkojen maksimipakkaus , kysyy listan parikohtaisten disjunktioiden enimmäismäärästä. Tämä ongelma voidaan luonnollisesti muotoilla lineaariseksi kokonaislukuohjelmointitehtäväksi , se kuuluu pakkaustehtävien luokkaan ja sen kaksoislineaarinen ohjelmointitehtävä on joukkopeittotehtävä [1] .

Lineaarisen ohjelmointiongelman lausunto

Maksimipakkauksen löytämisen ongelma voidaan muotoilla seuraavaksi lineaariseksi kokonaislukuohjelmointitehtäväksi .

maksimoida	$\sum _{S\in {\mathcal {S}}}x_{S}$		(etsi suurin osajoukko)
olosuhteissa	$\sum _{S\colon e\in S}x_{S}\leqslant 1$	kaikille $e\in {\mathcal {U}}$	(valittujen sarjojen on oltava pareittain erillään)
	$x_{S}\in \{0,1\}$	kaikille . $S\in {\mathcal {S}}$	(jokainen sarja on joko pakattu tai ei)

Esimerkkejä

Oletetaan esimerkiksi, että sinulla on keittiössäsi kokoelma erilaisia ruokia ( ) ja sinulla on keittokirja, jossa on kokoelma reseptejä ( ). Jokainen resepti vaatii tietyn sarjan tuotteita. Haluat valmistaa keittokirjan enimmäismäärän ruokia (olettaen, että tuotetta käytetään vain yhdessä ruoassa). Tässä tapauksessa etsit sarjapakkausta ( ) by ( ) - reseptisarjaa, jossa tuote ei sisälly kahteen eri reseptiin. ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {C}}$ ${\mathcal {U}},{\mathcal {S}}$

Toisena esimerkkinä kuvitellaan ulkomaisten edustajien kokous, joista jokainen puhuu englantia ja useita muita kieliä. Haluat ilmoittaa päätöksestä jollekin edustajaryhmälle, mutta et luota heihin etkä halua heidän keskustelevan päätöksestä keskenään kielellä, jota et ymmärrä. Tämän saavuttamiseksi valitset ryhmän siten, että kaksi edustajaa ei puhu muuta kieltä kuin englantia. Toisaalta haluat välittää päätöksesi mahdollisimman suurelle määrälle edustajia. Tässä tapauksessa joukon elementit ovat muita kieliä kuin englanti, ja osajoukot ovat kieliä, joita tietyt edustajat puhuvat. Jos nämä kaksi ryhmää eivät mene päällekkäin, edustajat eivät voi puhua muuta kieltä kuin englantia. Maksimipakkaus valitsee suurimman mahdollisen määrän edustajia annettujen rajoitusten mukaisesti. Vaikka ongelma on yleensä käsittämätön, tässä esimerkissä hyvä heuristiikka olisi valita edustajat, jotka puhuvat yhtä kieltä (muuta kuin englantia), jotta monia muita ei tarvitse sulkea pois.

Painotettu versio

Joukon pakkausongelmasta on painotettu versio, jossa jokaiselle osajoukolle on määritetty paino (reaaliluku) ja haluamme maksimoida kokonaispainon: $\sum _{S\in {\mathcal {S}}}w(S)\cdot x_{S}$

Ensimmäisessä esimerkissä voimme antaa reseptille painon, joka vastaa ruoasta pivien ystävien määrää, jotta illallinen miellyttää maksimimäärää ystäviä.

Paino näyttää vaikeuttavan ongelmaa, mutta suurin osa tunnetuista tuloksista ongelmalle ilman painoja pätee myös painotettuun ongelmaan.

Heuristiikka

Pakkausongelma voi olla vaikea jollekin k :lle , mutta ei välttämättä ole vaikea löytää k :tä , joka on helppo ratkaista tietyille syötteille. Voimme esimerkiksi käyttää ahnealgoritmia , jossa etsimme joukon, joka leikkaa vähiten muita joukkoja, lisäämme sen ratkaisuun ja poistamme joukot, joiden kanssa se leikkaa. Jatkamme samaa niin kauan kuin sarjoja riittää. Saamme jonkin kokoisen paketin, vaikka ei välttämättä maksimikokoa. Vaikka mikään algoritmi ei voi aina antaa lähelle maksimitulosta (katso seuraava osa), monissa käytännön sovelluksissa tämä heuristinen algoritmi antaa hyviä tuloksia.

Vaikeus

Paitsi joukon pakkausongelma NP-täydellinen, optimointiversio on osoittautunut yhtä vaikeaksi arvioida kuin maksimiklikkiongelma . Erityisesti sitä ei voida approksimoida millään vakiokertoimella [2] . Tunnetuin algoritmi approkimoi kertoimella [3] . Painotettu muunnos voidaan approksimoida samassa määrin [4] . $O({\sqrt {|U|}})$

Ongelmalla on kuitenkin muunnelma, joka on muokattavampi - jos emme salli osajoukoissa olla enemmän kuin k ≥ 3 alkiota, vastaus voidaan approksimoida kertoimella k / 2 + ε mille tahansa ε > 0:lle. 3-elementtijoukkojen ongelma voidaan approksimoida kertoimella, joka on lähellä 50%. Toisessa muokattavammassa muunnelmassa, sillä ehdolla, että mikään alkio ei ole useammassa kuin k osajoukossa, vastaus voidaan approksimoida tekijällä k . Sama pätee painotettuun versioon.

Vastaavat ongelmat

Itsenäisen joukkotehtävän ja joukon pakkausongelman välillä on yksi yhteen lyheneminen :

Kun joukossa on joukon pakkausongelma , luomme graafin, jossa jokainen joukko edustaa kärkeä ja välillä on kaari ja jos ja vain jos . Nyt jokainen riippumaton kärkijoukko tuloksena olevassa graafissa vastaa joukkojen pakkausta . $\mathcal{S}$ $S\in {\mathcal {S}}$ $v_{S}$ $v_{S}$ $v_{T}$ $S\cap T\neq \phi$ $\mathcal{S}$
Koska tehtävänä on löytää itsenäinen joukko graafin kärjestä , luomme joukon joukkoja, joissa jokainen kärki vastaa joukkoa kohdassa , joka sisältää kaikki :n vieressä olevat reunat . Nyt jokainen tuloksena olevan joukon pakkaus vastaa riippumatonta kärkijoukkoa kohdassa . $G(V,E)$ $v$ ${\displaystyle S_{v))$ $v$ $G(V,E)$

Pelkistys on kaksisuuntainen PTAS-vähennys ja se osoittaa, että näitä kahta ongelmaa on yhtä vaikea arvioida.

Erikoistilaisuudet

Matching ja 3D matching ovat sarjapakkauksen erikoistapauksia. Maksimikoon vastaavuus löytyy polynomiajasta, mutta suurimman 3-ulotteisen sovituksen tai suurimman riippumattoman joukon löytäminen on NP-kovia ongelmia.

Muut asiaan liittyvät tehtävät

Sarjan pakkaus kuuluu sarjan osien peittämiseen tai erottamiseen liittyvien ongelmien perheeseen. Yksi asiaan liittyvistä ongelmista on sarjan peittämisongelma . Tässä annetaan myös joukko S ja joukko joukkoja, mutta haasteena on määrittää, voimmeko valita k joukkoa, jotka yhdessä sisältävät kaikki S :n alkiot . Nämä sarjat voivat olla päällekkäisiä. Optimointiversio etsii tällaisten sarjojen vähimmäismäärää. Maksimipakkausongelma ei edellytä kaikkien elementtien peittämistä poikkeuksetta.

NP-täydellinen tarkka kattavuus -tehtävä puolestaan edellyttää, että jokainen elementti sisältyy täsmälleen yhteen osajoukkoon. Tällaisen tarkan kattavuuden löytäminen koosta riippumatta on NP-täydellinen tehtävä.

Karp osoitti joukon pakkausongelman NP-täydellisyyden vähentämällä siihen klikkiongelman .

Katso myös: Hypergraafien pakkaukset .

Muistiinpanot

↑ Vazirani, 2001 .
↑ Hazan, Safra, Schwartz, 2006 . Katso erityisesti s. 21 — "Maksimaalista klikkia (ja siten maksimaalista riippumatonta joukkoa ja maksimaalista joukkojen pakkausta) ei voida approksimoida ellei NP ⊂ ZPP." $O(n^{1-\epsilon })$
↑ Halldórsson, Kratochvíl, Telle, 1998 , s. 176-185.
↑ Halldorsson, 1999 , s. 261-270.

Kirjallisuus

Maksimisarjan pakkaus , Viggo Kann.
" asettaa pakkaus ". Algoritmien ja tietorakenteiden sanakirja , toimittanut Paul E. Black, National Institute of Standards and Technology. Huomaa, että määritelmä tässä on hieman erilainen.
Stephen S. Skiena. 18.2 Joukon pinoamisen ongelma // Algoritmit. Kehittämisopas. - 2. - Pietari: "BHV-Petersburg", 2011. - S. 635-638. - ISBN 978-5-9775-0560-4 .
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger. " Enimmäissarjan pakkaus ". Kokoelma NP-optimointiongelmista .
M. Gary, D. Johnson. Laskentakoneet ja vaikeita ongelmia. - M .: "Mir", 1982. A3.1: SP3, s. 279.
Vijay V. Vazirani. Approksimaatioalgoritmit. - Springer-Verlag, 2001. - ISBN 3-540-65367-8 .
Elad Hazan, Shmuel Safra, Oded Schwartz. K -joukon pakkaamisen approksimoinnin monimutkaisuudesta // Computational Complexity . - 2006. - T. 15 , no. 1 . - S. 20-39 . - doi : 10.1007/s00037-006-0205-6 .
Magnus M. Halldorsson. 5. vuotuinen kansainvälinen tietojenkäsittely- ja kombinatoriikkakonferenssi. - Springer-Verlag, 1999. - T. 1627 . — S. 261–270 .

Linkit

Pascal-ohjelma ongelman ratkaisemiseksi . Julkaisusta Discrete Optimization Algorithms with Pascal-ohjelmat ( MacIej M. Syslo, ISBN 0-13-215509-5 ).
Vertailuarvot piilotetuilla optimaalisilla ratkaisuilla sarjan peittämiseen, pakkaamiseen ja voittajan määrittämiseen
Pakkausongelman ratkaiseminen PHP:llä

Pakkaustehtävät
Pakkaa ympyrät	Ympyrässä / suorakulmaisessa kolmiossa / tasakylkisessä suorakulmaisessa kolmiossa / neliössä Apolloniuksen matto Ympyräpakkauslause Tammes -ongelma (sfäärillä)
Ilmapallon pakkaus	Apolloniev pallossa tiheä pakkaus yhteysnumero Pallomainen pakkausraja (Hamming)
Muut paketit	Konteihin Tetrahedra Sarjat
Palapeli	Conway Slotobera - Graatsma