Verzweigen und beschränken SS11
Inhaltsverzeichnis |
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"). Daraus entspringt die Motivation, Lösungsbäume zu begrenzen und Teilbäume auszusondern, welche für die Lösung defintiv nicht in Frage kommen. Das Problem dabei ist, 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 wird, dies sogar 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 der Bounds 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 uns bereits bekannte Rurcksackproblem lässt sich mit dem "Branch and Bound" Verfahren sehr gut umsetzen. Dazu muss man sich ersteinmal Gedanken über die Werteschranke (bound) machen, nach denen man die einzelnen Knoten bewertet.
Dazu eignet sich ein Wertequotient (\frac{Wert}{Gewicht}) der den einzelnen Wert eines Gegenstandes in Abhänigkeit seines Gewichtes darstellt. Ordnet man diese nun absteigend nach ihrem Werteqotienten und billdet alle Kombinationen dieser Werte druch wegassen verschiedener Gegenstäne, so ist die optimale Lösung des Rucksackproblemes dejenige Kombination, deren Gesamtgewicht kleiner oder gleich der Rucksackkapazität ist und den maximalen Wert besitzt. Für die Darstellung der Kombination eignet sich die Darstellung in einem Vektor, in dem die Position den Gegenstand in der Ordnung repräsentiert und dessen Wahrheitswert für die Einbeziehung des jeweiligen Objektes in den Rucksack steht.
Werteqotient: wq = \frac{Wert}{Gewicht}
Ordnung der Gegenstände: O = (wq_{1}, wq_{2}, ..., wq_{n})
Vektor der ausgewählten Gegenstände: V = (x_{1}, x_{2}, ..., x_{n}) mit x_{i} \in \{0,1\}
Die optimale Lösung wäre nun: \sum_{i=1}^n x_i * g_i \le Gesammtgewicht & \sum_{a=i}^n x_i + w_i \rightarrow max
Das Rundreiseproblem
Problemstellung
Das Rundreiseproblem (englisch: travelling salesman problem) ist eine klassische logistische Problematik mit einer großen Palette an modernen Anwendungsbeispielen. Dabei wird eine minimale Route zwischen einer Anzahl von Punkten gesucht, die alle abgearbeitet werden müssen. Es ist also ein klasisches Minimierungsproblem.
Annahme: Ein Lieferproblem von einem Heimatort zu 4 Lieferorten
Es gibt nun 4! mögliche Routen:
ABCD ABDC ACBD ACDB ADBC ADCB
BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA
DABC DACB DBAC DBCA DCAB DCBA
Dabei lassen sich unnötige und unwirtschaftliche Routen ausgliedern, um eine minimalisierte Lösung zu finden, also eine möglichst kurze Strecke.
Naiver Algorithmus
Ein Ansatz zur Lösung des Problems ist ein Algorithmus, der zuerst alle möglichen Routen ((n-1)!) generiert. Dabei entsteht ein exponetieller Aufwand mit der Formel:
n! = \sqrt{2*\pi*n}*\left(\frac{n}{e}\right)^n*\left(1+\frac{1}{12n}+\frac{1}{288n^2}+\mathcal{O}\left(\frac{1}{n^3}\right)\right)In diesem Aufwand ist der eigentliche Lösungsaufwand noch nicht inbegriffen sondern nur der Aufwand zur Berechnung der möglichen Lösungen.
Nachdem die Lösugen generiert wurden, kann als mit Hilfe von Entfernungsmatrizen die kürzeste Strecke herausgefunden werden.
Dies lässt eine simple Lösung vermuten.
Allerdings wird der Aufwand durch seine exponentielle Natur schon bei nur 15 Orten maßlos groß (87.178.291.200 mögliche Rundreisen).
Wenn nun also ein Unternehmen mit vielen Punkten arbeiten will, bedarf es einer anderen Lösungsmöglichkeit.