Aus ProgrammingWiki

Autoren

Hannes Kretschmer

Julian Hilsberg

Bewerten, auswählen und expandieren

Die Lösungsbäume, welche durch das Tiefe-zuerst- oder Breite-zuerst-Verfahren entstehen können, da diese einen exponentiellen Aufwand betreiben, mitunter sehr groß werden. Um das zu vermeiden, müssen die Teilbäume, die absolut nicht verwendbar sind, bestimmt und entfernt werden. Somit wird die Lösungssuche verkürzt, denn der Baum wird während der Suche aufgebaut. Es werden also gewisse Knoten, deren folgender Teilbaum aussichtslos erscheint, nicht weiter expandiert. Das Entfernen der unbrauchbaren Teilbäume verändert nichts am exponentiellen Zeitaufwand des Suchprozesses. Im worst case ist der Aufwand identisch mit dem der systematischen Suche ohne Beschränkung.

Arbeitsweise

Den erzeugten Knoten (branch) des Suchbaumes werden Wertschranken (bound) zugeordnet. Die Wertschranken besagen, dass kein Folgeknoten eine bessere Wertigkeit erhält. Ob die Bewertung der Knoten mit zunehmender Tiefe des Suchbaums ab- oder zunimmt ist von der Bewertungsfunktion abhängig. Je nach dem, ob ein Maximierungs-, bzw. Minimierungsproblem vorliegt, wird eine obere, bzw untere Schranke festgelegt. Beim Erzeugen des Baumes wird nun jeweils der Knoten mit der besten Schranke expandiert. Bei mehreren Knoten mit derselben (besten) Schranke wird einer der Knoten zufällig ausgewählt. Es ist möglich, dass manche Knoten entstehen, deren Bounds schlechter sind, als die von noch nicht expandierten Branches anderer Teilbäume. Deshalb ist es unbedingt notwendig, alle Expansionskandidtaen aufzuheben!

Dies wird am besten durch einer nach dem Bound sortierten Form realisiert, damit der Aufwand des Vergleichs der Bounds so gering wie möglich gehalten wird. Dafür eignen sich besonders Prioritätswarteschlangen (siehe 3.5.3).

Bound-Bestimmung

Die nicht expandierten Knoten bilden, wie auch bei der systematischen Suche, die Lösungen. Welches Blatt als Lösung verstanden wird, hängt von der Aufgabenstellung ab.

Das Problem, welches bei der Bestimmung der Bounds ergibt, ist folgendes: Wenn sich die Schrankenbestimmung zu stark an der Optimierungsaufgabe orientiert, sind die Werte für die Bounds zwar sehr präzise, allerdings ist damit auch ein sehr hoher Aufwand verbunden. Da die Optimierung aber den Aufwand verringern soll, ist somit kein Vorteil aus dem Prozess zu ziehen. Auf der anderen Seite erhält man statt einer Lösung lediglich Näherungswerte, wenn man eine einfache Schrankenfunktion wählt, da das Risiko besteht, dass die Bounds keine echten Schranken für das Optimum darstellen.

Anwendung auf das Rucksackproblem

Theorie

Um dieses Prinzip auf das Rucksackproblem anzuwenden, werden alle $n$ Gegenstände nach ihrem spezifischen Wert $\frac{w_i}{g_i}$ in absteigender Reihenfolge geordnet. Somit steht der Gegenstand mit dem größten spezifischen Wert an erster Stelle:

, für alle

Es wird der Vektor $\vec{x} = (x_1, x_2, \dots , x_n)$, mit $x_i \in \{0, 1 \}$ gesucht, sodass

,sowie max

bereits im Rucksack:

Restkapazität:

obere schranke für zusätzlichen Wertgewinn:

Beispiel

Gegeben sind $n = 4$ Gegenstände mit den zugehörigen Gewichten $g_i$ und Werten $w_i$. Die Kapazität des Rucksacks beträgt $K = 8$.

Lösungsbaum für Beispielaufgabe

Das Rundreiseproblem

Problemstellung

Ein Geschäftsmann (auch Handlungsreisender) muss bei einer Rundreise $n$ vorgegebene Städte besuchen. Er startet in einer dieser Städte, besucht nacheinander alle anderen Städte und kehrt am Ende in seine Ausgangsstadt zurück.
Das Optimierungsproblem besteht jetzt darin, die Rundreise so zu planen, dass ihre Gesamtlänge minimal wird. Die Entfernung zwischen den einzelnen Paaren von Städten sind angegeben, z.B. in einer Tabelle oder Matrix. Das Problem ist auch bekannt unter dem Namen Travelling Salesman Problem (TSP).

Einteilung

Das Rundreiseproblem gehört in die Kategorie der NP-vollständigen Problemen. Für solche Probleme ist kein effizienter Algorithmus bekannt. Es wird aber angenommen, dass jeder deterministische Algorithmus zur exakten Lösung mindestens exponentiell viele Rechenschritte braucht. Ein mathematischer Beweis für diese Vermutung existiert aber bis heute nicht. Für spezielle Formen des TSP und zur Berechnung von Näherungslösungen sind aber viele effiziente Algorithmen bekannt.

Praxis

Einsätze in der Praxis:

• Verkehrsplanung
• Logistik
• Entwurf integrierter Schaltungen

Naiver Algorithmus

Die wahrscheinlich offensichtlichste Lösung liegt darin sich alle Rundreisen generieren zu lassen und dann die mit dem kürzesten Weg auszuwählen. Für $n$ Städte gibt es insgesamt $n!$ Rundreisen. Da man aber jeden Rundweg in zwei Richtungen gehen kann, sind nur die Hälfte der Rundreisen verschieden. Somit sind nur $\frac{n!}{2}$ Rundreisen wirklich relevant. Ist der Start- und Zielort festgelegt sind es nur $\frac{(n-1)!}{2}$ mögliche Rundreisen. Der Aufwand allein für die Erstellung aller Rundreisen ist exponentiell, wie sich mit der Stirling-Formel zeigen lässt:

Bereits für 10 Städte gibt es 181.440 mögliche Rundreisen, für 13 sind es dann 239.500.800 mögliche Rundreisen. Wenn die Berechnung pro Rundreise 1 Millisekunde bräuchte, benötigt man zur Berechnung aller Rundreisen bei 13 Städten rund 3 Tage.
Nun muss man noch die kürzeste Rundreise finden, was durch Entfernungsmatrizen möglich ist. Möchte man nun das TSP mit vielen Städten (großem $n$) lösen, bedarf es aber einer anderen Lösungsstrategie.

(/ (length (staedte-permut 10)) 2)

ausführen

Lösung mit Verzweigen und Beschränken

Finden einer Schrankenfunktion

Die Bestimmung eines Bounds (einer Schranke) für das vorgestellte Travelling Salesman Problem ist nicht einfach. Eine solche Schranke $s_k$ soll für einen Knoten $k$ versprechen, dass von $k$ aus kein Weg entstehen kann, der kürzer ist als der Bound $s_k$. Hat ein Knoten eines anderen Teilbaumes eine kleinere untere Schranke, ist dieser Knoten zu bevorzugen.
Eine einfach zu berechnende Schrankenfunktion, ergibt sich aus der Summe der zurückgelegten Teilwege vom Start aus und der Entfernung zum nächstgelegenen noch unbesuchten Knoten. Leider ist die Funktion alles andere als präzise, auch wenn der Weg zum nächsten Knoten sehr kurz ist, kann der weitere Weg sehr lang sein und somit die Gesamtlänge weit größer ist als die ideale Lösung.
Man muss den weiteren Weg nach dem Verlassen des Knotens $k$ auch in die Betrachtung mit einbeziehen. Als Beispiel könnte man die Summe aller zu $k$ hinführenden Kanten und von $k$ wegführenden Kanten berechnen, um so eine verlässlichere Schranke zu bekommen. Um Doppelzählung zu vermeiden dividiert man die Summe noch durch zwei. In diesem Fall hofft man aber auch nur auf eine Näherungslösung. Mit begrenztem Wissen und wenig Zeit eine gute Lösung zu erhalten nennt man Heuristik.

Lösung mit reduzierten Entfernungsmatrizen

Wie oben schon angesprochen, eignen sich Matrizen gut zur Angabe der Entfernungen zwischen den einzelnen Städten. Auch zur Berechnung des kürzesten Weges können sie helfen.
Durch Reduktion jedes Zeileneintrags um das Zeilenminimum erhält man eine zeilenreduzierte Matrix. Danach bildet man in der zeilenreduzierten Matrix alle Spaltenminima und zieht diese von den Werten in den Spalten ab. Wichtig ist, dass man die Zeilen- und Spaltenminima jeweils neben bzw. unter die Matrix schreibt. Diese sind später für die Bound-Bildung wichtig.
Beispiel:
originale Entfernungsmatrix $\longrightarrow$ zeilenreduzierte Matrix $\longrightarrow$ vollständig reduzierte Matrix

Wenn man nun von einem Knoten zum nächsten geht, muss man die Entfernungsmatrix entsprechend modifizieren. Wenn man vom Knoten $i$ aus die Kante $(i,j)$ hinzunimmt sind diese Modifizierungen erforderlich:

• Setze $E[z,j] = x$ für alle $z \neq i$, denn $j$ wird nur von $i$ aus besucht.
• Setze $E[i,s] = x$ für alle $s \neq j$, denn ein anderer Weg von $i$ aus ist verboten.
• Setze $E[j,i] = x$, denn der Weg von $j$ nach $i$ ist nicht mehr verfügbar. Er wurde bereits in anderer Richtung durchlaufen.

Schranken können auch kleiner sein, als der später ermittelte kürzeste Rundweg.

Ablauf:

1. Startknoten festlegen und durch Erstellen der reduzierten Matrix die untere Schranke bestimmen
2. in der Hierarchie eine Ebene nach unten gehen und für die Knoten der einzelnen Teilbäume die untere Schranke bestimmen
3. an dem Knoten mit der kleinsten Schranke weiter nach unten gehen und jeweils wieder die minimale Schranke bestimmen
4. gibt es mehrere Teilstücke mit der gleichen minimalen Schranke müssen alle besucht werden
5. ist man in der untersten Ebene angekommen, gibt es nur noch einen Pfad und der letzte Knoten ist dann die Lösung

Prioritätswarteschlangen

Wie schon weiter oben erklärt ist es unbedingt notwendig, alle Blätter des Baumes in einer Warteschlange aufzubewahren. Auch wenn sie zum Zeitpunkt ihrer Analyse nicht die kleinste Schranke hatten.
Für solche Probleme eignet sich eine Prioritätswarteschlange (engl. priority queue, auch Vorrangwarteschlange) besonders gut. Diese ist eine Datenstruktur zur Speicherung einer Menge von Elementen, für die eine Prioritätsordnung definiert ist. Jeder Wert hat einen Schlüssel mit seiner Priorität. Folgende Operationen sind ausführbar:

• initialize: Initialisieren einer (leeren) Struktur
• insert: Einfügen eines Elements (an der richtigen Stelle)
• access min: Minimum lesen
• delete min: Minimum entfernen

Die Implementation erfolgt am besten mittels Heap (Halde). Ein Heap mit $n$ Elementen erlaubt das Einfügen eines neuen Elementes und das Entfernen des Minimums in $\mathcal{O}(\log n)$ Schritten. Das Minimum steht immer am Anfang des Heaps, deshalb kann access min in konstanter Zeit ausgeführt werden.
Für das TSP und andere Minimierungsprobleme nutzt man die Min-Prioritätswarteschlange, für Maximierungsprobleme dreht man einfach die Prioritätsordnung um, so dass das Maximum immer an erster Stelle steht und erhält so eine Max-Prioritätswarteschlange. Priority Queues für ganzzahlige Daten können einfach und effizient implementiert werden. Schwierig ist nur zwei Heaps schnell zu einem zusammenzusetzen. Die beste Möglichkeit ist die vorhandenen Heaps aufzulösen und einen neuen Heap mit allen Elementen aus beiden Heaps zu erstellen. Wenn $n$ die Anzahl der Elemente des einen Heaps und $k$ die des anderen ist, ist diese Operation in $\mathcal{O}(n+k)$ Schritten durchführbar.

Übungsaufgaben

Bitte bearbeiten Sie diese Aufgaben sorgfältig. Bei Fragen zur Aufgabenstellung oder für Lösungshinweise stehen wir Ihnen gerne zur Verfügung.

Übung.pdf (0.6 MB)

Literatur

Christian Wagenknecht

Algorithmen und Komplexität - Fachbuchverlag Leipzig, 2003. - ISBN 3-446-22314-2

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein

Algorithmen - Eine Einführung, Oldenbourg Verlag, 2. Auflage, 2007. - ISBN 978-3-486-58262-8

Thomas Ottmann, Peter Widmayer

Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 5. Auflage, 2012. - ISBN 978-3-8274-2803-5

Markus von Rimscha

Algorithmen kompakt und verständlich, Vieweg + Teubner Verlag, 2008. - ISBN 978-3-8348-0569-0