Einführung in die Graphentheorie und das Traveling-Sales-Man-Problem (TSP)

Das Traveling-Salesman-Problem (auch: Rundreiseproblem) TSP gehört zu den kombinatorischen Optimierungsproblemen. Es handelt sich hierbei um ein Rundreiseproblem, bei welchem mehrere Orte unter Minimierung der Reisezeit oder der Kosten nacheinander angesteuert werden sollen. Dabei darf ein Ort nur einmal besucht werden. Die Reihenfolge ist dabei nicht von Bedeutung. Das TSP ist daher ein relativ anschauliches Optimierungsproblem aus der Tourenplanung.

Ein Graph in der Informatik unterscheidet sich grundlegend vom mathematischen Verständnis eines Graphen als Darstellung von Funktionen. Die Definition eines Graphen gemäß der Graphentheorie ist folgende:

Der Graph G ist ein Paar zweier Mengen G=(V,E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ausgeben.

Im Grunde heißt es, dass ein Graph aus Knoten (die wir uns als zu besuchende Orte vorstellen können) und Kanten (eine Straße) besteht. Die Knoten werden mit Kanten verbunden. Es müssen nicht alle Knoten eine Verbindung mittels einer Kante besitzen (isolierter Knoten), aber eine Kante kann nicht „ins Nichts“ führen. Zusätzlich sind positive Distanzen zwischen allen diesen Knoten gegeben. Das Ziel ist die Bestimmung einer Besuchsreihenfolge, bei der die insgesamt zurückgelegte Distanz minimal ist.

Was ist das TSP?

Beim Traveling-Salesman-Problem hat man einen Graphen gegeben, der als Knoten (allgemein) n Städte und zwischen jedem Städtepaar eine Kante besitzt. Nun möchte ein Salesman, also ein Händler, von einer Stadt aus starten und alle Städte genau einmal besuchen bevor er am Ende wieder zur ersten Stadt zurückkehrt. Diese Route sollte so schnell wie möglich sein, wodurch folgende Frage gestellt wird:

Finde eine kürzeste Rundreise durch n Städte. Jede Stadt soll dabei genau einmal besucht werden. Dazu betrachten wir folgenden Graphen:

Die Suche nach dem kürzesten Weg vom Startknoten A kann dazu verleiten, immer den Knoten mit der kleinsten Entfernung zu wählen. Dies könnte zum folgenden Weg führen:
ABDCA – die Kante von C nach A ist mit 15 gewichtet, wodurch der Weg eine Gesamtlänge von 24 hat.

Wenn man bei Knoten B die Kante nach C wählt, welcher ein Gewicht von 6 besitzt, umgeht man die Kante von C nach A und kommt mit der Route ABCDA auf eine Länge von 21 – in diesem Fall von A aus der kürzeste Weg.

Vorgehensweise - Erstelle Adjazenzmatrix (ADM)

Eine Adjazenzmatrix(manchmal auch Nachbarschaftsmatrix) eines Graphen ist eine Matrix, die speichert, welche Knoten des Graphen durch eine Kante verbunden sind. Sie besitzt für jeden Knoten eine Zeile und eine Spalte, woraus sich für n Knoten eine n x n-Matrix ergibt. Konkret auf den oben aufgeführten Graphen angewendet, ergibt sich folgende Matrix:

Die Repräsentation eines Graphen als Matrix erlaubt bspw. den Einsatz von Methoden der linearen Algebra. Die Anwendung und Untersuchung solcher Methoden bildet ein zentrales Thema in der Graphentheorie. Es bildet damit eine Schnittstelle zwischen Graphentheorie und linearer Algebra. Für unseren Kurs an dieser Stelle aber nicht relevant!

Vorgehensweise - Erstelle den Baumgraphen aus der ADM

Der Baumgraph lässt sich leicht aus der ADM ableiten:

Das Ziel des TSP auf Baumgraphen besteht darin, die kürzeste Rundreise durch den Baum zu finden, die alle Städte besucht und am Ausgangspunkt endet. Schwierigkeitsgrad: Das TSP auf Baumgraphen ist in der Regel einfacher zu lösen als das allgemeine TSP, da der Baumgraph spezielle strukturelle Eigenschaften hat. Es gibt Algorithmen, die zur Lösung dieses Problems verwendet werden können (dazu später mehr).

Welche Schwierigkeiten treten beim Lösen des TSP Problems auf?

Die Fragestellung wirkt einfach, jedoch gestaltet sich die Antwort deutlich schwieriger. Wenn man selbst einen Graphen zeichnet und den kürzesten Weg sucht, kann man z.B. auf folgende Strategien stoßen:

Ich starte bei einem Knoten und gehe immer den jeweils über die Kante mit der kleinsten Gewichtung zum nächsten Knoten – Problem: ich muss nicht zwingend alle Knoten erreichen und laufe Gefahr, einen Knoten doppelt zu besuchen.
Ich starte bei einem Knoten und gehe immer zum nächsten, noch nicht besuchten Knoten mit der geringsten Entfernung – Problem: man könnte durch diese Wahl auf Kanten stoßen, die viel größer gewichtet sind und dadurch der Weg dennoch länger ist.

Es gibt mehrere Verfahren und Methoden den kürzesten Weg eines Graphen zu finden, in der Literatur führt mehrere Lösungsmethoden an, welche im Grunde durch zwei Ansätze unterschieden werden:

Exakte Algorithmen – eine optimale Lösung wird für jedes Problembeispiel konstruiert. Dass diese Lösung den kürzesten Weg darstellt ist mathematisch bewiesen.
Heuristiken – es wird so schnell als möglich eine zulässige Lösung gefunden, die nicht zwingend optimal ist, aber dem recht nahekommt.

Eine Methode, wäre ein exakter Algorithmus: Man berechnet alle Wege und ihre Länge – der Weg mit der geringsten Länge ist der kürzeste Weg. Problem bei dieser Methode ist, dass bei wachsender Knotenzahl die Berechnung bzw. Bestimmung aller Wege mit ihren Längen kein Ende nimmt. Wenn es n Städte gibt und jede Stadt genau einmal besucht werden muss, gibt es (n-1)! mögliche Rundreisen mit einem beliebigen Startpunkt. Hierbei ist hinzuzufügen, dass es zwei Arten von Traveling-Salesman-Problemen gibt. Wenn der Hin- und der Rückweg zwischen zwei Städten gleich lang ist, dann spricht man von einem symmetrischen TSP, ansonsten von einem asymmetrischen TSP.

Im Kontext des TSP bezieht sich die Heuristik auf eine Methode oder Regel, die zur Lösung eines Problems verwendet wird. Eine Heuristik im TSP dient dazu, eine schnellere Annäherung an eine mögliche Lösung zu finden, ohne die Gewissheit zu haben, dass diese Lösung optimal ist. Diese Heuristiken sind in der Regel einfache, leicht verständliche Strategien, die in der Praxis nützlich sind, um eine relativ akzeptabele Lösung für ein Problem zu finden, wenn es nicht möglich ist, alle möglichen Routen zu berechnen.

Eine Heuristische Methode ist bspw. die Nächste-Nachbar-Heuristik - aus der Familie der Greedy-Algorithmen.

Angewendet auf unseren Baumgraphen, ergibt sich folgendes Ergebnis:

In diesem Beispiel haben wir eine Anzahl an möglichen Rundreisen in höhe von (n-1)! = (4-1)! = 6. Dies bedeutet, dass es insgesamt 6 mögliche Rundreisen gibt, wenn drei Städte besucht werden müssen. Diese Anzahl ist noch recht überschaubar und leicht zu visualisieren. Wenn jedoch die Anzahl der Städte (n) steigt, wächst die Anzahl der möglichen Rundreisen exponentiell an. Dies bedeutet, dass die Berechnung von n! für größere n zu enormen Zahlen führt. Zum Beispiel ergibt 10! bereits 3.628.800 mögliche Rundreisen, und je größer n wird, desto schneller steigt die Anzahl der möglichen Routen, was das TSP zu einem NP-schweren Problem macht und es schwierig macht, optimale Lösungen zu finden. Ein NP-Problem, kurz für "Nichtdeterministisch Polynomzeit-Problem", ist eine Klasse von Problemen in der Informatik, die eine besondere Eigenschaft bezüglich ihrer Lösbarkeit und Effizienz aufweisen. Darauf gehen wir hier nicht mehr näher ein!

Ein möglicher Algorithmus

Eingabe: ein vollständiger gewichteter Graph
Ausgabe: ein Hamiltonkreis (geschlossener Pfad im Graphen, der jeden Knoten genau einmal enthält)

Wähle einen Startknoten s.
Gehe von s aus zu einem Knoten v mit minimalem Abstand zu s.
Gehe von dem eben erreichten Knoten v zu einem noch nicht besuchten Knoten mit minimalem Abstand zu v.
Falls es noch unbesuchte Knoten gibt, gehe zu 3., anderenfalls kehre zum Startknoten s zurück!

Einfach gesagt, man geht von einem Startknoten immer zum nächsten noch nicht besuchten Knoten, welcher (von der Kantengewichtung aus gesehen) am nächsten ist. Wenn es keinen mehr gibt, kehrt man zum Startknoten zurück.
Diese Methode ist nicht ideal, da dieser nicht immer den kürzesten Weg als Lösung bereitstellt, wie die oben angeführte Beschreibung zeigt. Es gibt noch einige einfachere Methoden, die allesamt entweder zu zeitaufwändig (Ansatz exakter Algorithmus) sind, oder zu ungenaue Lösungen (Ansatz Heuristik) liefern.