Verzweigen und beschränken SS11

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche

Loading
Autoren:


Inhaltsverzeichnis

Bewerten, auswählen und expandieren

Lösungsbäume oder auch "Zustandsraum-Bäume" genannt, können bei systematischer und vollständiger Aufstellung sehr groß werden, wenn es sich bei dem Lösungsalgorithmus um einen Algorithmus mit exponentiellen Aufwand handelt (Beispiel "Schach-Lösungsbaum"). Daraus entspringt die Motivation, Lösungsbäume zu begrenzen und Teilbäume auszusondern, welche für die Lösung definitiv nicht in Frage kommen. Das Problem dabei ist, eben genau die Teilbäume herauszufiltern, die keinen Lösungsweg bringen können. Allerdings steht fest, dass mit dem als "Ausästen" beschriebenen Vorgehen nichts am exponentiellen Zeitaufwand verändert wird, dies sogar im Worst Case gar keine Zeitersparnis bringt. Allerdings ist in den meisten Fällen der praktische Wert des Vorgehens deutlich.


Vorgehensweise:

Das Verfahren "Branch and Bound" arbeitet wie folgt: Für jeden Knoten (branch) wird eine Wertschranke (bound) ermittelt. Diese besagt, dass keiner der folgenden Knoten nach diesen Branch eine bessere Bewertung erhält. Bei Maximierungsproblemen werden dabei obere, bei Minimierungsproblemen untere Schranken angegeben. Der Lösungsbaum entsteht dabei durch die Weiterverfolgung des besten Knotens – dem besten Bound. Bei einer Gleichheit mehrerer Bounds wird dabei zufällig einer der Bounds ausgewählt. Um eine Verschlechterung von Knoten in späteren Schritten entgegenzutreten, werden alle vorhergehend aussortierten Expansionskandidaten aufbewahrt, sortiert nach dem Aufwandsfaktor der Bounds, um einen möglichst kleinen Zwischenspeicherbedarf zu haben. Dafür eignen sich besonders sogenannte Prioritätswarteschlangen (priority queue). Diese sind Datentypen, mit dem wir uns später befassen werden.

Problem:

Sofern sich die Schrankenberechnung sehr stark an der Optimierungsaufgabe orientiert, erhält man zwar sehr genaue Werte, muss allerdings äußerst hohe Kosten (Zeitaufwände) in Kauf nehmen. Sofern der Aufwand gering gehalten werden soll, wird eine einfache Schrankenfunktion gewählt, allerdings mit dem Risiko, dass die Bounds nicht optimiert werden und nur ein Näherungswert erzielt wird.

Das Bedeutet
Je genauer die Schrankenfunktion, desto kleiner der Suchbaum, aber desto länger die Berechnungsdauer
Je oberflächlicher die Schrankenfunktion, desto kürzer die Berechnungsdauer, aber desto größer der Suchbaum.

Beispiel:

Bei Schachprogrammen wird ein ähnliches Verfahren genutzt. Dabei werden die optimalen Knoten für i Züge berechnet. Dabei können auch Opferungszüge eingebaut werden, welche auf den ersten Blick schlecht erscheinen, allerdings im Nachhinein einen Vorteil bewirken. Damit können auch Näherungslösungen als wertvoll eingestuft werden. Allerdings wird dennoch stets nach einer echten Bewertungsfunktion gesucht.


Anwendung auf das Rucksackproblem

Das uns bereits bekannte Rucksackproblem lässt sich mit dem "Branch and Bound" Verfahren sehr gut umsetzen.

Dazu benötigt man zuerst einen ein Wertequotient der den einzelnen Wert eines Gegenstandes in Abhängigkeit seines Gewichtes darstellt. Um jetzt die Selektion der einzelnen Objekte darzustellen, eignet sich die Darstellung in einem Vektor, in dem die Position den Gegenstand in der Ordnung repräsentiert und dessen Wahrheitswert für die Einbeziehung des jeweiligen Objektes in den Rucksack steht. 

Werte-Quotient: 

Ordnung der Gegenstände: 

Vektor der ausgewählten Gegenstände:  mit 

Die optimale Lösung wäre nun:  Gesamtgewicht   &    max

Um den Vektor der optimalen Lösung zu erhalten benötigen wir zuerst einen Breitesuchbaum, den wir mit Hilfe der Schranken des "Branch and bound" Verfahrens schrittweise einschränken. Dazu benötigen wir folgende Überlegung: Um einen Knoten bewerten zu können, bestimmen wir zuerst seinen noch maximal erreichbaren Wert, indem wir den aktuellen Gegenstand so oft dazu packen wie er reinpasst und dann den Wert bestimmen. Mathematisch betrachtet multiplizieren wir den Wertequotienten des aktuellen Gegenstandes mit der Restkapazität. 

Bereits im Rucksack (aktueller Wert): 

Restkapazität: 

Obere Schranke für zusätzlichen Wertegewinn:


Maximal erreichbarer Wert bei Weiterverfolgung des aktuellen Knotens:

aktueller Wert + Restkapazität * akt. Wertequotient

Nun können wir den Knoten mit der besten Wertevorhersage weiterverfolgen, da alle anderen Knoten aufgrund der Ordnung der Objekte nur niedrigere Werte erreichen können.

Beispiel:

Wir besitzen folgende Gegenstände:

i 1 2 3 4
15 10 6 4
6 4 3 2
3 2.5 2 2

Unser Rucksack hat dabei eine Kapazität von K = 11.

Wird bilden nun einen Breitensuchbaum, bei dem wir bei jedem Knoten mit der oberen Schranke prüfen, ob es sich lohnt diesen weiter zu verfolgen, oder nicht. In dem Falle verfolgen wir nur diejenigen Knoten Weiter, die die höchstmöglichste Schranke besitzen:

S3erjaeh Animation Breitensuchbaum bsp1.gif

Dabei ist es nicht zwangsweise immer die rechte Seite welche weiterverfolgt wird. Ein weiteres Beispiel eines "Linken Auswahlbaumes" befindet sich im Buch ([1]) auf Seite 90 Abbildung 6.1.

Das Rundreiseproblem

Problemstellung

Das Rundreiseproblem (englisch: travelling salesman problem) ist eine klassische logistische Problematik mit einer großen Palette an modernen Anwendungsbeispielen. Dabei wird eine minimale Route zwischen einer Anzahl von Punkten gesucht, die alle abgearbeitet werden müssen. Es ist also ein klasisches Minimierungsproblem.

Annahme: Ein Lieferproblem von einem Heimatort zu 4 Lieferorten

Img2.png

Es gibt nun 4! mögliche Routen:

ABCD ABDC ACBD ACDB ADBC ADCB

BACD BADC BCAD BCDA BDAC BDCA

CABD CADB CBAD CBDA CDAB CDBA

DABC DACB DBAC DBCA DCAB DCBA

Dabei gehen wir davon aus, dass H jeweils als Start- und Zielort feststeht.

Dabei lassen sich unnötige und unwirtschaftliche Routen ausgliedern, um eine minimalisierte Lösung zu finden, also eine möglichst kurze Strecke.

Naiver Algorithmus

Ein Ansatz zur Lösung des Problems ist ein Algorithmus, der zuerst alle möglichen Routen ((n-1)!) generiert. Dabei entsteht ein exponetieller Aufwand mit der Formel:

In diesem Aufwand ist der eigentliche Lösungsaufwand noch nicht inbegriffen sondern nur der Aufwand zur Berechnung der möglichen Lösungen.

Nachdem die Lösugen generiert wurden, kann als mit Hilfe von Entfernungsmatrizen die kürzeste Strecke herausgefunden werden.

Dies lässt eine simple Lösung vermuten.

Deutschland.gif

Allerdings wird der Aufwand durch seine exponentielle Natur schon bei nur 9 Orten sehr groß. in Diesem Fall gibt es 40320 verschiedene Rundreisen.

Bei bespielsweise 15 Orten wird bereits deutlich sichtbar, dass es unwirtschaftlich ist, so viele Routen zu berechnen (87.178.291.200 mögliche Rundreisen).

Wenn nun also ein Unternehmen mit vielen Punkten arbeiten will, bedarf es einer anderen Lösungsmöglichkeit.

Lösung mit Verzweigen und Beschränken

Um ein solches Entfernungsproblem mit Branch and Bound lösen zu können, müssen wir uns zuerst wieder Gedanken über eine Bewertungsfunktion machen, die bestimmt ob es sinnvoll ist diesen Knoten weiter zu verfolgen, oder lieber einen anderen zu nutzen. Dazu ist es sinnvoll zuerst zu überlegen wie man selbst als Mensch an so ein Problem heran gehen würde. Eine solche Umsetzung in einen Algorithmus nennt man Heuristik. Man erhofft sich von Heuristiken eine schnelle und gute Lösung, die aber nicht immer die beste und schnellste Lösung ist, sondern nur eine Näherungslösung in überschaubarer Zeit. Dabei gilt auch: je intensiver man das Problem analysiert, desto bessere Näherungslösungen entstehen.

Für das Problem des Handlungsreisenden (TSP - traveling salesman problem) könnte man auf folgende Heuristiken schließen:

  1. Wähle immer den kürzesten Weg.
    Defizit: Einbahnstraßenproblem: Wenn dann kann ein längerer Weg vorteilhafter als sein Rückweg sein. Somit kann die Auswahl des längeren Weges eine kürzere Reise verursachen, als zuerst den Kürzen zu wählen und dann einen Umweg in Kauf zu nehmen.
  2. Wähle den Knoten als nächstes, dessen Summe aller ankommende und wegführende Wege am kleinsten ist
    Defizit: Besitzt ein Knoten zu einem anderen einen großen Umweg würde er nicht bevorzugt, auch wenn durch ihn die Kürzeste Strecke durch eine andere Kombination zustande kommt.
  3. Wähle den Knoten als nächstes, welcher die beste Differenz von abgehenden und ankommenden Knoten besitzt.
    Defizit: Es werden keine Entfernungen berücksichtigt.
  4. Wähle den Knoten als nächstes, von dem die Summe aller abgehenden Wege bis zum Endknoten am geringsten ist.
    Defizit: Führt über einen Knoten der kürzeste und ein extrem langer Weg, würde ein Knoten mit zwei normal-langen Strecken bevorzugt.


Da Heuristiken aber nur zu einer guten Lösung führen, benötigt man eine Möglichkeit einen falschen Weg bestmöglich zu erkennen und abzubrechen um an einer besseren Stelle weiter zu rechnen. Eine Möglichkeit wäre Backtracking, wo man jeden einzelnen Knoten zurückläuft. Eine weitere Möglichkeit wäre jedoch sich bei jedem Knoten den Bewertungswert zu notieren und bei jedem Schritt zu prüfen, ob ein vorheriger Knoten existiert der einen Besseren Wert besitzt als der Aktuelle. Dafür benötigt man eine Bewertungsfunktion die unabhängig von der Tiefe des Suchbaumes bewertet. Betrachtet man alle bisherigen Heuristiken kann man feststellen, dass sich diese nicht ebenenübergreifend vergleichen lassen. Um dies zu realisieren eignet sich eine Kombination aus einer weiteren Heuristik: Dem Durchschnittswert.

Nutzen wir nun die vierte Heuristik und kombinieren wir diese mit der Durchschnittsheuristik, erhalten wir folgenden Algorithmus: 

Wähle den Knoten als nächstes, von dem die durchschnittliche Länge aller abgehenden Wege bis zum Endknoten am geringsten ist.

Da es sich in diesem Beispel aber nu um Heuristiken handelt, kann nicht garantiert werden, dass unsere Bewertungsfunktion auch eine echte unter bzw obere Schranke ist. Bei einer echten unteren Schrankenfunktion kann der Wert aller niederen zu expandierenden Knoten nie unter dem Wert des Elternknotens liegen. Daher ist unser Algorthmus nur eine Bewertungsfunktion, anhand derer entschieden wird welcher Knoten das höchste Potential hat um zu Lösung zu gehören. Dennoch kann auch diese Bewertugnsfunktion zum Erfolg führen und eine Lösung finden. Ein Beispiel für eine echte Schrankenfunktion wäre die reduzierte Entfernungsmatrix. Diese kann im Buch (|1]) auf Seite 95 nachgelesen werden.

Setzen wir nun diese Bewertungsfunktion um:

Gegeben sei folgende Entfernungsmatrix: (Aus Gründen der Vergleichbarkeit der Lösung wurde die Tabelle aus dem Buch [1] (Seite 94) übernommen.)

von \ nach 1 2 3 4
1 0 20 15 10
2 8 0 9 8
3 6 12 0 13
4 5 20 9 0

Nun benötigen wir noch eine Bewertungsfunkton. Diese leiten wir aus unserer Heuristik ab:

Nun gehen wir wie folgt vor (Pseudocode): 

Wiederhole solange wie nicht alle Knoten besucht worden:
begin
  Ermittle alle Bewertungen für alle abgehenden Wege
  Füge alle Wege der Ergebnisliste hinzu
  Wähle den Knoten mit der kleinsten Bewertung
  Prüfe ob es in der Ergebnisliste einen Wert mit geringerer Bewertung gibt.
  Wenn Ja -> Setze die Suche bei diesem Knoten fort
  Wenn nein -> Entferne den gefundenen Knoten aus der Ergebnisliste
  Setze die Suche bei dem gefundenen Knoten fort.
end

S3erjaeh Animation TSP final.gif

Es ergibt sich eine minimale Rundreise von 1->4->2->3->1 mit einer Weglänge von 35

Umsetzung in Scheme:

Übungen

Aufgaben

Quellen

[1] Wagenknecht, Chr.: Algorithmen und Komplexität, Leipzig: Fachbuchverlag, 2003.

[2] http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php

Von „https://programmingwiki.de/AuK/Verzweigen_und_beschr%C3%A4nken_SS11“
Persönliche Werkzeuge