Verzweigen und beschränken SS09
Inhaltsverzeichnis |
Motivation
Angenommen die Lösungssuche bei einem Problem lässt sich in einer Baumstruktur darstellen, dann sind die Blätter des Baumes die Lösungen. Wie wir bereits wissen können diese Lösungsbäume bei der systematischen und vollständigen Suche enorm groß werden.
Es ergibt sich also ein exponentieller Aufwand. ????????Aufwandsformel?????????
Ziel
Ausästen (ändert zwar nichts am exp. Aufwand aber hat trotzdem praktischen Nutzen) Maxima, Minimaproblem
Einführung branch and bound
Begriffsklärung branch, bound,
Bound
Boundoptimierung Bewertung Boundbestimmung Tafelbild
Bewertungsfunktion
Filter Schwierigkeit bei b'n'b ist Finden der Bewertungsfunktion
Prioritätenlisten, Expandierungskandidaten
Rucksackproblem
Beispiel: 3 gegenstände mit gewichten 1, 3, 7, 9 Werte: 3, 5, 10, 10
| i | 1 | 2 | 3 | 4 |
| w_i | 3 | 5 | 10 | 10 |
| g_i | 1 | 3 | 7 | 9 |
| \frac{w_i}{g_i} | 3 | 1.7 | 1.4 | 1.1 |
Maximalgewicht: 15
Ziel: finden des groeßten Wertes mit gmax <= K
an beispiel spezifischen wert erklaeren (in absteigender folge)
expandierungskandidat + prioritätsliste
Rundreiseproblem
Beim Rundreiseproblem handelt es sich um ein Optimierungsproblem. Es ist heute oft in der Logistikbranche anzutreffen. 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. -> anfang = ende Durch Anwendung der STIRLINGschen Formel ergibt sich allein für die Erstellung aller möglichen Rundreisen ein exponentieller Aufwand:
n! = \sqrt{2*\pi*n}*(\frac{n}{e})^n*(1+\frac{1}{12n}+\frac{1}{288n^2}+\mathcal{O}(\frac{1}{n^3}))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. -> Aufwand?????????????????????????????????????? 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.
| Anzahl der Städte | mögliche Rundreisen (n-1)! |
| 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 |
Lösung mit Branch and Bound
Minimierungsproblem -> Knoten mit kleiner Schranke sind vorzuziehen
Mögliche Schranke: Summer der aktuellen Teilweglänge vom Start bis zum nächsten unbesuchten Knoten -> einfache Schrankenfunktion aber schlecht, da Weg zum Nachbarknoten zwar kurz aber rest sehr lang sein kann -> besser: Einbeziehen aller hinführenden und wegführenden Kanten -> Näherungslösung
Frage: 6.2 Wie kommt man zu den Matrizen?
Zusammenfassung
Beispielergebnisse mit und ohne branch and bound