AuK/Verzweigen und beschränken SS09

Wiki-Quelltext dieser Seite.

<language>Java</language>
Das Wiki ist noch nicht fertig!

Vorlesungsfolien: <document>Branch_and_Bound.pdf</document>

==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.

<center>[[Bild:Suchbaum.png]]
<br />
<math>\downarrow</math>
<br />
[[Bild:Suchbaum3.png]]
</center>

Angenommen jede Kante und jeder 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.

<math>a*k^n+b</math> zu <math>c*k^n+d</math> mit <math>c < a</math> und/oder <math>d < b</math>.
Wir wollen also die Aufwandsfunktion so beeinflussen, dass sie unterhalb der Aufwandsgleichung ohne Verzweigen und Beschränken liegt.

<center>
<gnuplot>
set title "Aufwandsziel"
set yrange [0:50]
set xrange [0:3]
set xlabel "n"
set ylabel "T(n)"
plot 3*10**x+10, 10**x
</gnuplot>
</center>

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

==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==


<!-- 
Warum spezifischer Wert ? 
Teilüberschriften formatieren
Formulierung bei den mathematischen Beschreibungen ausbessern
-->


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.<br/>

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:<br/>

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

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



Beispiel: 
4 Objekte<br/>
Gewichten: 1, 3, 9, 7<br/>
Werte: 3, 5, 10, 11<br/>
Kapazität: 4<br/><br/>
Obj={(1,3),(3,5),(9,10),(7,11)}<br/>

{|border="1"
|width="50pt"| &nbsp;i 
|width="50pt"| 1 
|width="50pt"| 2 
|width="50pt"| 3 
|width="50pt"| 4 
|-
|&nbsp;<math>w_i</math> ||3 ||5 ||11 ||10
|-
|&nbsp;<math>g_i</math> ||1 ||3 ||7 ||9
|-
|&nbsp;<math>\frac{w_i}{g_i}</math> ||3 ||1.7 ||1.6 ||1.1
|}
<br />
Somit ist sichergestellt das das Objekt mit dem besten spezifischen Wert als erstes eingepackt wird.

Bewertungsfunktion = aktuelle Wertsumme + (Kapazität - aktuelle Gewichtssumme) * spezifischer Wert des einzupackenden Objektes


Ziel: Ergebnissvektor finden mit maximalen Werte beim einhalten der Kapazitätsgrenze.

==Rundreiseproblem==
Beim Rundreiseproblem (engl.: traveling salesman problem) handelt es sich um ein Optimierungsproblem, genauer gesagt ein Minimierungsproblem.
Gesucht ist dabei die kürzeste Rundreise, wobei jede Stadt genau einmal besucht werden muss.


Es ist heute oft in der Logistikbranche anzutreffen.
Es sind jedoch auch andere Anwendungsgebiete denkbar, wie zum Beispiel Maschinensteuerung.

'''Beispiel: Plotter'''

Angenommen wir wollen ein Viereck mittels eines Plotters zeichnen.

<center>[[Bild:Plotter.png]]</center>

Weiter nehmen wir an, dass das Zeichnen jeder Strecke 10 ms und das Anheben/Absetzen 1 ms in Anspruch nimmt.
Das bewegen des Schreibkopfes soll ebenfalls 10 ms für jede Strecke dauern.

Die Reihenfolge, in der die Seiten gezeichnet werden wählen wir zufällig:
<math>\overline{AB}, \overline{CD}, \overline{BC}, \overline{AD}</math>

Unter der Annahme, dass sich der Plotter bereits im Punkt <math>A</math> befindet wird die Zeit, die zum Zeichnen des Vierecks benötigt wird folgendermaßen berechnet;
 <math>t_{Gesamt} = t_{Absetzen} + t_{\overline{AB}} + t_{Anheben} + t_{\overline{BC}} + t_{Absetzen} + t_{\overline{CD}}\ldots</math> 
Daraus würde sich eine Gesamtzeit von 91 ms ergeben.

Würden wir die einzelnen Strecken allerdings in einer bestimmten Reihenfolge zeichnen, so würden einige unütze Bewegungen des Schreibkopfes entfallen.
Unsere neue Zeichenreihenfolge sieht folgendermaßen aus:
<math>\overline{AB}, \overline{BC}, \overline{CD}, \overline{DA}</math>
Mit dieser Reihenfolge konnte die Gesamtzeit auf 43 ms reduziert werden.

Für Privatanwender mag diese Zeitersparnis auf den ersten Blick kaum relevant sein. Allerdings haben wir in dem Beispiel nur ein kleines Viereck gezeichnet.
In der Praxis (z.B. Ingenieurbüro) werden sehr viel komplexere Zeichnungen erstellt und ein Plottvorgang kann durchaus mehrere Minuten (im Extremfall sogar Stunden) dauern.
Ein anderes Beispiel wären auch Fräsmaschinen. Da in Unternehmen häufig die Formel <math>Zeit=Geld</math> zutrifft (genau genommen kann man die Größen Zeit und Geld nicht gleichsetzen, da sie unterschiedliche Einheiten haben, besser wäre zu sagen, dass sich Zeit und Geld in einem proportionalem Verhältnis befinden) kommt es auf jede Zeitersparnis an. Nicht zuletzt wird durch die Optimierung
der Maschinenwege auch deren Abnutzung verringert. 

===Naiver Algorithmus===
Der offensichtlichste Ansatz das Rundreiseproblem zu lösen besteht darin, alle möglichen Rundreisen zu generieren.
Daraus ergeben sich <math>(n-1)!</math> 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:

<math>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)</math>

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.

{|border="1"
|-
|'''Anzahl der Städte''' || '''mögliche Rundreisen <math>(n-1)!</math>'''
|-
|3 || 2
|-
|5 || 24
|-
|10 || 362.880
|-
|15 || 87.178.291.200
|-
|20 || 121.645.100.408.832.000
|-
|50 || 608.281.864.034.267.560.872.252.163.321.295.376.887.552.831.379.210.240.000.000.000
|-
|}

===Mögliche Bewertungsfunktionen===
Wie wir gesehen haben ist der naive Ansatz zur Lösung des Rundreiseproblem zwar einfach zu verstehen, hat also eine geringe kognitive Komplexität, ist in der Praxis jedoch nicht anwendbar.
Folglich müssen wir nach einem effizienteren Algorithmus zur Lösung des Rundreiseproblems suchen.

Unser erster Ansatz besteht darin, die Summe der Teilweglängen der bisherigen Teilstrecke zu nehmen und die Entfernung bis zum nächsten unbesuchten Knoten dazu zu addieren.
Das Problem dieses Ansatzes besteht darin, dass zwar der bisherige Weg und der Weg zum nächsten Ort kurz sein kann, der Restweg dafür aber extrem lang.

Es wäre auch möglich, die Bewertung an Hand aller hinführenden und wegführenden Strecken zu ermitteln. Diese würde man addieren und durch zwei teilen, um eine Doppelzählung zu vermeiden.
Man bekommt durch dieses Verfahren allerdings nur eine Näherungslösung.

Wir sind also immer noch nicht an unserem Ziel angekommen, eine Bewertungsfunktion zu finden, welche uns das optimale Ergebnis liefert.

===Lösung mit Branch and Bound===
Um das Problem mit Verzweigen und Beschränken lösen zu können benötigen wir eine Bewertungsfunktion.
Eine Möglichkeit, die auch wirklich zur kürzesten Rundreise führt besteht in der Verwendung von Entfernungsmatrizen für die Distanzen zwischen den Städten.
In dieser Matrix werden unzulässige Verbindungen mit \<math>\infty</math> markiert.
Entfernungsmatrizen müssen nicht symmetrisch sein. Auf Grund von Einbahnstraßen etc. kann es durchaus sein, dass Hin- und Rückweg unterschiedlich sind.

Das Verfahren funktionert folgendermaßen:

Als Ausgangsmatrix kommt die gegebene Entfernungsmatrix zum Einsatz.
Im ersten Schritt wird diese Ausgangsmatrix reduziert. Diese Reduktion geschieht so:
Zuerst wird für jede Zeile das Minimum ermittelt. Dieses Minimum wird in eine extra Spalte rechts neben die Zeile geschrieben.
Danach wird das Minimum von allen Zellen in der Zeile subtrahiert. Das Ergebnis wird dann in der entsprechenden Zelle als Fußnote an den Ausgangswert angefügt.
Nachdem die Zeilenminima gebildet wurden, werden die Spaltenminima der eben berechneten Fußnoten gebildet. Die Spaltenminima werden in eine neue Zeile
unterhalb der Matrix geschrieben. Um die konkrete Knotenbwertung zu erhalten werden nun alle Zeilen- und Spaltenminima addiert.
An Hand der Bewertung wird der Knoten nun in die priority queue eingefügt.

Als nächstes ermittelt man die Matrix, die im Knoten (<math>i \rightarrow j</math>) benötigt wird. Dazu wird in Zeile <math>i</math> und Spalte <math>j</math> der Wert aus der Ausgangsmatrix übernommen.
Anschließend müssen einige Zellen mit <math>\infty</math> markiert werden. Dies geschieht an Hand folgender Regeln:

<ol>
<li>Setze <math>E[z,j]=\infty</math> für alle <math>z \neq i</math>, denn <math>j</math> wird genau von <math>i</math> aus besucht.</li>
<li>Setze <math>E[i,s]=\infty</math> für alle <math>s \neq j</math>, denn ein Weg von <math>i</math> zu einem anderen Knoten als <math>j</math> ist verboten.</li>
<li>Setze <math>E[j,i]=\infty</math>, denn der Weg von <math>j</math> nach <math>i</math> steht nicht mehr zur Verfügung.
</ol>

Hat man diese Modifikationen vorgenommen, kann wieder die Bewertung ermittelt werden. Der Knoten wird dann ebenfalls in die priority queue eingefügt.
Der Vorgang wiederholt sich dann für jeden Knoten, der in der priority queue an vorderster Stelle steht. Kann ein Knoten nicht mehr expandiert werden, so wird er aus der priority queue entfernt.

An Hand der Übung 5 und der dazugehörigen Lösung kann der Algorithmus Schritt für Schritt nachfolzogen werden.

==Übung==
<ol>
<li>
Stellen Sie die Signatur und Axiome für den abstrakten Datentyp priority queue auf.
(zur Hilfe: [http://de.wikipedia.org/wiki/Abstrakter_Datentyp#Mathematisch-axiomatische_und_-algebraische_Methode Wikipedia-ADT])
<br />
</li>
<li>
Gegeben ist folgender Baum mit Knotenbewertungen (Maximierungsproblem):<br />
<center>[[Bild:Aufgabe2.png]]</center>
<br />
Verinnerlichen Sie sich die Funktionsweise der priority queue, indem sie den Inhalt der priority queue in jedem Schritt aufschreiben!
<br />
</li>
<li>
Gegeben sind folgende 4 Gegenstände (Gewicht . Wert):
<br />
(1 . 3)
<br />
(3 . 5)
<br />
(9 . 10)
<br />
(7 . 11)
<br />
<br />
Die Kapazität des Rucksacks beträgt 12.
<br />
Die Bewertungsfunktion ist die Selbe wie die im Buch auf Seite 90 verwendete.
<br />
(Bewertungsfunktion := Aktuelle Wertsumme + (Kapazität - Gewichtssumme) * spezifischer Wert des nächsten Gegenstandes)
<br />
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.
<br />
</li>
<li>
Überprüfen Sie, dass die Lösung des TSP auf Seite 96 im Bild 6.2 auch wirklich das korrekte Ergebnis liefert.
</li>
<li>
Gegeben ist folgende Entfernungsmatrix:<br/>
{|border="1"
|width="50pt"| '''von\nach''' 
|width="50pt"| '''Dresden'''
|width="50pt"| '''Zittau'''
|width="50pt"| '''Görlitz''' 
|width="50pt"| '''Bautzen''' 
|-
|'''Dresden''' ||<math>\infty</math> ||108 ||109 ||63
|-
|'''Zittau''' ||114 ||<math>\infty</math> ||37 ||46
|-
|'''Görlitz''' ||110 ||35 ||<math>\infty</math> ||49
|-
|'''Bautzen''' ||65 ||46 ||51 ||<math>\infty</math>
|}
<br />
Ermitteln sie die kürzeste Rundreise zwischen den Städten. (kontrollieren Sie das Ergebnis mit [http://maps.google.de/ Google-Maps])
</li>
</ol>

[[Verzweigen und beschränken - Loesungen|Lösungen]]