Exacte overdekking

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de wiskunde is exacte overdekking een bijzonder geval van het begrip overdekking van een verzameling.

Definitie[bewerken]

Gegeven een verzameling U (de "universele verzameling" genoemd) en een verzameling S, die bestaat uit deelverzamelingen van U; dus S \subseteq \mathcal{P}(U), waarbij \mathcal{P}(U) de machtsverzameling van U voorstelt.

Een exacte overdekking (Engels: exact cover) van U is een deelverzameling C van S, waarvan de elementen twee aan twee disjuncte verzamelingen zijn en waarvan de vereniging gelijk is aan U.

Elk element uit U mag dus in een en slechts een van de verzamelingen uit C voorkomen. De geselecteerde verzamelingen vormen aldus een partitie van U.

Probleem van de exacte overdekking[bewerken]

Het probleem van de exacte overdekking is een beslissingsprobleem uit de computerwetenschap. Voor gegeven verzamelingen U en S van deelverzamelingen van U is de vraag: is het mogelijk om uit de elementen van S een selectie te maken die een exacte overdekking van U is?

Dit is een van de 21 klassieke NP-volledige problemen, die Richard M. Karp in 1972 opsomde.

Voorbeeld[bewerken]

Stel

U = \{a, b, c, d, e, f\} en
S = \{S_1, S_2, S_3, S_4, S_5 \}
waarbij

 S_1 = \{a,b\}, S_2 = \{a,b,c\}, S_3 = \{c, e\}, S_4 = \{d, f\}, S_5 = \{e, f\}.

De verzameling

C = \{ S_1, S_3, S_4 \} = \{ \{a,b\}, \{c, e\}, \{d, f\} \}

is een exacte overdekking van U.

Matrixvoorstelling[bewerken]

Stel de universele verzameling U heeft n elementen, genummerd van 1 tot n, en de verzameling S bestaat uit m deelverzamelingen van U. We kunnen S voorstellen als een matrix A met n rijen en m kolommen. Het element a_{i,j} op de i-de rij en de j-de kolom is 1 wanneer het i-de element van U voorkomt in de j-de verzameling van S, en anders 0.

Voor het voorbeeld hierboven geeft dit de matrix:

S1 S2 S3 S4 S5
a 1 1 0 0 0
b 1 1 0 0 0
c 0 1 1 0 0
d 0 0 0 1 0
e 0 0 1 0 1
f 0 0 0 1 1

Het probleem van de exacte overdekking wordt in deze vorm: maak, indien mogelijk, een selectie van kolommen uit deze matrix, zodat in de geselecteerde kolommen in elke rij exact eenmaal een "1" voorkomt. Donald Knuth formuleerde hiervoor een recursief algoritme dat met backtracking alle mogelijke oplossingen vindt voor een gegeven matrix van 0'en 1'en. Hij noemde dit "Algoritme X" en voor de computerimplementatie gebruikte hij een techniek die hij "dancing links" noemde.[1]

Toepassingen[bewerken]

Dit zijn enkele van de problemen die men kan reduceren tot een exacte-overdekkingsprobleem:

  • het betegelen van een schaakbord met de 12 pentomino's (polyomino's met vijf vierkanten). De vier centrale vakjes van het bord blijven daarbij vrij. Elke pentomino kan slechts eenmaal geplaatst worden, en elk van de 60 vakjes moet door een en slechts een polyomino bedekt worden.
  • het achtdamesprobleem: plaats n dames op een n bij n schaakbord zodanig dat ze elkaar niet kunnen aanvallen. In elke rij en elke kolom van het bord moet dan exact een dame staan, evenals in elke diagonale rij.
  • Sudoku: in een vierkant van 9 op 9 zijn er 9x9x9 = 729 kandidaten (toewijzingen van een van negen cijfers aan elk vakje). Elk vakje moet exact een cijfer bevatten; elke rij, kolom of deelvierkant van 3 op 3 moet exact eenmaal elk cijfer van 1 tot 9 bevatten. Deze voorwaarden kan men formuleren als verzamelingen van toewijzingen (324 in totaal: 9x9 voor vakjes, rijen, kolommen en deelvierkanten). Dit geeft een matrix van 729 rijen en 324 kolommen.

Verwante problemen[bewerken]

Exact hitting set[bewerken]

Voor een universele verzameling U en een collectie S van deelverzamelingen van U, is een exact hitting set een deelverzameling U^* van U zodat elke verzameling uit S exact een element uit U^* bevat. Het probleem om een exact hitting set te vinden voor gegeven U en S is equivalent aan het exacte-overdekkingsprobleem.

Voorbeeld[bewerken]

Stel U = \{1,2,3\} en

S = \{S_1, S_2, S_3\} met S_1=\{1,3\}, S_2 = \{2\}, S_3 = \{1,2\}.

Een exact hitting set in dit geval is U^* = \{2,3\}.

Verzamelingenoverdekking[bewerken]

Wanneer men in de definitie de eis dat de elementen van S disjuncte verzamelingen zijn laat vallen, en men dus toelaat dat een element uit U in meer dan een verzameling uit C voorkomt, krijgt men het verzamelingenoverdekkingsprobleem (set cover problem). Als beslissingsprobleem luidt dit: is het mogelijk om voor een gegeven positief geheel getal k, een selectie C te maken van ten hoogste k verzamelingen uit S, zodat hun vereniging gelijk is aan U? Het corresponderende optimalisatieprobleem zoekt naar de kleinst mogelijke C (dit wil zeggen die met het kleinst aantal selecties uit S).

Bronnen, noten en/of referenties