Verzweigen und beschränken SS09
Aus ProgrammingWiki
Archivierte Version vom 2009-04-21T10:30:49+00:00. Aktuelle Version
Inhaltsverzeichnis |
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 |
| w_i | 3 | 5 | 10 | 10 |
| g_i | 1 | 3 | 7 | 9 |
| \frac{w_i}{g_i} | 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