hier werden die Fragen, welche Metriken besitzt das TSP (Travelling Salesman Problem) behandelt.
Zur Bedeutung des TSP hier aus Wikipedia kurz eine Erklärung:
"Sehr viele auch praktisch relevante Probleme sind NP-vollständig. Die Lösung des Problems könnte daher von großer Bedeutung sein. Der Beweis von P = NP würde bedeuten, dass für Probleme der bisherigen Klasse NP Algorithmen existieren, die eine Lösung in – wesentlich schnellerer – Polynomialzeit generieren können. Da es jedoch in den vergangenen Jahrzehnten noch nicht gelungen ist, auch nur einen einzigen derartigen Algorithmus zu finden, wird in der Fachwelt angezweifelt, dass diese Algorithmen überhaupt existieren.
"
Einführung
Betrachtet wird das metrische TSP.D.h.
- Die Punkte sind in einem Koordinatensystem metrisch.
- Die Abstände sind positiv definiert: d(i,j) >= 0
- Die Abstände zwischen den Punkten sind symmetrisch: d(i,j) = d(j,i)
- Es herrscht die Dreiecksungleichung: d(i,k) <= d(i,j) + d(j,k)
Metriken
Nach Sandor P. Fekete Dr. Thesis "Geometry and the Travelling Salesman Problem" von 1992, gibt es ein Zusammenhang von Fläche zur optimalen TSP Lösung.Wir haben im metrischen TSP:
1. Punkte im metrischen Koordinaten-System
2. Zentren zwischen konvexen Polygonen und das Zentrum aller Punkte3. Konvexe Teilmengen
4. Flächen der konvexen Polygone und innere Fläche des TSP5. Längen der Wege zwischen Teilmengen der Punkte und die gesamte Länge
Da als Grundlage nur das Koordinatensystem und die Punkte vorhanden sind, ist dies alles, was an Metriken für das TSP möglich ist.
Aus 1. lässt sich ableiten, dass die Punkte als höher/tiefer (y-Achse) und links/rechts (x-Achse) unterscheiden lassen.
Aus 2. lässt sich ableiten, dass alle Abstände zum Zentrum des TSP (d.h. alle der Mittelpunkt aller Punkte) am kürzesten ist.
Aus 3. zeigt sich, dass das Problem des TSP sich in aneinanderreihen von konvexen Gebieten ergibt.
Aus 4. lässt sich ableiten, dass die Fläche des TSP minimal ist.
Und aus 5. lässt sich ableiten, dass auch der Weg über alle Punkte im TSP minimal seien muss.
1. Koordinatensystemmetrik
Da die Punkte des TSP in einem Koordinatensystem liegen, ist auch klar, dass Punkte weiter links, weiter rechts oder unten und oben liegen können, im Verhältnis zu einem anderen Punkt.Dies führt dazu, dass es möglich ist eine globale konvexe Hülle über alle Punkte legen zu können.
Diese Tatsache kann dafür verwendet werden um das Problem in Teilprobleme zu untergliedern. Dabei wird davon ausgegangen, dass das Problem des TSP sich in Teilprobleme untergliedern lässt, wie es Zachariasen 2006 in einer Präsentation als "Algorithm of Aroras" beschrieben hat.
Das TSP lässt sich unterteilen in Teilprobleme, die sich in oben-links, oben-rechts, unten-rechts und unten-links untergliedern.
Werden die Teilprobleme gelöst, so muss im Anschluss nur noch die Vereinigung der Teilprobleme betrachtet werden.
Das nennt sich in der Informatik: Divide and Conquer.
2. Abstand zum Zentrum
Die Bedeutung vom Abstand zum Zentrum liegt in der Tatsache, dass natürlich der Mittelpunkt dem Punkt entspricht, der die kleinsten Abstände zu allen anderen Punkten in der Summe enthält. Dadurch ist es möglich ein Minimierungskriterium im Abstand zum Mittelpunkt zu wählen.Leider dient das Kriterium nicht direkt der Sortierung der Punkte zur Lösung vom TSP.
Es gibt jedoch vielversprechende Ansätze um eine Minimierung der Teilmengen, die ein TSP bildet zu lösen. Dazu mehr weiter unten.
3. Konvexe Teilmengen
Gut ist, dass sich das TSP auflöst in eine globale überlagernde konvexe Hülle und andere konvexe Hüllen am Rand. Dabei schneiden die konvexen Hüllen in die globale konvexe Hülle ein. Das ergab die Beobachtung der möglichen Formen korrekt gelöster TSP's.Die einschneidenden konvexen Hülle, die in die globale Hülle hinein schneiden, werden der kürzeren Form "Navel" genannt.
Navels können wiederum Navles enthalten, so das die konvexe Hülle des Navel N1 einschneidende Navels N1,i enthält.
Diese im Projekt shortcut beobachteten Eigenschaften, führen dazu, dass das gesamte Gebilde des TSP als eine subtrahierende Menge von konvexen Hüllen betrachtet werden kann.
Die Metrik hierauf wäre die Navels so groß wie nötig, jedoch so klein wie möglich zu halten. D.h. die gesamte Summe der Flächen der Navels sollte minimiert werden.
4. Flächen
Wie schon von Sandor P Fekete festgestellt, gibt es einen besonderen Zusammenhang zwischen der Lösung eines TSP und der Fläche, welches die Lösung des TSP aufspannt. Die Fläche ist minimal.In shortcut getätigte Untersuchungen haben gezeigt, dass die Minimierung der Flächen der Navel auch zu einer Minimierung der Fläche des TSP führt.
Dies ist bedeutend, da dadurch eine Approximation anhand der Flächen der Navels zum Gesamtziel, der Lösung des TSP, führt.
Minimierung der Flächen der Navel führt also auch zu einer minimalen Fläche des TSP.
In Kombination mit Metrik 3 der konvexen Hülle, ergibt sich das Theorem:
Da das TSP in Navels aufspaltbar ist, führt auch eine Minimierung der Navel-Fläche zu einer Minimierung der TSP-Fläche. Da die Lösung des TSP nach Metrik 4 der Flächen, eine minimale Fläche hat, führt demnach die Minimierung der Navels zu einer Minimierung des Gesamtergebnisses.
5. Längen
Die allgemein verwendete Metrik um ein TSP zu lösen ist in vielen Verfahren, wie dem Greedy oder dem Minimal-Spanning-Tree, die Minimierung der Abstände zwischen den Punkten. Typisch ist, die Strecke auf Basis der Abstände zischen den Punkten zu minimieren. Ungeschickter Weise, ergibt sich jedoch anhand eines Beispiels (Bsp. 1), dass die Minimierung der Strecke nicht zum korrekten TSP führt. Die Metrik ist unbrauchbar.Schlussfolgerung
Es ist nun das Ziel alle notwendigen und hilfreichen Metriken zu verwenden, um das TSP mit Gradientenverfahren und Minimierung zu lösen.Kombiniert man die Metriken miteinander, so bekommt man folgende Zusammenhänge.
Die Metrik der Längen ist aufgrund des Gegenbeispiels unbrauchbar.
Auf den ersten Blick scheint der Abstand zum Zentrum mit der Metrik der Flächen ähnlich zu sein. Es ist möglich die Flächen der Navels zu minimieren, es ist ebenso möglich, die Abstände zum Mittelpunkt eines Navels zu minimieren.
Es scheint beides gleichwertig.
Jedoch macht sich ein Ausreißer bei einer Metrik der Flächen stärker bemerkbar als bei der Summe der Abstände zum Zentrum vom Navel. Weitergehend wird vom Mittelwert der Abstände zum Zentrum vom Navel gesprochen, statt von der Summe, da hier nur eine Gewichtung von 1/n sich auswirkt.
Zur Erklärung, das Gewicht von 1/n ist zwar wichtig bezüglich dem Mittelwert, da jedoch entweder der Punkt i am Navel N1 oder N2 liegen muss und zur Entscheidung hier nur der Abstand zum Zentrum wichtig ist, so ist der Faktor n für die Minimierung aller n Punkte nicht ausschlaggebend.
Entscheidend ist, dass bei einer Metrik der Fläche, sich ein Navel proportional stärker vergrößern kann, als durch einfache Addition eines großen Wertes zum Zentrum. Daraus ergibt sich, dass die Metrik der Fläche, Ausreißer weniger zulässt als die Metrik zum Zentrum. D.h. sollte die Entscheidung für einen Punkt i zu N1 oder N2 sein, so wird unter der Metrik der Fläche der Navel gewählt, welcher Punkte hat, die näher an i liegen, als es bei der Metrik vom Zentrum der Fall ist.
Generell, ist das TSP nicht die Lösung der minimalen Abstände, wie es das Bsp1 gezeigt hat, sondern das Finden eines kürzesten Round-Trip. D.h. das Ergebnis betrachtet zu jedem Zeitpunkt einen Fort- und einen Rückweg vom/zum Start.
Weiter ist klar, dass die Lösung des TSP, nach den Beobachtungen für die Metrik der konvexen Mengen, aus Subtraktion von konvexen Hüllen besteht. D.h. es gibt eine Fläche, welche durch andere Flächen subtrahiert wird.
Somit ist klar, dass die Metrik zum Zentrum der selben Kategorie, wie die Metrik der Abstände entspricht, und daher unbrauchbar ist.
Unter Berücksichtigung aller Informationen, wie Punkte im Koordinatensystem, Dreiecksungleichung, Abstände und Flächen, ergibt sich folgende Metrik für das TSP geeignet.
- Das TSP wird zerlegt in Teilprobleme, welche eine schnellere Lösung produzieren und helfen die im Mergeschritt zu betrachtenden Reste gering zu halten.
- Und die Metrik zur Minimierung ist die Flächen der Navels zu minimieren.
Eine Kombinatorik, wie Fläche multipliziert zum Abstand zum Zentrum dient nicht, da offensichtlich das Maß des Abstand zum Zentrum ungeeignet ist.
Mit freundlichen Grüßen,
Sebastian Böhmer
