AuK/Verzweigen und beschränken SS09

Wiki-Quelltext dieser Seite.

==Motivation==

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