imported>Peter Buch: Allgemeinverständliche Erklärung durch ein alltägliches Beispiel.

2022-11-28T11:24:13Z

Allgemeinverständliche Erklärung durch ein alltägliches Beispiel.

Neue Seite

Das '''Problem der exakten Überdeckung''' (englisch ''Exact cover'') ist ein [[Entscheidbar|Entscheidungsproblem]] der [[Kombinatorik]]. Es gehört zu den [[Karps 21 NP-vollständige Probleme|21 klassischen NP-vollständigen Problemen]], von denen [[Richard M. Karp]] [[1972]] gezeigt hat, dass sie [[NP-Vollständigkeit| 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 <math>X</math> und eine Menge <math>S</math> von [[nichtleer]]en Teilmengen von <math>X</math>, also <math>S \subseteq \mathcal{P}(X)</math>, wobei <math>\mathcal{P}(X)</math> die [[Potenzmenge]] von <math>X</math> bezeichnet.

Gesucht ist eine Teilmenge <math>U</math> von <math>S</math>, deren [[disjunkte Vereinigung]] <math>X</math> ist:
: <math> X = \dot{\bigcup_{Y\in U}}Y </math>.
Das heißt: Jedes Element in <math>X</math> soll in genau einer der Mengen in <math>U</math> vorkommen. Die Mengen in <math>U</math> bilden also eine ''exakte Überdeckung'' von <math>X</math> (<math>U</math> ist eine [[Partition (Mengenlehre)|Partition]] von <math>X</math>).

[[Bild:Exact_cover.png|framed|Grafische Darstellung des Beispiels (die exakte Überdeckung ist rot eingezeichnet)]]
Zum Beispiel sei
:<math>X = \{a, b, c, d, e, f\}</math> und
:<math>S = \{ \{a,b\}, \{a,b,c\}, \{c, e\}, \{d, f\}, \{e, f\} \}</math>.

Die Menge
:<math>U = \{ \{a,b\}, \{c, e\}, \{d, f\} \}</math>
zeigt, dass eine exakte Überdeckung existiert.

Dieses Beispiel entspricht genau dem oben genannten alltäglichen Beispiel.

==Siehe auch==

* [[Mengenzerlegungsproblem]]

{{Navigationsleiste Karps 21 NP-vollständige Probleme}}

[[Kategorie:Komplexitätstheorie]]

Problem der exakten Überdeckung - Versionsgeschichte

imported>Peter Buch: Allgemeinverständliche Erklärung durch ein alltägliches Beispiel.