Verzweigen und beschränken SS09

Das Wiki ist noch nicht fertig!

Vorlesungsfolien: Branch_and_Bound.pdf

Motivation

Wie bekannt kann die Lösungssuche bei Problemen als Baum visualisiert werden. Wir wissen auch, dass die Lösungsbäume bei der systematischen und vollständigen Suche enorm groß werden. Es ergibt sich also ein exponentieller Aufwand. Betrachten wir den folgenden Baum.

\downarrow

Angenommen jede Kante und jede Knoten benötigt eine Grundoperation, dann würde die Erstellung des Baumes bei vollständiger Suche 33 Grundoperationen benötigen (17 Knoten + 16 Kanten). Wenn nun mit Hilfe von Branch and Bound der komplette rechte Teilbaum entfällt, so werden nur noch 13 Grundoperationen benötigt. Auch wenn wir nichts am exponentiellen Aufwand ändern können, so haben wir in dem Beispiel einen deutlichen praktischen Nutzen bemerkt.

Ziel

Unser Ziel ist es diesen exponentiellen Aufwand zu verringern.

a*k^n+b zu c*k^n+d mit c < a und/oder d < b

Ein Ansatz das zu erreichen besteht darin, Teilbäume, die wahrscheinlich nicht zum gewünschten Ergebnis führen, zu entfernen, den Baum also auszuästen.

Das Ausästen ändert zwar nichts am exponentiellen Aufwand, hat aber dennoch einen praktischen Nutzen.

Einführung branch and bound

Für das eben beschriebene Ausästen gibt es ein Hilfsmittel namens Branch and Bound (Verzweigen und Beschränken). Bei diesem Verfahren werden die Knoten des Lösungsbaumes bewertet. Je nach Bewertung der Knoten können nun diejenigen Knoten weiter verfolgt werden, welche die für das Problem beste Lösungsaussichten bieten. Im Idealfall muss also in jedem Schritt nur ein einziger Knoten verfolgt werden.

Wie kommen wir nun zu den Bewertungen? Dazu wird die so genannte Bewertungsfunktion benötigt. Das Finden der Bewertungsfunktion stellt die größte Schwierigkeit bei Branch and Bound dar. Es gibt kein Verfahren der das Finden der Bewertungsfunktion ermöglicht. Die Bewertungsfunktion ist immer von der konkreten Problemstellung und der eigenen Erfahrung abhängig. Das Finden einer guten Bewertungsfunktion ist Grundlage für die Optimierung der Bounds und somit zur Lösungsfindung.

Das Verzweigen (engl: branch) wird am besten deutlich wenn man sich die Erklärung zur Expandierung und Expandierungskandidtaten ansieht.

Schranke, Expandierung und Prioritätenliste

Je nach Problem kann man zwischen Minimierungs- und Maximierungsproblemen unterscheiden. Handelt es sich um ein Minimierungsproblem, so wird nun der Knoten mit der niedrigsten Bewertung expandiert. Als Beispiel für ein Minimierungsproblem wäre die Suche nach dem kürzesten Weg zwischen mehreren Stationen bzw. Orten zu nennen.

Analog dazu wird bei einem Maximierungsproblem der Knoten mit der höchsten Bewertung expandiert. Ein Beispiel hierfür ist die Auslastung der Produktionskapazität einer Fabrik, wo es darum geht die Produkte in der Kombination zu produzieren, das die Auslastung nicht überschritten wird und der maximale Gewinn mit den produzierten Gütern erzielt werden kann.

Die Schranken werden bei Minimierungsproblemen als untere und bei Maximierungsproblemen als obere Schranken angegeben.

Die Knoten eines Baumes dienen als Bewertungsziel und werden, je nach Güte, expandiert, dabei beginnt die Expandierung immer bei der Wurzel des Baumes. In jedem Schritt wird nur ein Knoten expandiert.

Es kann vorkommen das die Expandierung eines Knotens nicht zum Ziel führt. Aus diesem Grund sind auch die übrigen Knoten des Baumniveaus potentielle Expandierungskandidaten. Die Knoten müssen also gespeichert werden. Da die Bewertung der Knoten bei der Weiterverarbeitung eine Rolle spielt, bietet sich eine so genannte Prioritätenliste (engl: priority queue) an. In dieser sind die Expandierungskandidaten je nach Optimierungsproblem nach ihrer Bewertung geordnet.

Welcher Knoten expandiert wird entscheidet das Verfahren also anhand der Prioritätenliste, welche nach jeder Knotenbewertung aktualisiert wird. Expandiert wird immer das erste Element dieser Liste. Ist ein Knoten nicht mehr expandierbar wird er aus der Prioritätenliste entfernt. Damit ist die Position eines Knotens im Baum, für das Verfahren, irrelevant.

Expandierungsablauf: Wurde die Wurzel bewertet wird dieser Knoten mit seiner Bewertung in der Priotitätenliste eingeordnet. Als erstes und bisher einzigstes Element der PL wird dieser Knoten nun weiter expandiert. Der entstehende Kindsknoten wird bewertet und in die PL eingeordnet. Es wird nun geprüft ob der Elternknoten, der Knoten von dem aus expandiert wurde, noch Expandierbar ist. Ist dies nicht der Fall so wird dieser aus der PL entfernt. Erneut wird das erste Element der PL expandiert, dieses muss nicht zwangsweise der Elternknoten des zuletzt expandierten sein. Ist eine Bewertung des aktuell expandierten Knotens identisch mit der des Elternknoten wird der Kindknoten hinter diesem in der PL eingeordnet, da der Kindknoten nur gleichwertig ist.

Im worst-case-Szenario ist der Zielknoten der letzte Expandierungsschritt wobei alle Knoten des Baumes expandiert werden musten.

Rucksackproblem

Ein Mittel zur Beschreibung eines Sachverhaltes ist die formulierung eines Problem. Das 0/1-Rucksackproblem ist so ein Beispiel. Der Kontex ist das Entscheidungs-/Auswahl-Problem für eine Menge von Objekten welche je einen Wert und je ein Gewicht besitzen wenn eine Kapazität(Gewichts- oder Wert-Grenze) die Kombinationsmöglichkeit dieser Objekte beschränkt und die optimale Objektkombination gefunden werden soll.

Diese Optimum kann mit Hilfe von Branche and Bound mit geringem Aufwand gefunden werden. Das Ergebnis wird in Form eines Vektors dargestellt und somit ergibt sich folgende mathematische Formulierung:

\frac{w_i}{g_i} \geq \frac{w_i +1}{g_i +1} für alle Elemente 1 \leq i \leq n
Der gesuchte Vektor ist dabei \vec{x}=(x_1, x_2, ..., x_n), mit x_i \in \{0, 1\} sodass dessen Werte \sum \limits _{i=1}^{n} x_i g_i \leq K und \sum \limits _{i=1}^{n} x_i w_i \rightarrow max genügen.

Vorgehen: Wertepaare in eine Tabelle einordnen.
Ermitteln eines spezifischen Wertes (w_i / g_i) für jedes Wertepaar.
Absteigende Ordnung der Spalten nach dem spezifischen Wert.

Beispiel: 4 Objekte
Gewichten: 1, 3, 9, 7
Werte: 3, 5, 10, 11
Kapazität: 4

Obj={(1,3),(3,5),(9,10),(7,11)}

Somit ist sichergestellt das das Objekt mit dem besten spezifischen Wert als erstes eingepackt wird.

Bewertungsfunktion:= Aktuelle Wertsumme + (Kapazität - Gewichtssumme) * spezifischer Wert des einzupackenden Gegenstandes

Ziel: finden des groeßten Wertes mit gmax <= K

Rundreiseproblem

Beim Rundreiseproblem handelt es sich um ein Optimierungsproblem. Es ist heute oft in der Logistikbranche anzutreffen. Gesucht ist dabei die kürzeste Rundreise, wobei jede Stadt genau einmal besucht werden muss. Für die Distanzen zwischen den Städten wird eine sogenannte Entfernungsmatrix benötigt. In dieser Matrix werden unzulässige Verbindungen als unendlich markiert.

Naiver Algorithmus

Der offensichtlichste Ansatz das Rundreiseproblem zu lösen besteht darin, alle möglichen Rundreisen zu generieren. Daraus ergeben sich (n-1)! verschiedene Rundreisen. Die Anfangsstadt ist auch gleichzeitig die Zielstadt. Durch Anwendung der STIRLINGschen Formel ergibt sich allein für die Erstellung aller möglichen Rundreisen ein exponentieller Aufwand:

Die eigentliche Bestimmung der Lösung ist in diesem Aufwand noch nicht inbegriffen!

Nachdem alle möglichen Rundreisen erstellt wurden, können mit Hilfe der Entfernungsmatrix die einzelnen Längen der Reisen berechnet werden. Anschließend wird die Reise mit der kürzesten Entfernung als Ergebnis genommen.

Das eben beschriebene Verfahren sieht sehr einfach aus. Warum wird es also nicht in der Praxis genutzt? Dazu reicht ein Blick in die folgende Tabelle.

Lösung mit Branch and Bound

Beim TSP handelt es sich um ein Minimierungsproblem, d.h., Knoten mit kleiner Bewertung sind vorzuziehen.

Welche Möglichkeiten der Schrankenbestimmung haben wir nun?

Man könnte die Summe der aktuellen Teilweglängen vom Start bis zum nächsten unbesuchten Knoten berechnen. Diese Schrankenfunktion ist zwar einfach, führt aber nicht zum Ziel, da zwar der der aktuelle Weg kurz sein kann, der Rest aber sehr lang.

Eine bessere Variante wäre die Einbeziehung aller hinführenenden und wegführenden Kanten (und anschließende Division durch zwei um Doppelzählung zu vermeiden). Dadurch erhält man allerdings nur eine Näherungslösung.

Eine Möglichkeit, die auch wirklich zur kürzesten Rundreise führt besteht in der Verwendung von Entfernungsmatrizen. In dieser Matrix werden alle nicht möglichen Strecken mit unendlich markiert (in jedem Knoten neu). Durch Reduktion der Matrix kann somit sogar die Länge der kürzesten Rundreise ermittelt werden. Eine detailliertere Beschreibung kann im Buch auf Seite 95 f. nachgelesen werden.

Zusammenfassung

kurzfassung von b n b

Bewertung was b n b bringt

alternativen, einordnung von b n b

Beispielergebnisse mit und ohne branch and bound

Übung

1. Stellen sie die Signatur und Axiome für den abstrakten Datentyp priority queue auf. (zur Hilfe: Wikipedia-ADT)
   

2. Gegeben ist folgender Baum mit Knotenbewertungen (Maximierungsproblem):
   

   

   
   Verinnerlichen sie sich die Funktionsweise der priority queue, indem sie den Inhalt der priority queue in jedem Schritt aufschreiben!
   

3. Gegeben sind folgende 4 Gegenstände (Wert . Gewicht):
   (3 . 1)
   (5 . 3)
   (10 . 9)
   (11 . 7)
   
   Die Kapazität des Rucksacks beträgt 12.
   Die Bewertungsfunktion ist die Selbe wie die im Buch auf Seite 90 verwendete.
   (Bewertungsfunktion := Aktuelle Wertsumme + (Kapazität - Gewichtssumme) * spezifischer Wert des nächsten Gegenstandes)
   Finden sie die optimale Gegenstandskombination. Stellen sie dazu zuerst wie auf Seite 89 im Beispiel 6.1 zu sehen eine Tabelle mit den spezifischen Werten auf.
   

4. Überprüfen sie, dass die Lösung des TSP auf Seite 96 im Bild 6.2 auch wirklich das korrekte Ergebnis liefert.

5. Gegeben ist folgende Entfernungsmatrix:
   

   von\nach	Dresden	Zittau	Görlitz	Bautzen
   Dresden	\infty	108	109	63
   Zittau	114	\infty	37	46
   Görlitz	110	35	\infty	49
   Bautzen	65	46	51	\infty

   
   Ermitteln sie die kürzeste Rundreise zwischen den Städten. (Tipp: sie können ihr Ergebnis mit google-maps kontrollieren)

Lösungen