Verzweigen und beschränken SS09

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.

\downarrow

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.

Es ergibt sich also ein exponentieller Aufwand. ????????Aufwandsformel?????????

Ziel

Unser Ziel ist es diesen exponentiellen Aufwand zu verringern.

c*n^k zu b*n^k mit b \leq c

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.

Beispiel: zeigen das Teilbäume unwichtig sein können Tafelbild: 4 Städte, gesucht 1 nach 4, 3 ist extrem weit entfernt mit dazugehörigen Baum

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

Bei einem Binärbaum zum Beispiel könnte bereits im ersten Schritt mit etwas Glück der halbe Baum entfernt werden.?? ist das nicht immer so bei binärer Suche?????

Beispiel: Aufwandsgegenüberstellung

Einführung branch and bound

Für das eben beschriebene Ausästen gibt es ein mathematisches 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.

BEISPIEL

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.

Expandierung und Prioritätenlisten

Die Expandierung beginnt bei der Wurzel des Baumes. Dazu werden alle möglichen Folgeknoten ermittelt und bewertet.

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 nennt werden bei Minimierungsproblemen als untere und bei Maximierungsproblemen als obere Schranken angegeben.

Es kann sein 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.

Expandiert man einen Knoten im Niveau n, so erhält man alle Knoten des Niveaus n+1. Diese werden nun bewertet und in die Prioritätenliste eingetragen. Das erste Element der Prioritätenliste wird expandiert (man erhält also die Knoten im Niveau n+2). Führt nun die Expandierung dieses Knotens nicht zum Ziel, so muss der Expandierungskandidat verworfen werden und mit dem nächsten Element in der Prioritätenliste fortgefahren werden.

Rucksackproblem

Beispiel: 3 gegenstände mit gewichten 1, 3, 7, 9 Werte: 3, 5, 10, 10 Maximalgewicht: 15

an der Tafel entwickeln

Formeln aus Buch erklären Wieso Rucksack nochmal? (Maximierungsproblem) -> was machen wir anders als die vorige gruppe Wie ermittelt man Gewichte Wozu spezifischer Wert

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

an beispiel spezifischen wert erklaeren (in absteigender folge)

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:

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.

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?

Beispiel: zwei Schritte an der Tafel, rest präsentation

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