Nastavit problém s krytím

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. června 2022; ověření vyžaduje 1 úpravu .

Problém pokrývající množinu je klasickou otázkou v informatice a teorii složitosti . Tento problém zobecňuje problém NP -úplného vertexového pokrytí (a proto je NP-obtížný). Ačkoli je problém pokrytí vrcholů podobný tomuto, přístup použitý v přibližném algoritmu zde nefunguje. Místo toho budeme uvažovat o chamtivém algoritmu. Jím dané řešení bude o logaritmický počet horší než optimální. Jak velikost problému roste, kvalita řešení se zhoršuje, ale stále spíše pomalu, takže tento přístup lze považovat za užitečný.

Problémové prohlášení

Počáteční data problému pokrývajícího množinu jsou konečná množina a rodina jejích podmnožin. Kryt je rodina nejmenší mohutnosti, jejíž spojení je . V případě dotazu na povolení vstupu se uvádí dvojice a celé číslo ; otázkou je existence krycího souboru mohutnosti (nebo méně). ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {C}}\subseteq {\mathcal {S}}$ ${\mathcal {U}}$ $({\mathcal {U}),{\mathcal {S)))$ $k$ $k$

Příklad

Jako příklad problému zakrývání množiny zvažte následující problém: představte si, že k dokončení úkolu je vyžadována určitá sada dovedností . Existuje také skupina lidí, z nichž každý má některé z těchto dovedností. Pro splnění úkolu je nutné vytvořit co nejmenší podskupinu, tzn. včetně nositelů všech potřebných dovedností. $S$

Metody řešení

Greedy přibližný algoritmus

Chamtivý algoritmus vybírá množiny podle následujícího pravidla: v každé fázi je vybrána množina, která pokrývá maximální počet dosud nepokrytých prvků.

Greedy-Set-Cover(U,F), kde je daná množina všech prvků, je rodina podmnožin $U$ $F$ $U$

$X\leftarrow U$
$C\leftarrow \varnothing$
while $X\not =\varnothing$ do
1. vybrat s nejvyšší $S\in F$ $\mid X\cap S\mid$
2. $X\leftarrow X\setminus S$
3. $C\leftarrow C\cup \{S\}$
return $C$

Lze ukázat, že tento algoritmus pracuje s přesností , kde je mocnina největší množiny a je součtem prvních členů harmonické řady. $O(H(s)}$ $s$ $H(n)$ $n$

H(n)=\sum _{k=1}^{n}{\frac {1}{k))\leq \ln {n}+1

Jinými slovy, algoritmus najde kryt, jehož velikost je maximálně násobkem velikosti minimálního krytu. $H(s)$

Feigeho teorém říká , že pro problém pokrytí množin neexistuje žádný algoritmus s aproximačním faktorem , protože jinak by se třída složitosti NP rovnala třídě složitosti TIME( ). [1] Chamtivý algoritmus je tedy nejlepším aproximačním algoritmem pro problém pokrytí množiny. $(1-\epsilon )\cdot H(n)$ ${\displaystyle n^{O(\log \log n)))$

Existuje standardní příklad, kdy chamtivý algoritmus pracuje s přesností . $\log _{2}(n)/2$

Vesmír se skládá z prvků. Množina množin se skládá z párových disjunktních množin , jejichž mohutnosti jsou resp. Existují také dvě disjunktní sady , z nichž každá obsahuje polovinu prvků z každé . Na takové množině vybírá chamtivý algoritmus množiny , přičemž optimálním řešením je volba množin a Příklad podobných vstupních dat pro je vidět na obrázku vpravo. $n=2^{(k+1)}-2$ $k$ ${\displaystyle S_{1},\ldots ,S_{k))$ ${\displaystyle 2,4,8,\ldots ,2^{k))$ $T_{0},T_{1}$ $S_{i}$ ${\displaystyle S_{k},\ldots ,S_{1))$ $T_{0}$ $T_{1}$ $k=3$

Genetický algoritmus

Genetický algoritmus je heuristická metoda náhodného vyhledávání založená na principu simulace vývoje biologické populace.

V obecném případě během činnosti algoritmu dochází k postupné změně populací, z nichž každá je rodinou obalů, nazývaných jednotlivci populace. Kryty počáteční populace jsou konstruovány náhodně. Nejběžnější a nejlépe osvědčené je stacionární schéma genetického algoritmu, ve kterém se následující populace liší od předchozí pouze jedním nebo dvěma novými jedinci. Při konstrukci nového jedince ze současné populace se s přihlédnutím k vahám krytí vybere „rodičovský“ pár jedinců a na jejich základě se v proceduře překřížení (náhodně nebo deterministicky) určí určitá množina krytí. se tvoří sady . Poté projde mutací , po které je z ní postaven jedinec, který v nové populaci nahradí obal s největší hmotností. Populace je aktualizována určitým (zadaným) počtem opakování a výsledkem algoritmu je nejlepší nalezené pokrytí. $J^{\prime },J''$ $J_{x}$

Přesné řešení

Problém pokrytí množin je často formulován jako problém celočíselného programování [2] :

Je požadováno najít , kde je matice a = 1 pokud , a = 0 jinak; označuje vektor jednotek; ; je vektor, kde , pokud je zahrnuto v pokrytí, jinak . ${\displaystyle f^{*}(c,A)=\min\{(c,x)|Ax\geq e,x\in \{0,1\}^{n}\))$ $A$ $(m\times n)$ $a_{{ij}}$ ${\displaystyle i\in S_{j))$ $a_{{ij}}$ $E$ $m$ ${\displaystyle c=(c_{1},c_{2},\dots ,c_{n})^{T))$ ${\displaystyle x=(x_{1},x_{2},\tečky ,x_{n})^{T))$ $x_{j}=1$ $S_j$ $x_{j}=0$

Přesné řešení lze získat v polynomiálním čase, pokud je matice zcela unimodulární . To také zahrnuje problém pokrytí vrcholů na bipartitním grafu a stromu . Konkrétně, když každý sloupec matice obsahuje přesně dvě jedničky, lze na problém nahlížet jako na problém pokrývající hrany grafu, který se efektivně redukuje na nalezení maximální shody . Na třídách problémů, kde nebo jsou ohraničeny konstantou, se problém řeší v polynomiálním čase vyčerpávajícími výčtovými metodami. $A$ $A$ $n$ $m$

Související úkoly

Literatura

A. V. Eremejev, L. A. Zaozerskaya, A. A. Kolokolov. Soubor pokrývající problém: složitost, algoritmy, experimentální studie. Diskrétní analýza a výzkum operací. Ser. 2. 2000. V. 7, N 2. S. 22-46.
Thomas H. Kormen a kol., Kapitola 16 Greedy Algorithms // Algorithms: Construction and Analysis = ÚVOD DO ALGORITHMŮ. - 1. vyd. - M .: Moskevské centrum pro kontinuální matematické vzdělávání, 2001. - S. 889-892. - ISBN 5-900916-37-5 .

Poznámky

↑ Uriel Feige. Prahová hodnota ln n pro přibližné pokrytí sady // Žurnál ACM. - 1998-07. — Sv. 45 , iss. 4 . — S. 634–652 . — ISSN 1557-735X 0004-5411, 1557-735X . - doi : 10.1145/285055.285059 .
↑ A. V. Eremejev, L. A. Zaozerskaja, A. A. Kolokolov. SET KRYCÍ PROBLÉM: SLOŽITOST, ALGORITMY, EXPERIMENTÁLNÍ STUDIE // DISKRÉTNÍ ANALÝZA A OPERAČNÍ VÝZKUM. - 2000. - červenec-prosinec ( 7. díl , č. 2 ). - S. 22-46 . Archivováno z originálu 25. ledna 2021.

Odkazy

Srovnávací testy se skrytými optimálními řešeními pro krytí sady, balení sady a určení vítěze

NP-úplné problémy
Maximalizační problém stohování (balení)	Balení v kontejnerech dvourozměrné balení lineární balení balení podle hmotnosti balení podle hodnoty Problém s batohem
teorie grafů teorie množin	Problém s krytím vertexu Klikněte na problém Problém nezávislé množiny (množiny) Nastavit problém s krytím Steinerův problém Problém cestujícího prodejce Obecný problém cestujícího prodejce
Algoritmické problémy	Problém splnitelnosti pro booleovské vzorce (v konjunktivní normální formě)
Logické hry a hádanky	Generalizované značky (hra v N 2 -1) problém s nejkratším řešením Problémy, jejichž řešení jsou aplikována v Tetrisu Generalizovaný problém sudoku Problém vyplňování latinského čtverce Kakurův úkol
Třídy obtížnosti Operační výzkum Optimalizace Kombinatorická optimalizace Aplikovaná matematika Teorie algoritmů Dynamické programování 21 NP-úplný Karp problém