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

==Rundreiseproblem==

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