Állítsa be a fedési problémát

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. június 28-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A problémahalmaz a számítástechnika és a komplexitáselmélet klasszikus kérdése . Ez a probléma általánosítja az NP-teljes csúcsfedő problémát (és ezért NP-nehéz). Bár a csúcslefedési probléma hasonló ehhez, a közelítő algoritmusban alkalmazott megközelítés itt nem működik. Ehelyett egy mohó algoritmust veszünk figyelembe. Az általa adott megoldás logaritmikusan sokszor rosszabb lesz az optimálisnál. A probléma méretének növekedésével a megoldás minősége romlik, de még mindig meglehetősen lassan, így ez a megközelítés hasznosnak tekinthető.

Problémafelvetés

A halmazfedő probléma kiindulási adata egy véges halmaz és részhalmazainak egy családja . A borító a legkisebb kardinalitású család, melynek uniója . A belépési engedéllyel kapcsolatos kérdés esetén egy pár és egy egész szám kerül megadásra ; a kérdés a kardinalitás (vagy kevesebb) fedőhalmazának megléte. ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {C}}\subseteq {\mathcal {S}}$ ${\mathcal {U}}$ $({\mathcal {U}),{\mathcal {S)))$ $k$ $k$

Példa

Példaként egy halmazt lefedő problémára tekintsük a következő problémát: képzeljük el, hogy egy feladat elvégzéséhez egy bizonyos készségkészletre van szükség . Van egy olyan embercsoport is, akik mindegyike rendelkezik ezekből a képességekből. Meg kell alkotni a feladat elvégzéséhez elegendő legkisebb alcsoportot, azaz. beleértve az összes szükséges készség hordozóit. $S$

Megoldási módszerek

Mohó közelítő algoritmus

A mohó algoritmus a következő szabály szerint választ ki halmazokat: minden szakaszban kiválasztanak egy halmazt, amely lefedi a még le nem fedett elemek maximális számát.

Greedy-Set-Cover(U,F), ahol az összes elem adott halmaza, részhalmazok családja $U$ $F$ $U$

$X\leftarrow U$
$C\leftarrow \varnothing$
while $X\not =\varnothing$ do
1. válassza a legmagasabbat $S\in F$ $\mid X\cap S\mid$
2. $X\leftarrow X\setminus S$
3. ${\displaystyle C\leftarrow C\cup \{S\))$
return $C$

Megmutatható, hogy ez az algoritmus pontossággal működik , ahol a legnagyobb halmaz hatványa, és a harmonikus sorozat első tagjainak összege . $O(H(s))$ $s$ $H(n)$ $n$

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

Más szóval, az algoritmus olyan fedelet talál, amelynek mérete legfeljebb a minimális fedő méretének a mérete. $H(s)$

Feige tétele azt mondja, hogy a halmazlefedési feladathoz nincs közelítő tényezővel rendelkező algoritmus , mert különben az NP komplexitási osztály egyenlő lenne a TIME( ) összetettségi osztállyal. [1] Így a mohó algoritmus a legjobb közelítő algoritmus a halmazlefedési problémára. $(1-\epsilon )\cdot H(n)$ ${\displaystyle n^{O(\log \log n)))$

Van egy szabványos példa, ahol a mohó algoritmus pontosan működik . $\log _{2}(n)/2$

Az univerzum elemekből áll. A halmazok halmaza páronkénti diszjunkt halmazokból áll , amelyeknek a számossága rendre. Két diszjunkt halmaz is létezik , amelyek mindegyike tartalmazza az elemek felét . Egy ilyen halmazon a mohó algoritmus kiválasztja a halmazokat , míg az optimális megoldás a halmazok kiválasztása és A jobb oldali ábrán látható példa hasonló bemeneti adatokra . $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$

Genetikai algoritmus

A genetikai algoritmus egy heurisztikus véletlenszerű keresési módszer, amely egy biológiai populáció evolúciójának szimulációján alapul.

Általános esetben az algoritmus működése során a populációk egymás utáni változása történik, amelyek mindegyike egy fedőcsalád, amelyet populáció egyedeinek nevezünk. A kezdeti sokaság fedőit véletlenszerűen állítjuk össze. A leggyakoribb és legjobban bevált a genetikai algoritmus stacionárius sémája, amelyben a következő populáció csak egy-két új egyeddel tér el az előzőtől. Amikor a jelenlegi populációból új egyedet állítunk össze, a lefedettségek súlyát figyelembe véve, kiválasztunk egy „szülő” egyedpárt , és ezek alapján a keresztezési eljárásban (véletlenszerűen vagy determinisztikusan) egy bizonyos fedezeti halmazt. halmazok alakulnak ki . Ezután egy mutáción megy keresztül , amely után egy egyed épül fel belőle, amely az új populációban a legnagyobb súllyal helyettesíti a borítást. A sokaság bizonyos (meghatározott) számú alkalommal frissül, és az algoritmus eredménye a talált legjobb lefedettség. $J^{\prime },J''$ $J_{x}$

Pontos megoldás

A halmazlefedési feladatot gyakran egészszámú programozási feladatként fogalmazzák meg [2] :

Meg kell találni , ahol egy mátrix, és = 1, ha , és = 0 egyébként; az egyesek vektorát jelöli ; ; egy vektor, ahol , ha benne van a lefedettségben, egyébként . ${\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},\dots ,x_{n})^{T))$ $x_{j}=1$ $S_j$ $x_{j}=0$

A pontos megoldást polinomiális időben kaphatjuk meg, ha a mátrix teljesen unimoduláris . Ez magában foglalja a csúcsok lefedésének problémáját is egy bipartit gráfon és fán . Különösen, ha a mátrix minden oszlopa pontosan két 1-est tartalmaz, a probléma a gráf éllefedési problémájaként fogható fel, ami gyakorlatilag a maximális egyezés megtalálására redukálódik . Azokon a feladatosztályokon, ahol vagy amelyeket konstans határol, a feladatot polinomiális időben, kimerítő felsorolási módszerekkel oldják meg. $A$ $A$ $n$ $m$

Kapcsolódó feladatok

Irodalom

A. V. Eremejev, L. A. Zaozerszkaja, A. A. Kolokolov. A problémát lefedő halmaz: komplexitás, algoritmusok, kísérleti vizsgálatok. A műveletek diszkrét elemzése és kutatása. Ser. 2. 2000. V. 7, N 2. S. 22-46.
Thomas H. Kormen et al. , 16. fejezet Mohó algoritmusok // Algoritmusok: Konstrukció és elemzés = BEVEZETÉS AZ ALGORITMUSOKBA. - 1. kiadás - M .: Moszkvai Matematikai Folyamatos Oktatási Központ, 2001. - S. 889-892. - ISBN 5-900916-37-5 .

Jegyzetek

↑ Uriel Feige. Ln n küszöbérték a fedőkészlet közelítéséhez // Journal of the ACM. - 1998-07. — Vol. 45 , iss. 4 . — P. 634–652 . — ISSN 1557-735X 0004-5411, 1557-735X . - doi : 10.1145/285055.285059 .
↑ A. V. Eremejev, L. A. Zaozerszkaja, A. A. Kolokolov. A PROBLÉMÁT FEDEZŐ BEÁLLÍTÁS: KOMPLEXITÁS, ALGORITMUSOK, KÍSÉRLETI TANULMÁNYOK // DISZKRÉT ELEMZÉS ÉS MŰVELETKUTATÁS. - 2000. - július-december ( 7. köt. 2. szám ). - S. 22-46 . Archiválva az eredetiből 2021. január 25-én.

Linkek

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

NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája	Csomagolás konténerekbe kétdimenziós csomagolás lineáris csomagolás súly szerinti csomagolás érték szerinti csomagolás A hátizsák probléma
gráfelmélet halmazelmélet	Csúcsborítási probléma Kattintson a probléma Egy független halmaz (halmaz) problémája Állítsa be a fedési problémát Steiner probléma Az utazó eladó probléma Általános utazó eladó probléma
Algoritmikus problémák	Kielégíthetőségi probléma Boole-képleteknél (konjunktív normál formában)
Logikai játékok és rejtvények	Általános címkék (játék N 2 -1-ben) legrövidebb megoldási probléma Problémák, amelyek megoldásait a Tetrisben alkalmazzák Általános Sudoku probléma Latin négyzet kitöltési probléma Kakuro feladata
Nehézségi osztályok Operációkutatás Optimalizálás Kombinatorikus optimalizálás Alkalmazott matematika Algoritmusok elmélete Dinamikus programozás 21 NP-teljes Karp probléma