Verzweigen und beschränken SS10

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 muss 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 der und 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

Anwendung auf das Rucksackprinzip