uni/algodat/report4567/p5-fragestellungen.md

P5 Fragestellungen

Reduktion auf SAT

Wir haben alle Artikel sowie alle Bundles mit denen wir arbeiten können. Die Anzahl an Artikel bestimmt dann die Anzahl an Klauseln. Die Bundles übernehmen dann die Rolle der Variablen, alle Variablen werden nicht negiert eingesetzt und eine Variable ist nur dann in einer Klausel, wenn ein Bundle den Artikel welcher der Klausel zugeordnet ist beinhält.

Konkret wird für jede Klausel überprüft, welche Bundle den zugehörigen Artikel der Klausel besitzt. Besitzt ein Bundle einen Artikel, so wird dessen Variable, repräsentiert durch seinen Index im Eingabearray, in die Klausel eingesetzt.

Ist ein Artikel in keinem Bundle enthalten, so wird dessen Klausel enstprechend keine Variablen enthalten und in Folge unerfüllbar sein. Gibt es zum Beispiel zu einen Artikel nur ein Bundle, dann wird dieser ausschlaggebend für eine optimale Lösung sein, weil ohne das Bundle die Klausel unerfüllbar ist.

Sei $n$ die Anzahl an Variablen und $b$ die Anzahl an Bundles. Dann befindet sich die Laufzeitkomplexität der Reduktion in $O(n b^2)$.

Es ist auch schnell klar, dass durch diese Vorgehensweise genau so viele Klauseln entstehen wie Artikel vorhanden sind. Analog werden auch nur genau so viele Variablen existieren wie nichtleere Bundles vorhanden sind. Wird diese maximale DNF beschränkt durch die Auswahl von $k$ Variablen, so verändert sich die Anzahl an Klauseln nicht, aber Variablen wird es nur noch $k$ geben. Für ein maximales DNF gibt es im worst-case $n$ Klauseln mit jeweils $b$ Variablen pro Klausel. Mit der Einschränkung durch $k$ gibt es im worst-case nur noch $n$ Klauseln mit jeweils $k$ Variablen pro Klausel.

Laufzeit

Die Laufzeit geht hervor aus den jeweiligen Abbildungen. Sehr interessant ist der erhebliche Unterschied zwischen erfüllbaren und unerfüllbaren Probleminstanzen. Aus einem Vergleich von Abb.4 gegen Abb.5 sowie ein Blick auf den Vergleich in Abb.6 geht hervor, dass erfüllbare Probleminstanzen eine viel höhere Laufzeit haben können. Da der Mechanismus zum Finden eines k darauf basiert, das Suchinterval im jeden Schritt im gewünschten Bereich zu halbieren, wird bei erfüllbaren Probleminstanzen garantiert früher oder später ein $k$ gefunden, sodass die aus der Reduktion resultierende DNF erüllbar ist. In diesem Fall muss weiter gesucht werden. Anders ist es, wenn eine Probleminstanz unerfüllbar ist. Zwar muss für alle $k$ die probiert werden überprüft werden, ob jede b choose k Kombination unerfüllbar ist, aber es gibt insgesamt nicht so viele $k$ welche überprüft werden müssen.

Klarerweise wird das Problem auch schwieriger mit steigendem $n$ oder $b$, wobei bei steigendem $n$ mehr Klauseln überprüft werden müssen und bei steigendem $b$ der Suchraum größer wird, da $0 \leq k \leq b$.