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