Autoren

Hannes Kretschmer

Julian Hilsberg

Bewerten, auswählen und expandieren

Anwendung auf das Rucksackproblem

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:

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 Stirlingschen Formel zeigen lässt:

n! \approx \sqrt{2 \cdot \pi \cdotn} \cdot \left( \frac{n}{e} \right)^n = \mathcal{O}(n^n)

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.

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

&  &  &  & | & 

&  &  &  & | & 6

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:

Schranken können auch kürzer 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. Folgende Operationen sind ausführbar:

• initialize: Initialisieren der 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 accesss min in konstanter Zeit ausgeführt werden.