Autoren:

• Erik Jähne
• Tony Schöne

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 Rucksackproblem lässt sich mit dem "Branch and Bound" Verfahren sehr gut umsetzen.

Dazu benötigt man zuerst einen ein Wertequotient \left(\frac{Wert}{Gewicht}\right) der den einzelnen Wert eines Gegenstandes in Abhängigkeit seines Gewichtes darstellt. Um jetzt die Selektion der einzelnen Objekte darzustellen, 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.

Werte qotient: 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 Gesamtgewicht & \sum_{a=i}^n x_i + w_i \rightarrow max

Um den Vektor der optimalen Lösung zu erhalten benötigen wir zuerst einen Breitesuchbaum, den wir mit Hilfe der Schranken des "Branch and bound" Verfahrens schrittweise einschränken. Dazu benötigen wir Folgende Überlegung: Um einen Knoten bewerten zu können, bestimmen wir zuerst seinen noch maximal erreichbaren Wert, indem wir den aktuellen Gegenstand so oft dazupacken wie er reinpasst und dann den Wert bestimmen. Mathematisch betrachtet multiplizieren wir den Wertequotienten des Aktuellen Gegenstandes mit der Restkapazität.

Bereits im Rucksack (aktuell Wert): \sum_{i=1}^k x_iw_i

Restkapazität: Gesamtgewicht - \sum_{i=1}^k x_ig_i

Obere Schranke für zusätzlichen Wertegewinn: Restkapazitaet * wq_k = ( Gesamtgewicht - \sum_{i=1}^k x_ig_i ) * wq_k

Maximal erreichbarer Wert bei Weiterverfolgung des aktuellen Knotens: aktueller Wert + Restkapazität * akt. Wertequotient

Nun können wir den Knoten mit der Besten Wertevorhersage weiterverfolgen, da alle anderen Knoten aufgrund der Ordnung der Objekte nur niedrigere Werte erreichen können.

Beispiel:

Wir besitzen folgende Gegenstände:

Unser Rucksack hat dabei eine Kapazität von K = 11.

Wird bilden nun einen Breitensuchbaum, bei dem wir bei jedem Knoten mit der oberen Schranke prüfen, ob es sich lohnt diesen weiter zu verfolgen, oder nicht. In dem Falle verfolgen wir nur diejenigen Knoten Weiter, die die höchstemöglichste Schranke besitzen:

Dabei ist es nicht zwangsweise immer die rechte Seite welche weiterverfolgt wird. Ein Weiteres Beispiel eines "Linken Auswahlbaumes" befindet sich im Buch ([1]) auf Seite 90 Abbildung 6.1.

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:

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 9 Orten sehr groß. in Diesem Fall gibt es 40320 verschiedene Rundreisen.

Bei bespielsweise 15 Orten wird bereits deutlich sichtbar, dass es unwirtschaftlich ist, so viele Routen zu berechnen (87.178.291.200 mögliche Rundreisen).

Wenn nun also ein Unternehmen mit vielen Punkten arbeiten will, bedarf es einer anderen Lösungsmöglichkeit.

Lösung mit Verzweigen und Beschränken

Übungen

Quellen

[1] Prof. Dr. Christian Wagenknecht: "Algorythmen und Komplexität"