Verzweigen und beschränken SS10
Inhaltsverzeichnis |
Autoren:
Mark Ziener (simkzien@stud.hs-zigr.de)
Mario Reichel (simareic@stud.hs-zigr.de)
Bewerten, auswählen und expandieren
Wiederholung Systematische Suche
Wie bereits in vorangegangenen Vorlesungen erwähnt, können die Lösungsbäume, ob mittels Tiefe- oder Breitesuchverfahren, sehr groß werden. So kommt es bei der systematisch Vollständigen suche zu einem exponentiellen Zeitaufwand. Bei einem 0/1 Rucksackproblem mit n=6 Entscheidungen, führt dies bereits zu 2^n also 64 äußeren Knoten. In einer Baumdarstellung kann dies einen schon fast erschlagen.
Nehmen wir noch als Beispiel ein Problem mit 2^{100} Problemen. Dies kann man Umformen in der Form 2^{100} = 2^{10*10} > 1000^{10} = 10^{30} .
Wenn man zugrunde legt das ein Rechner eine Milliarde Alternativen pro Sekunde abfragen und verarbeiten kann, so würde man für das gesammte Problem eine zeit von 10^{21} Sekunden benötigen. Dies würde das geschätzte Alter der Erde von 5 Milliarden Jahre übertreffen.
Wie kann man dem nun entgegenwirken? Man könnte versuchen bestimmte Teilbäume auszuschließen, die vermutlich zu keiner Lösung führen. Diese muüsen dann nicht mehr weiter expandiert werden (was man auch als „ausästen" bezeichnet). Dieser Ansatz würde den Lösungsprozess drastisch beschleunigen, aber natürlich nichts an exponentiellen Zeitaufwand ändern sondern diesen nur verringern, im Worst-Case-Fall kann es sogar auf den selben Zeitaufwand hinaus laufen.
Diesen Denkansatz nennt man Verzweigen und Beschränken (engl. Branch and Bound). Das Hauptproblem ist das finden der nicht zu expandierenden Knoten durch einen Bewertungsalgorithmus. Je mehr Knoten dadurch aussortiert werden, desto Geringer ist der Zeitaufwand.
Das ganze wird mittels einer Wertschranke (Bound) für jeden Knoten (Branch-Schritt) bewerkstelligt. Diese Garantiert, dass keiner der Folgeknoten eine bessere Bewertung erhält als der Aktuelle.
Die Bewertung der Knoten richtet sich dabei nach der Art des Problems. Nimmt man z.B. das Rucksackproblem so handelt es sich um ein Maximierungsproblem bei dem eine obere Wertschranke gesetzt wird. Durch diese wird immer der Knoten mit der Höchsten Bewertung verfolgt.
Bei der Suche nach dem kürzesten Weg handelt es sich wiederum um ein Minimierungsproblem. Es wird eine untere Schranken angelegt und der Knoten mit der geringsten Bewertung expandiert.
Das finden einer passenden Bewertungsfunktion ist dabei das größte Problem da diese immer per Hand an das zu suchenden Ergebnis angepasst werden muss. Das finden und gegebenenfalls Editieren dieser Funktionen setzt meist eine gewisse Erfahrung voraus.
Die Komplexität des Algorithmus zur Bound bestimmung spielt natürlich auch eine Rolle. Wenn die Wertschranke durch eine umfassende Berechnung genau bestimmt wird, fallen nahezu alle Knoten weg bis auf die zur optimalen Lösung führenden. Dadurch würde der Aufbau des Baumes zwar einen linearen Aufwand haben, der jedoch, je nach Algorithmus, mit einem enormen Berechnungsaufwand für den Bound zu kombinieren ist.
Wenn hingegen ein Algorithmus verwendet wird, dem nur eine sehr simple Berechnung zu Grunde liegt, ist kaum Aufwand nötig um die Wertschranke zu bestimmen. Doch ist diese sicherlich deutlich ungenauer wodurch man die Knoten nicht unbedingt strickt ausschließen kann, oder im Worst-Case-Fall wieder alle Knoten abarbeiten muss um die optimale Lösung zu finden. So muss man versuchen einen Mittelweg zwischen diesen beiden Extremen zu finden um einen Neherungswert für den Bound zu bilden.
Weiteres Problem ist, das durch den Neherungswert bestimmte Knoten nicht konsequent ausgeschlossen werden können. So ist es durchaus möglich, das ein Ast erweitert wird, bei dem sich später erst heraus stellt das er keine Ideale Lösung ist. Auf Grund dieser Tatsache ist es nötig, alle Knoten, sortiert nach ihrem Bound-Wert, in einer sogenannten Prioritätswarteschlange zu sammeln, um sie später evtl. wieder abrufen zu können. Später dazu mehr.
Bei der Visualisierung dieses Problems greifen wir wieder auf das Baumprinzip zurück:
Die hier verwendete Bewertungsfunktion ist eine einfache Addition der Werte, mit der Expansion beginnen wir an der Wurzel. Wir suchen nach einer Kombination aus den Werten 7 5 3 6 die 15 ergeben soll. Wir expandieren also den Knoten mit der Bewertung 7 und im Folgeschritt die 13 dieser führt allerdings nur zu Knoten deren Wert über 15 liegt und somit nicht als Ergebnis in Frage kommen. Nun ist es nötig zum Knoten mit der nächst besten Bewertung wechseln zu können welcher dann auch zum gesuchten Ergebnis 15 führt, aus diesem Grund werden alle Expansionskandidaten in einer Prioritätswarteschlange aufbewahrt. Sollten zwei Werte gleich sein, dann wird einer zufällig ausgewählt.
AVL-Baum (Prioritätswarteschlange)
AVL-Bäume sind Datentypen, die zur Implementierung von Ranglisten oder Prioritätslisten verwendet werden können. Sie repräsentieren eine Baumstrucktur, die ausbalanciert und geortnet ist.
In diesem AVL-Baum mit Balance-werten ist gut der hierarchische Aufbau zu erkennen. Ausgehend vom Wurzelelement, stehen immer links des jeweiligen Knoten kleinere Werte, rechts nur größere werte. Die Balance geht aus der Tiefe des rechten und linken Teilbaumes hervor. Wenn ein Teilbaum zu groß wird, dreht man die Elemente um eine möglichst gleichmäßiger Tiefe zu haben.
Dieser Baum muss einige Methoden beherschen:
Einfügen eines Elementes
Der Baum wird so lang verfolgt bis ein leerer Knoten erreicht ist, in dem man den neuen Wert Speichern kann. Dabei wird im Baum Ebene für Ebene abgestiegen. Wenn der vorhandene Wert größer ist als der einzufügende, wird zum linken Ast des Elementes verwiesen. Ist der Ist der Wert kleiner, wird nach rechts verwiesen.
Suchen eines Elementes
Es wird wie bei dem einfügen eines Elementes vorgegangen. Dieser Vorgang wird Ebene für Ebene wiederholt bis entweder das zu suchende Element gefunden wurde oder der letzte Knoten erreicht ist.
Ausbalancieren eines Baumes
Durch das Ausbalancieren der Äste eines Baumes, wird wie schon erwähnt erreicht das alle Äste eine relativ gleichmäßige Länge haben. Dadurch kommt erst der große Vorteil dieser Struktur zu tragen. Wenn man in einer Langen Liste ein Element sucht müsste man die gesammte Liste durch gehen bis das Element gefunden ist. Im Worst-Case-Fall ist dies ein aufwand von \mathcal {O} (n). Bei einem ausbalancierten Suchbaum hingegen liegt dieser Aufwand bei \mathcal {O} (log n).
Die AVL-Baum ist entartet, sobald der Wert für die Balance an einem Knoten größer 1 oder kleiner -1 ist. In diesem Falle müssen Elemente in diesem Baum gedreht werden. Zur Auswahl stehen dazu die einfach rechts und links Rotation und die doppelte rechts und links Rotation.
Eine Implementierung solch eines AVL-Baumes ist in einer etwas abgewandelten Form im Beispiel "Rundreiseproblem mit Branch and Bound" zu finden.
Anwendung auf das Rucksackproblem
Anwendung auf das Rucksackproblem
Das Rucksackproblem ist ein sehr weit verbreitetes Beispiel-Problem in der Komplexitätstheorie und beschäftigt sich mit der Suche nach der effektivsten Kombination von n Gegenständen mit einem bestimmten Gewicht, sowie einem bestimmten Wert, wobei das Gewicht eine bestimmte Grenze nicht überschreiten darf.
Anwendungsbeispiele hierfür kann man sich viele denken, sei es nun das Packen des Koffers für den Urlaub oder ein Juwelendieb der vor dem Eintreffen der Polizei, mit der maximal möglichen Beute, verschwinden möchte.
Ein naiver Ansatz zur Lösung ist hier schnell gefunden, das Erzeugen aller Möglichkeiten den Rucksack zu packen und die Ausgabe der Kombination mit dem höchsten Wert. Allerdings würden sich für 60 Gegenstände n^{60} Kombinationen ergeben, deren Berechnung bei vielleicht 10^9 Möglichkeiten pro Sekunde um die 30 Jahre dauern würde, bei 61 wären es dann schon über 60 Jahre. Man sieht also dass, einem ein exponentieller Anstieg, im wahrsten Sinne des Wortes schnell über den Kopf wachsen kann.
Mathematischer Formulierung:
Gegen sind:
* n = Anzahl der Objekte * gi = Gewicht von Objekt i * wi = Wert von Objekt i * G = das maximale Gewicht
Es wäre auch kein vielversprechender Ansatz die Gegenständen mit dem Höchsten Wert einzupacken, bis kein Platz mehr ist, da das Verhältnis von g_i zu w_i eine Rolle spielt.
Deswegen muss ein weiterer Wert definiert werden, der die Effektivität der einzelnen Objekte beschreibt, um Sie anschließend vergleichen zu können. Diesen nennen wir \frac{w_i}{g_i} und Ordnen die Elemente nach diesem sodass sichergestellt wird das dass Element mit der besten Bewertung an erster Stelle steht, da der dazugehörige Knoten die Wurzel bildet.
Der gesuchte Ergebnisvektor ist nun:
\sum \limits _{i=1}^n {x_i g_i} \leq K sowie
Beispiel
Wir haben 4 Objekte und eine Maximalen Kapazität von 10
\begin{array}{l|l|l|l|l} \text{i} & 1 & 2 & 3 & 4\\ \hline \text{w_i}& 4 & 7 & 11 & 9\\ \hline \text{g_1}& 1 & 4 & 5 & 5 \\ \hline \text{\frac{w_i}{g_i}}& 4 & 1.75 & 2.2 & 1.8 \end{array}Die Bewertungsfunktion ist Bewertung = aktuelle Wertsumme + (maximal Gewicht - aktuelle Gewichtssumme) * \frac{w_i}{g_i} des einzupackenden Objektes Geordnet ergibt sich dann
\begin{array}{l|l|l|l|l} \text{i} & 1 & 3 & 4 & 2\\ \hline \text{w_i}& 4 & 11 & 9 & 7\\ \hline \text{g_1}& 1 & 5 & 5 & 4 \\ \hline \text{\frac{w_i}{g_i}}& 4 & 2.2 & 2.8 & 1.75 \end{array}Nun bewerten wir den Wurzelknoten und es ergibt sich 0+(10-0)*4 = 40 Anschließend Berechnen wir für jeden Knoten den Bound und expandieren immer den Knoten mit der besten Bewertung. Dieses Objekt wird dann aus der Liste der Gegenstände entfernt, da es sich ja bereits im Rucksack befindet, so fahren wir fort bis entweder K erreicht ist oder kein Knoten mehr expandierbar ist