Setați problema acoperirii

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 28 iunie 2022; verificarea necesită 1 editare .

Problema acoperirii multimii este o intrebare clasica in informatica si teoria complexitatii . Această problemă generalizează problema acoperirii nodurilor NP-complete (și, prin urmare, este NP-hard). Deși problema acoperirii vârfurilor este similară cu aceasta, abordarea utilizată în algoritmul aproximativ nu funcționează aici. În schimb, vom lua în considerare un algoritm lacom. Soluția dată de el va fi mai rea decât cea optimă de un număr logaritmic de ori. Pe măsură ce dimensiunea problemei crește, calitatea soluției se deteriorează, dar totuși destul de lent, astfel încât această abordare poate fi considerată utilă.

Declarația problemei

Datele inițiale ale problemei de acoperire a mulțimii sunt o mulțime finită și o familie de submulțimi ale acesteia. O copertă este o familie cu cea mai mică cardinalitate, a cărei unire este . În cazul unei întrebări despre permisiunea de a intra, sunt date o pereche și un număr întreg ; întrebarea este existența unui set de acoperire a cardinalității (sau mai puțin). ${\mathcal {U}}$ $\mathcal{S}$ ${\mathcal {C}}\subseteq {\mathcal {S}}$ ${\mathcal {U}}$ $({\mathcal {U}), {\mathcal {S}))$ $k$ $k$

Exemplu

Ca exemplu de problemă de acoperire a unui set, luați în considerare următoarea problemă: imaginați-vă că este necesar un anumit set de abilități pentru a finaliza o sarcină . Există, de asemenea, un grup de oameni care au fiecare dintre aceste abilități. Este necesar să se formeze cel mai mic subgrup suficient pentru a finaliza sarcina, adică. inclusiv purtători ai tuturor aptitudinilor necesare. $S$

Metode de rezolvare

Algoritmul Aproximat Greedy

Algoritmul greedy selectează seturile după următoarea regulă: la fiecare etapă, se selectează un set care acoperă numărul maxim de elemente neacoperite încă.

Greedy-Set-Cover(U,F), unde este o mulțime dată de toate elementele, este o familie de submulțimi $U$ $F$ $U$

$X\leftarrow U$
$C\leftarrow \varnothing$
while $X\not =\varnothing$ do
1. alege cu cea mai mare $S\in F$ $\mid X\cap S\mid$
2. $X\leftarrow X\setminus S$
3. $C\leftarrow C\cup \{S\)$
return $C$

Se poate demonstra că acest algoritm funcționează cu acuratețe , unde este puterea celei mai mari mulțimi și este suma primilor termeni ai seriei armonice. $O(H(s))$ $s$ $H(n)$ $n$

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

Cu alte cuvinte, algoritmul găsește o acoperire a cărei dimensiune este de cel mult ori dimensiunea acoperirii minime. $H(e)$

Teorema lui Feige spune că pentru problema de acoperire a mulțimii nu există un algoritm cu un factor de aproximare , deoarece în caz contrar, clasa de complexitate NP ar fi egală cu clasa de complexitate TIME( ). [1] Astfel, algoritmul greedy este cel mai bun algoritm de aproximare pentru problema de acoperire a mulțimii. $(1-\epsilon )\cdot H(n)$ $n^{O(\log \log n))$

Există un exemplu standard în care algoritmul greedy funcționează cu precizie . $\log _{2}(n)/2$

Universul este format din elemente. Setul de mulțimi este format din mulțimi disjunse pe perechi , ale căror cardinalități sunt , respectiv. Există, de asemenea, două seturi disjunse , fiecare conţinând jumătate din elementele din fiecare . Pe un astfel de set, algoritmul greedy selectează seturile , în timp ce soluția optimă este alegerea seturilor și Un exemplu de date de intrare similare pentru poate fi văzut în figura din dreapta. $n=2^{(k+1)}-2$ $k$ $S_{1},\ldots, S_{k)$ $2,4,8,\ldots ,2^{k)$ $T_{0},T_{1}$ $Si}$ $S_{k},\ldots, S_{1)$ $T_{0}$ $T_{1}$ $k=3$

Algoritm genetic

Algoritmul genetic este o metodă de căutare aleatorie euristică bazată pe principiul simulării evoluției unei populații biologice.

În cazul general, în timpul funcționării algoritmului, are loc o schimbare succesivă a populațiilor, fiecare dintre acestea fiind o familie de acoperiri, numite indivizi ai populației. Acoperirile populației inițiale sunt construite aleatoriu. Cea mai comună și mai bine dovedită este schema staționară a algoritmului genetic, în care următoarea populație diferă de cea anterioară doar prin unul sau doi indivizi noi. La construirea unui individ nou din populația actuală, ținând cont de ponderile acoperirilor, se selectează o pereche de indivizi „părinte” , iar pe baza acestora, în procedura de încrucișare (aleatoriu sau determinist), un anumit set de acoperire. se formează mulţimi . Apoi suferă o mutație , după care se construiește un individ din el, care înlocuiește acoperirea cu cea mai mare greutate în noua populație. Populația este actualizată de un anumit număr (specificat) de ori, iar rezultatul algoritmului este cea mai bună acoperire găsită. $J^{\prime },J''$ $J_{x}$

Soluția exactă

Adesea , problema de acoperire a mulțimii este formulată ca o problemă de programare cu numere întregi [2] :

Este necesar să găsiți , unde este o matrice și = 1 dacă , și = 0 în caz contrar; denotă un vector de uni; ; este un vector, unde , dacă este inclus în acoperire, în caz contrar . $f^{*}(c,A)=\min\{(c,x)|Ax\geq e,x\in \{0,1\}^{n}\)$ $A$ $(m\times n)$ $a_{{ij}}$ $i\in S_{j}$ $a_{{ij}}$ $e$ $m$ $c=(c_{1},c_{2},\dots,c_{n})^{T)$ $x=(x_{1},x_{2},\dots,x_{n})^{T)$ $x_{j}=1$ $S_j$ $x_{j}=0$

Soluția exactă poate fi obținută în timp polinomial dacă matricea este complet unimodulară . Aceasta include, de asemenea, problema acoperirii nodurilor pe un graf și un arbore bipartit . În special, atunci când fiecare coloană a matricei conține exact doi 1, problema poate fi privită ca o problemă de acoperire a marginilor graficului, care se reduce efectiv la găsirea unei potriviri maxime . Pe clasele de probleme în care sau sunt mărginite de o constantă, problema se rezolvă în timp polinomial prin metode de enumerare exhaustivă. $A$ $A$ $n$ $m$

Sarcini conexe

Literatură

A. V. Eremeev, L. A. Zaozerskaya, A. A. Kolokolov. Setul care acoperă problema: complexitate, algoritmi, studii experimentale. Analiza discretă și cercetarea operațiunilor. Ser. 2. 2000. V. 7, N 2. S. 22-46.
Thomas H. Kormen et al., Capitolul 16 Algoritmi lacomi // Algoritmi: Construcție și analiză = INTRODUCERE ÎN ALGORITMI. - Ed. 1. - M .: Centrul din Moscova pentru Educație Matematică Continuă, 2001. - S. 889-892. - ISBN 5-900916-37-5 .

Note

↑ Uriel Feige. Un prag de ln n pentru aproximarea acoperirii setului // Jurnalul ACM. - 1998-07. — Vol. 45 , iss. 4 . — P. 634–652 . — ISSN 1557-735X 0004-5411, 1557-735X . - doi : 10.1145/285055.285059 .
↑ A. V. Eremeev, L. A. Zaozerskaya, A. A. Kolokolov. SET DE PROBLEME DE ACOPERIRE: COMPLEXITATE, ALGORITMI, STUDII EXPERIMENTALE // ANALIZA DISCRETA SI CERCETARE OPERATIVA. - 2000. - iulie-decembrie ( vol. 7 , nr. 2 ). - S. 22-46 . Arhivat din original pe 25 ianuarie 2021.

Link -uri

Benchmark-uri cu soluții optime ascunse pentru acoperirea seturilor, ambalarea seturilor și determinarea câștigătorului

Probleme NP-complete
Problema de maximizare a stivuirii (ambalării)	Ambalare in containere ambalare bidimensională ambalare liniară ambalare după greutate ambalare după valoare Problema rucsacului
teoria grafurilor teoria multimelor	Problemă de acoperire a vârfurilor Faceți clic pe problemă Problema unei multimi (multimi) independente Setați problema acoperirii Problema lui Steiner Problema vânzătorului ambulant Problemă generalizată a vânzătorului ambulant
Probleme algoritmice	Problemă de satisfacție pentru formulele booleene (în formă normală conjunctivă)
Jocuri de logică și puzzle-uri	Etichete generalizate (joc în N 2 -1) cea mai scurta solutie problema Probleme ale căror soluții sunt aplicate în Tetris Problemă generalizată de Sudoku Problemă de umplere a pătratului latin Sarcina lui Kakuro
Clasele de dificultate Cercetare operațională Optimizare Optimizare combinatorie Matematică aplicată Teoria algoritmilor Programare dinamică 21 Problemă Karp NP-completă