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

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