Zustandsraum und Schnitte

Pruning schneidet Äste ab, die keine gültige Lösung mehr erreichen können. Frühe Konflikttests sparen exponentielle Arbeit.

Beispiel: bei n-Damen keine Dame in derselben Diagonale platzieren, bevor man tiefer geht.

Wo gebraucht

Pruning entscheidet, ob Backtracking in der Praxis endet. Dieselbe Idee in Branch-and-Bound, SAT-Solvern und Query-Planern.

Vertiefung

Der Zustandsraum enthält alle partiellen und vollständigen Konfigurationen eines Suchproblems. Eine Darstellung ist gut, wenn aus ihr sowohl die nächsten Entscheidungen als auch die noch verletzbaren Bedingungen effizient abgeleitet werden können. Unterschiedliche Darstellungen desselben Problems erzeugen daher Suchbäume mit sehr verschiedener Grösse.

Ein Schnitt beendet die Untersuchung eines Teilbaums, sobald feststeht, dass dort keine zulässige oder keine bessere Lösung entstehen kann. Machbarkeitsschnitte nutzen harte Bedingungen. Schranken vergleichen dagegen das bestmögliche Ergebnis eines Zweigs mit der bisher besten vollständigen Lösung.

Schwierigkeitsstufen

1. Zustand, Entscheidung und Zielzustand eines Problems unterscheiden.
2. Einen sicheren Machbarkeitsschnitt aus einer Nebenbedingung ableiten.
3. Eine optimistische Schranke für ein Optimierungsproblem begründen.

Fallstricke

Eine Schranke muss optimistisch sein, wenn mit ihr ganze Zweige verworfen werden. Wird das erreichbare Ergebnis zu schlecht geschätzt, kann der Algorithmus gerade den optimalen Zweig abschneiden.