Lektion 4.4

Umgang mit NP-schweren Problemen

50 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • eine exakte Verzweigung für Knotenüberdeckung begründen und ihren Parameter von der gesamten Eingabelänge trennen,

  • zulässige Lösungen, untere Schranken und einen Optimalitätsnachweis auseinanderhalten,

  • die Zwei-Approximation über ein maximales Matching beweisen,

  • Heuristiken und pseudopolynomielle Tabellen anhand ihrer tatsächlichen Garantien beurteilen.

Vorausgesetzt: Polynomielle Reduktionen zwischen NP-Problemen, Das 0/1-Rucksackproblem

Ein Schwerebeweis nimmt einem Problem nicht seine praktische Bedeutung. Prüfungen müssen geplant, Gegenstände ausgewählt und knappe Ressourcen verteilt werden. Die nächste Frage lautet deshalb nicht „Ist alles hoffnungslos?“, sondern: Welche Art von Ergebnis brauchen wir, welche Eingaben erwarten wir und welche Zusicherung muss das Verfahren liefern?

Manchmal ist eine kleine Instanz exakt lösbar. Manchmal ist eine bestimmte Kenngröße klein, obwohl der Graph groß ist. Manchmal genügt ein nachweislich naher Wert, manchmal zunächst nur eine gute zulässige Lösung. Diese Möglichkeiten sind verschieden. Wir untersuchen sie vor allem am ungewichteten Knotenüberdeckungsproblem und vergleichen sie anschließend mit Rucksack und Graphfärbung.

Definition

Exakte Lösung, Approximation und Heuristik

Ein exaktes Verfahren liefert nach vollständigem Abschluss eine optimale Lösung oder die richtige Entscheidungsantwort. Es darf dafür im ungünstigsten Fall sehr lange brauchen. Eine Approximation liefert eine zulässige Lösung mit einer bewiesenen Gütegarantie. Für ein Minimierungsproblem mit Optimalwert OPT bedeutet ein Faktor c≥1c\ge1, dass der ausgegebene Wert höchstens c·OPT ist. Die Garantie gilt für alle Eingaben des ausdrücklich genannten Modells.

Eine Heuristik nutzt eine begründete Suchidee, besitzt aber nicht automatisch eine solche Gütegarantie. Ein gieriges Vorgehen kann je nach Problem ein exakter Algorithmus, eine bewiesene Approximation oder nur eine Heuristik sein. Die Bezeichnung der Methode ersetzt keinen Beweis. Bei einem Maximierungsproblem müssen die Ungleichungen passend umgekehrt werden; hier beginnen wir mit Minimierung.

Schritt für Schritt

Knotenüberdeckung exakt nach einem kleinen Budget durchsuchen

Gesucht ist eine Überdeckung mit höchstens k Knoten. Wähle eine noch vorhandene Kante {u,v}. Jede zulässige Überdeckung muss u oder v enthalten. „u oder v“ erlaubt auch, dass eine Lösung beide enthält; die zwei Zweige müssen nicht disjunkt sein.

  1. Sind keine Kanten mehr vorhanden und ist das Restbudget nicht negativ, ist die bisherige Auswahl ausreichend. Ist das Restbudget null und noch eine Kante vorhanden, scheitert der Zweig.

Schritt 1 von 3
Satz

Ein kleiner Parameter kann wichtiger sein als ein kleiner Graph

Die beschriebene Suche lässt sich in O(2k poly(n+m))O(2^k\,\mathrm{poly}(n+m)) Zeit ausführen, wobei n die Knoten- und m die Kantenzahl ist. Sie ist festparameter-tractabel, kurz FPT, bezüglich k: Der exponentielle Teil hängt nur vom gewählten Parameter ab.

Beispiel

Eine sichere Vereinfachungsregel statt einer bloßen Vermutung

Hat ein Knoten u mehr als k verschiedene Nachbarn, muss jede Überdeckung mit höchstens k Knoten u enthalten. Würde u nicht gewählt, müssten alle seine Nachbarn gewählt werden, um die an u liegenden Kanten zu überdecken. Das wären zu viele.

Man darf u daher fest wählen, seine Kanten entfernen und das Restbudget um eins senken. Die Regel benutzt das aktuelle Restbudget, nicht unbegrenzt das ursprüngliche Budget. Sie erhält die Existenz einer Lösung in beiden Richtungen. Solche beweisbaren Vereinfachungen können die anschließende Suche verkleinern, ohne das Problem durch eine ungeprüfte Auswahl zu ersetzen.

Definition

Untere Schranke und beste bekannte Lösung

Bei einem Minimierungsproblem liefert eine zulässige Lösung mit Wert U eine obere Schranke: OPT≤U. Eine unabhängig bewiesene Zahl L mit L≤OPT ist eine untere Schranke. Stimmen beide überein, ist der Optimalwert nachgewiesen. Für L>0 begrenzen sie auch den möglichen relativen Abstand der gefundenen Lösung.

L≤OPT≤U,UOPT≤ULL\le\mathrm{OPT}\le U,\qquad\frac{U}{\mathrm{OPT}}\le\frac UL
Beispiel

Was ein Zwischenstand wirklich belegt

Für eine Knotenüberdeckung wurde eine zulässige Menge mit fünf Knoten gefunden. Eine andere Rechnung beweist, dass mindestens drei nötig sind. Dann liegt OPT zwischen 3 und 5. Die gefundene Lösung liegt höchstens um den Faktor 5/3 über dem Optimum, ist aber noch nicht als optimal bewiesen.

Bei Branch and Bound wird die exakte Suche mit solchen Schranken verbunden. Sind in einem Zweig bereits zwei Knoten gewählt und werden für den verbleibenden Rest nachweislich mindestens drei weitere benötigt, kann dieser Zweig eine gespeicherte Lösung der Größe fünf nicht verbessern. Wenn nur eine optimale Lösung gesucht wird, darf er abgeschnitten werden. Sollen alle gleich guten Lösungen aufgezählt werden, wäre das Abschneiden bei Gleichheit nicht erlaubt. Die Schranke muss für genau diesen Restgraphen und die bereits getroffenen Entscheidungen gültig sein.

Definition

Matching, maximal und maximum

Ein Matching ist eine Kantenmenge, deren Kanten keine Endpunkte gemeinsam haben. Jede Knotenüberdeckung muss mindestens einen Endpunkt jeder Matchingkante enthalten. Weil diese Endpunkte zwischen verschiedenen Matchingkanten nicht geteilt werden, folgt ∣M∣≤OPT|M|\le\mathrm{OPT}.

Ein Matching ist maximal, wenn keine weitere Kante hinzugefügt werden kann, ohne einen schon benutzten Endpunkt zu verwenden. Es ist maximum, wenn es unter allen Matchings die größte mögliche Kantenzahl besitzt. Für das folgende Näherungsverfahren genügt ein maximales Matching. Man erhält eines, indem man wiederholt eine Kante mit noch unbenutzten Endpunkten hinzufügt, bis keine mehr möglich ist.

Satz

Zwei-Approximation für ungewichtete Knotenüberdeckung

Berechne ein maximales Matching M und wähle beide Endpunkte jeder Matchingkante als Menge C. Dann ist C eine Knotenüberdeckung und besitzt höchstens doppelt so viele Knoten wie eine optimale Überdeckung.

∣C∣=2∣M∣≤2 OPT|C|=2|M|\le2\,\mathrm{OPT}

Eine zulässige Lösung ist noch nicht zwingend die kleinste

ABCD

Matching: AB. Näherung: A und B. Optimale Überdeckung: A.

Die hervorgehobene Kante AB kann um keine weitere disjunkte Kante ergänzt werden. Beide Endpunkte ergeben eine Überdeckung mit zwei Knoten. Das Zentrum A allein überdeckt aber bereits alle drei Kanten. Hier wird der garantierte Faktor zwei tatsächlich erreicht.

Kurz geprüft

Muss für die Zwei-Approximation ein Matching mit möglichst vielen Kanten berechnet werden?

Beispiel

Graphfärbung: Eine gute Heuristik mit einer unabhängigen Schranke vergleichen

Bei einer Graphfärbung erhalten benachbarte Knoten verschiedene Farben. In einem Prüfungsplan stehen Farben für Termine und Kanten für zeitliche Konflikte. Eine fertige gültige Färbung liefert eine obere Schranke für die kleinste mögliche Terminzahl. Ein Dreieck liefert unabhängig davon die untere Schranke drei, weil seine drei Knoten paarweise benachbart sind.

Das folgende gierige Verfahren ordnet Knoten zunächst nach absteigendem Grad und vergibt jeweils die kleinste noch erlaubte Farbe. Es liefert eine gültige Färbung, beweist aber nicht allgemein deren minimale Farbzahl. Im konkreten Beispiel enthält A,B,C ein Dreieck. Wenn der fertige Lauf drei Farben verwendet, stimmen obere und untere Schranke überein: Für dieses Beispiel ist die Färbung dann nachweislich optimal.

Eine heuristische Färbung und ihr Optimalitätsnachweis im Beispiel

Färben · Prüfungsplan

Jeder Knoten ist eine Prüfung, eine Kante heißt: Jemand schreibt beide. Verbundene Prüfungen brauchen verschiedene Termine. Wie viele Termine reichen?

Ungerichteter Graph · 7 Knoten · 11 Kanten

ABCDEFG
Gefärbt
0
Kanten geprüft
0
  • wird gefärbt
  • zu schon gefärbtem Nachbarn
Schritt 1 von 9
Tempo
← → Schritt, Leertaste Abspielen
Start

Reihenfolge festlegen

Jeder Knoten soll eine Farbe bekommen, und zwei Knoten, die durch eine Kante verbunden sind, dürfen nicht dieselbe haben. So plant man etwa Prüfungen: Knoten sind Prüfungen, eine Kante heißt „jemand schreibt beide“, eine Farbe ist ein Termin. Das gierige Verfahren nimmt die Knoten nacheinander und gibt jedem die kleinste Farbe, die kein Nachbar schon hat. Nach dem Vorschlag von Welsh und Powell kommen Knoten mit vielen Nachbarn (hohem Grad) zuerst, weil sie am schwersten unterzubringen sind.

Reihenfolge nach Grad

Höchster Grad zuerst, bei Gleichstand alphabetisch.

  1. E · 4
  2. B · 3
  3. C · 3
  4. D · 3
  5. G · 3
  6. F · 2

Werte der Knoten

KnotenZustandGradFarbe
Aunbekannt4–
Bunbekannt3–
Cunbekannt3–
Dunbekannt3–
Eunbekannt4–
Funbekannt2–
Gunbekannt3–

Grad: Anzahl der Nachbarn · Farbe: Nummer der Farbe

Pseudocoden = 7, m = 11
  1. ordne die Knoten nach fallendem Grad
  2. für jeden Knoten u: kleinste Farbe, die kein Nachbar von u hat

Die Knoten sind Prüfungen, die Farben Termine. Der Schrittlauf zeigt die gierige Auswahl. Für den abschließenden Hinweis ergänzt das Werkzeug eine exakte Gegensuche mit begrenztem Rechenbudget; ohne vollständigen Suchabschluss bleibt die Optimalität offen. Das Dreieck liefert hier einen davon unabhängigen Nachweis der Mindestzahl. Weder dieser Einzelfall noch die zusätzliche Suche machen die gierige Auswahl allgemein optimal.

Probier es aus

Beispiel

Rucksack: Zahlenwerte und falsche Greedy-Sicherheit

Beim 0/1-Rucksack darf jeder Gegenstand ganz oder gar nicht genommen werden. Die Gewichte seien 10,20,30, die zugehörigen Werte 60,100,120 und die Kapazität 50. Die Wert-pro-Gewicht-Verhältnisse sind 6,5,4. Gierig nach diesem Verhältnis gewählt werden die ersten beiden Gegenstände: Gewicht 30, Wert 160. Der dritte passt dann nicht mehr hinein. Die zweite und dritte Auswahl erreicht dagegen bei Gewicht 50 den Wert 220 und ist hier optimal, wie vollständiges Prüfen der acht Teilmengen zeigt.

Die dynamische Tabelle benötigt bei n Gegenständen und ganzzahliger Kapazität W etwa O(nW) Tabellenschritte. Für kleine Kapazitäten kann das ein exaktes praktisches Verfahren sein. Bei binärer Kodierung von W ist es aber nur pseudopolynomiell: Die Spaltenzahl kann exponentiell in der Anzahl der Kapazitätsbits wachsen. Für den Rucksack mit teilbaren Gegenständen hätte die Verhältnisregel eine andere Garantie; dieses andere Modell darf nicht mit 0/1 verwechselt werden.

Häufige Fehler

Einige schnelle Läufe oder ein Zeitlimit widerlegen NP-Schwere

Ein Verfahren löst viele Testfälle schnell. Oder ein Suchlauf findet lange nichts. Daraus wird manchmal eine allgemeine Laufzeitaussage beziehungsweise die Unlösbarkeit der konkreten Instanz gefolgert.

Richtig ist

Messungen beschreiben die getesteten Fälle und Ressourcen, nicht alle Eingaben. NP-Schwere ist mit vielen einfachen Instanzen vereinbar. Ein erfolgloses Zeitlimit belegt weder Nichtexistenz einer Lösung noch Optimalität einer bisher gefundenen. Eine Garantie benötigt einen vollständigen Suchabschluss, einen passenden mathematischen Beweis oder gültige übereinstimmende Schranken.

Zusammenfassung

  • Exakte Suche, bewiesene Approximation und Heuristik liefern unterschiedliche Zusicherungen.

  • Die Endpunktverzweigung für VERTEX-COVER ist vollständig und braucht O(2k poly(n+m))O(2^k\,\mathrm{poly}(n+m)) Zeit. Ein kleines k hilft, ersetzt aber keinen allgemeinen Polynomialzeitbeweis.

  • Bei Minimierung gilt L≤OPT≤U. Gleichheit beweist Optimalität; für L>0 beschränkt U/L die relative Abweichung.

  • Ein maximales Matching liefert durch seine Endpunkte eine Zwei-Approximation für ungewichtete Knotenüberdeckung.

  • Eine gültige Färbung und ein ausreichend großes Dreieck können gemeinsam die optimale Farbzahl einer konkreten Instanz belegen.

  • Pseudopolynomielle Tabellen messen Zahlenwerte, während Polynomialzeit die Länge der Kodierung misst.

  • Zeitlimits und erfolgreiche Stichproben sind keine allgemeinen Korrektheits- oder Schwerebeweise.

Übungen

Aufgabe 1Multiple Choice

Ein zeitbegrenzter Optimierungslauf findet eine gültige Überdeckung mit neun Knoten und endet ohne vollständigen Suchabschluss. Was ist damit belegt?

Aufgabe 2Numerisch

Wie viele Blätter hat ein vollständig binärer Suchbaum mit vier Verzweigungsebenen, bevor irgendein Zweig vorzeitig abgeschnitten wird?

Aufgabe 3Numerisch

Ein maximales Matching enthält fünf Kanten. Wie viele Knoten wählt das beschriebene Endpunkt-Näherungsverfahren?

Aufgabe 4Numerisch

Für ein Minimierungsproblem sind eine gültige untere Schranke L=6 und eine zulässige Lösung mit U=9 bekannt. Welcher Faktor U/L begrenzt die relative Abweichung dieser Lösung?

Aufgabe 5Numerisch

Welchen Gesamtwert liefert die Verhältnis-Greedy-Auswahl im angegebenen 0/1-Rucksackbeispiel mit Kapazität 50?

Aufgabe 6Numerisch

Wie groß ist der optimale Wert desselben 0/1-Rucksackbeispiels?

Aufgabe 7Freitext

Führe beide Teile des Beweises für die Zwei-Approximation aus: Warum ist die Endpunktmenge eine Überdeckung, und warum ist sie höchstens doppelt so groß wie optimal?

Aufgabe 8Multiple Choice

Was bedeutet die Laufzeit O(2k poly(n+m))O(2^k\,\mathrm{poly}(n+m)) für VERTEX-COVER?