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)

==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!</math> verschiedene Möglichkeiten.

tabelle mit beispielwerten wegen fakultät

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