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

{|
| i || 1 || 2 || 3 || 4 
|-
|<math>w_i</math> |3 |5 |10 |10
|<math>g_i</math> |1 |3 |7 |9
|<math>\frac{w_i}{g_i} |3 |1.7 |1.4 |1.1
|}

Maximalgewicht: 15

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

an beispiel spezifischen wert erklären (in absteigender folge)


==Rundreiseproblem==

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