AuK/Verzweigen und beschränken SS09

Wiki-Quelltext dieser Seite.

==Motivation==
Beispiel mit grafischer Darstellung der Bäume und Aufwände
Bäume werden bei vollständiger Suche sehr groß -> exponetieller Aufwand
Beispiel für exponentiellen Zeitaufwand bei Baumaufbau


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

{|border="1"
|width="50pt"| i 
|width="50pt"| 1 
|width="50pt"| 2 
|width="50pt"| 3 
|width="50pt"| 4 
|-
|<math>w_i</math> ||3 ||5 ||10 ||10
|-
|<math>g_i</math> ||1 ||3 ||7 ||9
|-
|<math>\frac{w_i}{g_i}</math> ||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 <math>(n-1)!</math> verschiedene Rundreisen. -> anfang = ende
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}*(\frac{n}{e})^n*(1+\frac{1}{12n}+\frac{1}{288n^2}+\mathcal{O}(\frac{1}{n^3}))</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. -> 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.

{|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
|-
|}

===Lösung mit Branch and Bound===
Minimierungsproblem -> Knoten mit kleiner Schranke sind vorzuziehen

==Zusammenfassung==
Beispielergebnisse mit und ohne branch and bound