AuK/Verzweigen und beschränken SS11

Wiki-Quelltext dieser Seite.

= Bewerten, auswählen und expandieren =

Lösungsbäume oder auch "Zustandsraum-Bäume" genannt, können bei systematischer und vollständiger Aufstellung sehr groß  werden, wenn es sich bei dem Lösungsallgortihmus um einen  Allgorithmus mit exponentiellen Aufwand handelt (Beispiel "Schach-Lösungsbaum").
Draus entspringt die Motivation, Lösungsbäume zu begrenzen und Teilbäume auszusondern, welche für die Lösung defintiv nicht in Frage kommen. Dabei ist das Problem, eben genau die Teilbäume herauszufiltern, die keinen Lösungsweg bringen können.
Allerdings steht fest, dass mit dem als "ausästen" beschriebenen Vorgehen nichts am exponentiellen Zeitaufwand verändert, im worst case gar keine Zeitersparnis bringt. Allerdings ist in den meisten Fällen der praktische Wert des Vorgehens deutlich.

==Vorgehensweise:==

Das Verfahren branch and bound arbeitet wie folgt:
Für jeden Knoten (branch) wird eine Wertschranke (bound) ermittelt. Diese besagt, dass keiner der folgenden Knoten nach diesen branch eine bessere Bewertung erhält. Bei Maximierungsproblemen werden dabei obere, bei Minimierungsproblemen untere Schranken angegeben.
Der Lösungsbaum entsteht dabei durch die Weiterverfolgung des besten Knotens – dem besten Bound.  Bei einer Gleichheit mehrerer Bounds wird dabei zufällig einer ausgewählt.
Um eine Verschlechterung von Knoten in späteren Schritten entgegenzutreten, werden alle vorhergehend aussortierten Expansionskandiaten aufbewahrt, sortiert nach dem Aufwandsfaktor der Bounds, um einen möglichst kleinen Zwischenspeicherbedarf zu haben.
Dafür eignen sich besonders sogenannte Prioritätswarteschlangen (priority queue). Diese sind Datentypen, mit dem wir uns später befassen werden.

==Problem:==

Sofern sich die Schrankenberechnung sehr stark an der Optimierngsaufgabe orientiert, erhält man zwar sehr genaue Werte, muss allerdings äußerst hohe Kosten (Zeitaufwände) in Kauf nehmen.
Sofern der Aufwand gering gehalten werden soll, wird eine einfache Schrankenfunktion gewählt, allerdings mit dem Risiko,dass die Bounds nicht optimiert werden und nur ein Näherungswert erziehlt wird.

==Beispiel:==

Bei Schachprogrammen wird ein ähnliches Verfahren genutzt. Dabei werden die optimalen Knoten für i Züge berechnet. Dabei können auch Opferungszüge eingebaut werden, welche auf den ersten Blick schlecht erscheinen, allerdings im Nachhinein einen Vorteil bewirken. Damit können auch Näherungslösungen als wertvoll eingestuft werden. Allerdings wird dennoch stets nach einer echten Bewertungsfunktion gesucht.

= Anwendung auf das Rucksackproblem =
= Das Rundreiseproblem =
== Problemstellung ==
== Naiver Algorithmus ==
== Lösung mit Verzweigen und Beschränken ==