Verzweigen und Begrenzen
Inhaltsverzeichnis |
Einführung
Prinzip
Verzweigung
Bei der Verzweigung werden von einem Knoten des Entscheidungsbaumes aus zwei oder mehrTeilprobleme erzeugt. Die Art der Aufspaltung in Teilprobleme hängt immer vom betrachteten Problem ab. Es gibt verschiedene Auswahlverfahren für die Wahl des nächsten zu bearbeitenden Knotens im Aufteilungsbaum, die unterschiedliche Zielsetzungen haben. Die haeufigste verwendete Methoden sind Tiefensuche und Breitensuche
Tiefensuche
- Mit dieser Auswahlregel arbeitet sich das Verfahren im Baum möglichst schnell in die Tiefe .
- Hier geht man so weit wie möglich einen gewählten Pfad entlang. Wenn man am Ende eines Zweiges angekommen ist, geht man schrittweise zurück, bis man in einen bislang unbesuchten Teilbaum absteigen kann. Ist man wieder am Startknoten angelangt und es gibt keine unbesuchten Knoten, die mit dem Startknoten durch eine Kante verbunden sind, dann ist man fertig.
- Dieses Verfahren nennt man Backtracking: Man geht solange man kann, wenn man nicht mehr weiter kommt, geht man zurück bis man einen anderen Weg findet.
Breitensuche
- Die Breiten Suche ist ein Algorithmenmuster, das die Knoten eines Graphen nach der Entfernung von einem Startknoten geordnet durchläuft. Zuerst werden alle von diesem Startknoten direkt durch eine Kante erreichbaren Knoten bearbeitet, danach die mit zwei Kanten Entfernung, dann die mit drei usw.
- -Knoten werden in der Reihenfolge mit zunehmenden Abstand vom Startknoten aus besucht.
- -Nachdem alle Knoten mit Abstand d verarbeitet wurden, werden die mit d + 1 angegangen.
- -Die Suche terminiert, wenn in Abstand d keine Knoten auftreten.
- -Die Tiefe des Knotens v im Breitensuchbaum ist seine kürzeste Kantendistanz zum Startknoten.
- -Die zu verarbeitenden Knoten werden als FIFO-Queue (first-in first-out) organisiert.
- -Es gibt eine einzige „Verarbeitungsmöglichkeit“ für v, nämlich, wenn es aus der Queue entnommen wird
Beschränkung
Für jeden aus einem Verzweigungsschritt erzeugten Knoten wird eine Beschränkung, die sogenannte Wertschranke, bestimmt. Abhängig davon, ob ein Optimum maximaler- oder minimaler Gestalt gesucht wird, stehen verschiedene Verfahren zur Ermittlung der Wertschranke zur Verfügung. Die Schranke gibt an, dass für den aktuellen Knoten v_i mit Wertschranke bound_{v_i} kein durch Expansion erzeugter Folgeknoten v_{i+n} mit bound_{v_{i+n}} > bound_{v_i} existiert.
bound_{v_i}von\qquad v_i\colon \enspace \nexists v_{i+n}\mid bound_{v_{i+n}} > bound_{v_i}\mid n\in \mathbb{N}
Veranschaulichung
Schaut man sich einige Beispiele für eine Mögliche Abfolge bei verschiedenen Bäumen und unterschiedlichen Bewertungen an, wird schnell klar, dass eine Begrenzung große, irrelevante teilprobleme abschneiden und das Hauptproblem so erheblich verkleinern kann. Dies ist jedoch von den erhaltenen wertschranken abhängig. Im schlimmsten Fall wird keine Optimierung erreicht.
Einfaches Beispiel
<popup name="Erläuterung">
Es ist zu beachten, dass es sich bei diesem Beispiel um ein Worst-Case-Szenario handelt.</popup>
Größeres Beispiel
<popup name="Erläuterung">
Das Problem konnte verkleinert werden.</popup>
Dominanztest
Rucksackproblem
- Das Rucksackproblem ist ein Optimierungsproblem der Kombinatorik. Von Lösungsalgorithma her das Rucksackproblem ist einer der bekanntesten NP-Hard Probleme.
Es sei es gibt 'n' Gegenstände mit den Gewichten g_1,g_2 , \cdots , g_n und werten w_1, w_2 , \cdots , w_n . Gewicht der i ten Gegenstand ist g_i und Wert der i ten Gegenstand ist w_i Die Interpretation des Wertes wird durch den jeweiligen Sachkontext bestimmt.
- Das aktuelle Gesamtgewicht des Rucksacks darf die Maximalkapazitaet , sei K , nicht übersteigen.
Mathematische Schreibweise der 0/1 Rucksackprobleme ;
\sum_{i=1}^n {x_i}{ω_i} -> max , wobei \sum_{i=1}^n{x_i}{g_i} \leq K mit x_i \in {0,1}