Problem der exakten Überdeckung
Das Problem der exakten Überdeckung (englisch Exact cover) ist ein Entscheidungsproblem der Kombinatorik. Es gehört zu den 21 klassischen NP-vollständigen Problemen, von denen Richard M. Karp 1972 gezeigt hat, dass sie NP-vollständig sind.
Ein alltägliches Beispiel
Für ein Projekt soll ein Team zusammengestellt werden. In dem Team sollen Kompetenzen auf den Gebieten Architektur, Bauphysik, Chemie, Datenverarbeitung, Elektrotechnik und Finanzierung vertreten sein. Dabei kann ein Teammitglied mehrere Kompetenzen mitbringen. Außerdem soll keine Kompetenz mehrfach vertreten sein, denn das wäre eine Vergeudung von Humanressourcen. Zur Verfügung stehen folgende fünf Personen:
Anna ist kompetent für Architektur und Bauphysik, Boris für Architektur, Bauphysik und Chemie, Charlotte für Chemie und Elektrotechnik, Dennis für Datenverarbeitung und Finanzierung, Emma für Elektrotechnik und Finanzierung. Wie soll das Team nun aussehen? Wenn man Boris nimmt, scheidet Charlotte für die Abdeckung der Elektrotechnik aus, da dann die Chemie doppelt vertreten wäre. Also muss man zur Abdeckung der Elektrotechnik Emma heranziehen, was wegen der Finanzierung Dennis ausschließt, so dass die Datenverarbeitung nicht mehr abgedeckt werden kann. Also kann man von Anfang an Boris nicht verwenden. Das Problem ist aber lösbar, indem man das Team aus Anna, Charlotte und Dennis bildet. Das ist die so genannte exakte Überdeckung, hier von Teamkompetenzen durch Teammitglieder.
Es ist kein Zufall, dass die Argumentationsweise an das Sudoku-Lösen erinnert. Auch Sudoku ist ein Exact-cover-Problem.
Mathematische Formulierung
Gegeben sind eine Menge und eine Menge von nichtleeren Teilmengen von , also , wobei die Potenzmenge von bezeichnet.
Gesucht ist eine Teilmenge von , deren disjunkte Vereinigung ist:
- .
Das heißt: Jedes Element in soll in genau einer der Mengen in vorkommen. Die Mengen in bilden also eine exakte Überdeckung von ( ist eine Partition von ).
![](http://upload.wikimedia.org/wikipedia/de/2/29/Exact_cover.png)
Zum Beispiel sei
- und
- .
Die Menge
zeigt, dass eine exakte Überdeckung existiert.
Dieses Beispiel entspricht genau dem oben genannten alltäglichen Beispiel.
Siehe auch
- Mengenzerlegungsproblem