Backtracking und Branch and Bound

Backtracking und Branch and Bound sind systematische Suchparadigmen, die den Raum der Kandidatenlösungen als Baum durchsuchen und Unterbäume abschneiden, die nicht zu einer gültigen oder optimalen Lösung führen können, um ansonsten exponentielle Suchen in der Praxis handhabbar zu machen.

Definition

Backtracking ist eine Tiefensuche des Baumes partieller Kandidatenlösungen, die einen Zweig in dem Moment abschneidet, in dem der partielle Kandidat nicht zu einer gültigen Lösung vervollständigt werden kann; Branch and Bound erweitert dies um numerische Schranken für das Ziel, sodass Zweige, deren bestmöglicher Wert den aktuellen besten Wert nicht übertreffen kann, verworfen werden.

Scope

Dieses Thema behandelt erschöpfende Suchtechniken, die um einen Suchbaum herum organisiert sind: Backtracking, das Teillösungen verwirft, sobald sie eine Einschränkung verletzen, und Branch and Bound, das Schranken für das bestmögliche erreichbare Ziel verwendet, um Unterbäume bei der Optimierung zu beschneiden. Es umfasst Beispiele zur Constraint-Satisfaction (N-Damen-Problem, Graphfärbung, Sudoku) und kombinatorische Optimierungsbeispiele (Problem des Handlungsreisenden, ganzzahlige Programmierung) und erörtert, warum diese Methoden trotz exponentieller Kosten im schlimmsten Fall für NP-schwere Probleme wertvoll bleiben.

Core questions

• Wie wird der Lösungsraum eines Problems als Suchbaum partieller Zuweisungen modelliert?
• Welche Constraint-Prüfungen ermöglichen es dem Backtracking, unzulässige Zweige frühzeitig zu beschneiden?
• Wie werden untere und obere Schranken berechnet, um Zweige bei der Optimierung zu beschneiden?
• Wie beeinflusst die Reihenfolge von Verzweigung und Schrankenbildung die praktische Leistung?
• Warum werden diese Methoden trotz exponentieller Worst-Cases für NP-schwere Probleme eingesetzt?

Key concepts

• Suchbaum
• Tiefensuche
• Constraint-Propagation
• Beschneidung (Pruning)
• Schrankenfunktionen
• aktuelle beste Lösung (incumbent solution)
• N-Damen-Problem
• Relaxation der ganzzahligen Programmierung

Key theories

Beschneidung des Suchbaums

Beide Paradigmen organisieren Kandidatenlösungen als einen tiefenorientiert durchsuchten Baum; die Korrektheit ergibt sich aus der Vollständigkeit, während die Effizienz aus dem Beschneiden von Unterbäumen resultiert, die nachweislich keine gültige oder verbessernde Lösung enthalten können.

Schrankenfunktionen bei Branch and Bound

Branch and Bound verwaltet die bisher beste gefundene Lösung und eine Schranke (z. B. eine LP-Relaxation) für den besten Wert, der in jedem Unterbaum erreichbar ist; ein Unterbaum wird verworfen, wenn seine Schranke die aktuelle beste Lösung nicht verbessern kann.

Clinical relevance

Branch and Bound ist das Rückgrat der exakten kombinatorischen Optimierung in der Operations Research, einschließlich ganzzahliger und gemischt-ganzzahliger Programmierlöser, die für die Zeitplanung, Routenplanung und Planung verwendet werden. Backtracking liegt Constraint-Solvern, SAT-ähnlichen Suchen, Puzzle-Solvern und Parsern zugrunde, wo die systematische Suche mit Beschneidung der praktische Weg zu exakten Antworten ist.

History

Backtracking wurde in den 1950er und 1960er Jahren als allgemeine Technik systematisiert, insbesondere von Golomb und Baumert beschrieben. Branch and Bound wurde 1960 von Ailsa Land und Alison Doig für die ganzzahlige lineare Programmierung eingeführt und ist seitdem zu einem zentralen Bestandteil der kombinatorischen Optimierung geworden, der moderne gemischt-ganzzahlige Programmierlöser antreibt.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

Was ist der Unterschied zwischen Backtracking und Branch and Bound?

Backtracking wird typischerweise für Machbarkeits- und Constraint-Satisfaction-Probleme verwendet und beschneidet Zweige, die Constraints verletzen. Branch and Bound zielt auf Optimierung ab und beschneidet zusätzlich unter Verwendung numerischer Schranken, wobei jeder Unterbaum verworfen wird, dessen bestmögliches Ziel die bereits gefundene beste Lösung nicht übertreffen kann.

Wenn diese Methoden im schlimmsten Fall exponentiell sind, warum werden sie dann verwendet?

Für NP-schwere Probleme ist kein polynomialer exakter Algorithmus bekannt, aber effektives Beschneiden eliminiert oft den Großteil des Suchbaums bei realen Instanzen, sodass Branch-and-Bound- und Backtracking-Solver regelmäßig nachweislich optimale Lösungen weit schneller finden, als ihre Worst-Case-Schranken vermuten lassen.