Was kann Traveling salesman, disappointment

Sehr geehrte Damen und Herren,

Traveling Salesman ist ein Problem in der Informatik, welches für den Menschen leicht lösbar, jedoch für die Maschine schwer ist. Natürlich nur bei beschränkter Größe. Bei großer Größe, ist es auch für den Menschen schwer.

Das Problem ist :
Finde den kürzesten Rundweg für gegebene Punkte, welche alle miteinander auf direktem Weg erreichbar sind.

Was kann man damit machen?

Man kann natürlich kürzeste round-trips auf 2D Ebenen bestimmen.
Es geht jedoch auch darum, alles zu sortieren, was zwei orthogonale Eigenschaften hat.
Nicht dazu gehörend ist zum Beispiel, die Dichte. Sie hat das Volumen und das Gewicht als Eigenschaften. Jedoch ist sie schon durch den Bruch dieser Komponenten definiert und daher nicht wirklich zweidimensional.
Kartesische Koordinaten lassen sich hingegen nicht einfach durch einen Bruch eindeutig zuweisen.
Das TSP passt also auf zwei Eigenschaften, welche nicht per Definition durch einen Bruch definiert sind.

Typische Beispiele

Leider waren die drei typischsten Beispiele weniger passend für eine Anwendung des TSPs. Hier die Begründungen.

Soziale Netzwerke :
Sind eher chaotisch als strukturiert und daher aussagenlos trotz Anwendung eines TSPs.

Hyperlink Rankings :
Daten sind statisch, da keine Erhebungen der Klicks auf einen Link ausgeführt werden.
Ein round-trip auf diesem Netzwerk ist weniger klar zu interpretieren.
Daher scheint es weniger sinnvoll als TSP Beispiel.
Im Prinzip reicht es aus, die Anzahl der Verlinkungen zu wählen, welche weit über das Internet verteilt seien sollten und den Ort, so wie die Zeit, dazu zu nehmen, um ein aussagekräftiges Ranking zu erhalten.

Last but not least, shortest path:
Unter kürzestem Weg wird oft schnellster Weg verstanden.
Egal welches Kriterium betrachtet wird, die Vorgehensweise ist oft eine Rasterpyramide. D.h. es werden erstmal die groben Punkte verbunden und dann im Detail die Strecken gewählt.
Alternativ ist eine rekursive Suche möglich.
Shortest path, ist kein round-trip und nicht jeder Punkt ist auf direktem Weg mit jedem anderen zu erreichen. Daher ist es nicht so komplex wie das TSP. Somit schnell genug mit den oben genannten Methoden lösbar.

Es sieht so aus, als ob ich, bis auf ein Beispiel, kein passendes weiteres Beispiel finde.
Hilfe ist willkommen, in den Kommentaren.
Das eine Beispiel, das ich habe, ist das Dreikörperproblem
Dazu mehr in einem anderen Post.

Mit freundlichen Grüßen Sebastian

What can we do with a solved TSP

Dear ladies and gentlemen,

Now it is time here in Munich to think about the possibilities of a solved traveling salesman problem (TSP).

TSP is one of the most complex problems according to the complexity theory.
Although it is not complex according to the chaos theory.
So, we can say it is just very difficult to calculate.
Let's imagine, we have two difficulties, one is the power needed to calculate and the other is the capacity necessary to calculate.
TSP belongs to the question of power needed to calculate.

In the end, there are people who say TSP is not possible to solve in appropriate time. Although it is not proven, that it is not possible.
In the end, there is a theory, that say, if it is possible, every problem is possible to calculate in appropriate time.

This mean every thing is possible to calculate.
This is interesting, because you have problems that are hard to calculate till now.
The mystery is solved. Imagine what you want to prognosticate? It is possible to calculate now. Although you need very much capacity.

For example the weather forecast is very imprecise right now.
You know this is part of the chaos theory.
This is the reason, why you need very much capacity still.
With the help of the TSP solver, it is possible to improve the forecast, so that it is less necessary to correct the forecast according to newer measurements. With the right capacity, it is possible to get more proper forecasts for longer time.

It will be possible to get deeper understanding of the world. It will be possible to calculate the reality. It will be possible to forecast every thing.

What are you thinking TSP could be good for?
Write down in the comments.
Any help would be appreciated.

Yours sincerely Sebastian

Konzept für einen Beweis dass nur beschränkte Räume überprüft werden müssen

Herzlich willkommen,

Prüfung nur über Teilräume nötig

hier wird eine Skizze des Beweises beschrieben, der zeigt, dass nur Teilräume überprüft werden müssen, um das TSP für den gesamten Raum für eine beschränkte Anzahl von Punkten zu beweisen.

Es existiert ein grundlegendes Problem. Leider ist es noch nicht gelungen, einen Beweis für die Gültigkeit eines Algorithmus auf allen n Punkten, mit n beliebig, zu beschreiben. Dies liegt daran, dass mit n+1 die Anzahl der möglichen TSP Konstellationen um, Positionen im Raum minus n multipliziert. D.h. die bisherigen Möglichkeiten werden um die neuen möglichen Positionen multipliziert.
Ein einfacher induktiver Beweis für, n nach n+1 Punkte, liegt nicht nahe. Da, wenn die Kombinationsmöglichkeiten für die Positionen für n Punkte überprüft wurden, sich die Möglichkeiten für TSP Konstellationen um mindestens multiplikativ n+1 erhöhen. Überprüft heißt hier, dass der gefundene Algorithmus für n Punkte und alle Positionsmöglichkeiten (m x m) korrekt war. Das ergibt sich durch ein Gegenbeweis.
Angenommen m = 6 und n=3, dann gibt es einen Algorithmus A, welcher für 3 auf allen Positionen des 6x6 Koordinatensystems funktioniert. Angenommen, er funktioniert auch für n+1=4, dann ist die Annahme, nach Induktion, dass er auch für n+2 funktionieren sollte. Dem ist jedoch nicht so. Der Algorithmus A funktioniert nicht für n+2. Der Algorithmus A, sind hier die "Basisschritte" im Tamar-Algorithmus. Siehe Projekt shortcut.
Das Beispiel macht den Gegenbeweis, zu der Annahme des Induktionsschlusses.
Es ist nun klar, dass der Beweis für n+1 Punkte nur mathematisch geführt werden kann.

Daher sind hier die Anzahl der Punkte auf n beschränkt und der Raum, ohne Beschränkung der Allgemeinheit (o.B.d.A.), (2n,2n) = (m,m).

Es gilt zu beweisen:

Sind für n Punkte alle TSP Lösungen L korrekt im Raum (m,m), dann sind sie auch korrekt für einen anderen Raum in N oder Q beliebiger Größe.

Beweisskizze

Der Beweis beschränkt sich auf die Punkte der natürlichen Zahlen N.
Später wird ein Trick angewendet, dass aus Zahlen (N x N) nach Q transformiert werden kann.
Dennoch bleiben die irrationalen Zahlen übrig. Letztlich ist also ein TSP mit einem Punkt auf (2,sqrt(2)) nicht einfach beliebig beweisbar. Letztlich ist es schwer zu zeigen, dass die Lösungen L auch für einen Raum in R möglich sind.

Dennoch hier die Beweisskizze.
Es gelte der Raum M mit Anzahl der Positionen (m,m), wobei o.B.d.A m=2n entspricht.

Theorem 1

Ist L, die Liste von Punkten mit einer Lösung in M, so gilt:
die Lösung L' in M ist existiert, wobei für L' gilt:
  $$  L' = { l' : \exist l \in L:  l'_x = l_x+1 ^ l' \in M}  $$

L' ist um einen Punkt entlang der x-Achse verschoben. Analoges gilt dies für L'y, einer Verschiebung entlang der y-Achse.

Dies wurde durch Berechnen aller Lösungen L in M und dem Vergleich der Lösungen L' in M' bewiesen. Wobei, M' der Raum (m+1,m) war.
Die Lösungen L wurden auch in M' durchgeführt und waren identisch zu L'.
D.h. die Lösungen L waren für A gleich in M'. Und die Lösungen L' waren gleich in M'. Gleich oder identisch bedeutet, die Reihenfolge der Punkte in Lösungen L sind identisch mit der Reihenfolge der Punkte in L'.
D.h. die verschobenen Lösungen L' sind im gleichen Raum identisch.
Daraus folgt, die Lösungen L sind verschiebbar, was zu beweisen war.

Theorem 2

ist L in M lösbar, so ist auch das skalierte L' in M lösbar, wobei:
  $$  L' = { l' : \exist l \in L: l'_x = l_x*2 ^ l' \in M } $$
Analog gilt dies für L'y, der Skalierung entlang der y-Achse.

L' sind die Lösungen um eine verdoppelte Auflösung von L.

Bewiesen wird dies durch alle Tests in M. Die Berechnungen ergaben, dass alle L' denen von L entsprachen. D.h. die Reihenfolge der L' entsprach der Reihenfolge der L.
Daraus folgt, die Lösung L ist skalierbar, was zu beweisen war.

Theorem 3

Ein einzelner Punkt l' im skalierten und verschobenen Raum M', kann verschoben werden l*', und die Lösungen L*' sind zur ursprünglichen Lösung L identisch.

Wird ein Punkt verschoben, so entstehen neue Lösungen L*'. Diese Lösungen sind dann wieder identisch mit L*. Hierbei ist L*' die Lösung mit einzelner Verschiebung in der verschobenen und skalierten Menge L'. Und L*, die Lösung mit einzelner Verschiebung in der original Menge L.

Dabei bedienen wir uns eines Tricks. Es wird davon ausgegangen, dass die Lösungen L' im Raum M' := (2m,2m) liegen.
Es wird ein Punkt $l' \in L'$ zu l*' um zwei Zähler in x und/oder y-Achse verschoben.
Es ist, auf der Basis von Berechnungen, gezeigt, dass dies einer Verschiebung des Punktes um einen Zähler in Raum M := (m,m) entspricht.
D.h. die Reihenfolge der Punkte in L* \in M entspricht der Reihenfolge der Punkte in L*' \in M'.
Dies wird für alle Verschiebungen L*, mit l* berechnet. Dabei gibt es 8 Verschiebungen für l*. Das sind die Positionen in 3x3 Gatter ohne den Mittelpunkt. Dies entspricht äquivalent 8 Verschiebungen um zwei Zähler im Raum M' für l*'.

Die Berechnungen zeigen: L*' entsprach L* für alle Verschiebungen.
D.h., da klar ist, dass eine Skalierung nach Theorem 2 im Raum äquivalent ist, und  die Verschiebung eines einzelnen Punktes zwischen skalierten Räumen gültig ist, gilt:
Die Verschiebung eines einzelnen Punktes ist im Raum gültig. Was zu beweisen war.
Gültig, in dem Sinne, dass die Reihenfolge der Lösungen gleich sind.
L* wird als verformte Lösung bezeichnet. D.h. Verformungen von L sind möglich.

Theorem 4

Der Trick um zu zeigen, dass es nicht nur für Punkte im Raum NxN gilt, liegt in dem allgemein trivialen Theorem, dass es eine bijektive Abbildung von NxN nach Q gibt.

Dazu wird das Koordinatensystem M von NxN auf M^ := (NxN)x(NxN) erweiteret.
Die Berechnungen zeigen, dass obige Theoreme 1,2,3 auch für NxNxNxN gilt.
D.h. die Reihenfolge der Punkte entspricht weiterhin der Reihenfolge der Punkte von verschobenen, skalierten oder verformten Lösungen im Raum M^, bezüglich der Theoreme.
Daher ist klar: die Theoreme 1,2,3 sind für M^ gültig. D.h. die bijektive Abbildung kann auf M^ angewandt werden, und alle Lösungen in M^ sind auch in QxQ möglich. Was zu beweisen war.



Sehen Sie das auch so?

Offene Punkte

Es mutet an, per Induktion von n auf n+1 zu schließen. Jetzt, wo klar ist, dass ein Beweis im beschränkten Raum auch für unbeschränkte Räume von N und Q gilt.
Dennoch, muss m dann so gewählt werden, dass alle punkte n+1 rein passen.
Zudem gibt es durch n+1 Punkte, mindestens n+1 multiplikativ viele weitere Möglichkeiten, was sich schon aus der Reihenfolge der Punkte ergibt. Siehe dazu die Approximation der Möglichkeiten im TSP durch n!.
Wie ist also eine Induktion von n auf n+1 möglich, unter der Annahme eines beschränkten Raumes?



Mit freundlichen Grüßen,
Sebastian Böhmer

Metriken des TSP

Sehr geehrte Damen und Herren,

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

Neue Methoden und Metrik

Hallo, 

Es ist soweit. Die experimentellen Untersuchungen zur Lösung des TSP, sind an eine Konstellation gestoßen, welche weniger durch die bisherigen Verfahren lösbar ist.
Das Beispiel ist Test63. Dabei ging es um direkt in einer Linie hintereinander liegenden Hauptkanten der konvexen Hülle. Die erste war länger als die zweite. So kam es dazu, dass sich die Punkte in näheren Umgebung an der ersten alignten, im Gegensatz zur zweiten Hauptkante, welche besser wäre. 

Lösung

Lösung ist den seboehDist durch den Abstand zum Zentrum der Punkte eines 'Navels', zu verschlechtern. D.h. weiter weg liegende Punkte zum Zentrum werden schlechter bewertet, bezüglich dem seboehDist.
SeboehDist ist eine Minimierung. Daher reicht es den Abstand zwischen neuen Punkt und neuem Zentrum zu multiplizieren.

Ungeschickterweise, wird durch die Multiplikation das Beispiel 58, welches mit Kandidaten arbeitet, verschlechtert.
Deshalb hat sich ergeben, dass ca die vierte Wurzel vom Abstand besser ist.

Außerdem ist es wichtig, die Berechnung nur im correctDist zu machen. Nicht für alle SeboehDist. Jedoch wird der Abstand m, auch mit findBest verwendet. Das ergaben die Tests. 

Resümee

Bei der Verwendung unterschiedlicher Verfahren, und dem ständigen entwickeln anhand von Beispielen, stellt sich die Frage, ob es sinnvoll ist so weiter zu machen, oder grundsätzlich die Möglichkeit neu überlegt werden sollten. 

Dies wird im Beitrag "Metriken des TSP" beurteilt.

Ist TSP lösbar mit Candidates und Backtracking?

Sehr geehrte Damen und Herren,

nachdem einige Algorithmen programmiert wurden um das TSP im Gradientenverfahren zu lösen, sind wir am Tag der Deutschen Einheit auf folgende Konstellation von Punkten gestoßen.

Links ist das aktuelle Verfahren Tamar zu sehen. Rechts die korrekte Variante durch naives Verfahren.

Das Linke Bild unterscheidet sich aufgrund des Punktes 230x140, welcher an 30x40 align-en sollte. Dazu kommt, dass das "wipeAllMultiple()" 220x250 und 220x290 an 140x350 align-en sollte.
Leider konnte das wipeAllMultiple() nicht die 220x* Punkte align-en, da 230x140 gleichzeitig an einen anderen Root (30x40) aligned werden müsste.

Nun führt das Beispiel zu einer Korrektur des wipeAllMultiple() zu einem Ansatz mit Kandidaten-Management und Backtracking.

Im folgenden wird 230x140 als Punkt A bezeichnet. Der Punkt 220x140 als B und Punkt 220x290 als C.

Es ist nun so, dass A nur an 30 aligned, weil B und C an 140 aligned wurden. Jedoch ist in wipeAllMultiple() nicht vorgesehen, dass ein Punkt A gleichzeitig an andere Roots align-en kann, außer an dem "gegenüberliegenden/alternativen Root" (kurz: gR). Um ein Alignment an anderen Roots zu ermöglichen, ist es notwendig die Punkte des "ursprünglichen Roots" (kurz: uR) mit alternativen Roots (aR) zu vergleichen.

Es bietet sich aufgrund der Zweidimmensionalität an, die vier nächstliegenden Kanten (K(p), mit oBdA p=A) zu betrachten.

Es wird wie folgt vorgegangen:

• die Punkte P von uR (hier 370x30) werden bezüglich ihres Abstandes (seboehDist) zu gR sortiert. Dabei wird nur eine grobe Sortierung (gS) gemacht, welche nur das Alignement von p (aus P) berücksichtigt, welches aufgrund der aktuellen Situation an gR existiert. D.h. es werden keine vorherigen p_i an gR aligned, um das nächste Alignement des nächsten p_i+1 zu bestimmen.
• Entlang der gS wird nun p_s aus gS gewählt, welches am nächsten zu gR liegt, und das Alignement an gR (gA), sowie das Alignment an den alternativen vier Kanten K(p) bestimmt. Das Alignement an K(p) wird hier aA bezeichnet. Mit aA_i(p) als die Kante mit i'ten Abstand zu p.
• Das beste Alignement bA zwischen aA und gA wird für p gewählt.
• Herrscht nun eine lokale Verbesserung, so wird p als "auserwählt" an aA aligned. Herrscht keine lokale Verbesserung, so wird p als "Kandidat" an aA aligned. Kandidaten werden in weiteren Alignements nicht berücksichtigt. Sie sind für später.
• Es wird mit dem nächsten p aus gS fortgefahren, bis keine Punkte mehr in gS liegen.
• Nun ist es so, dass wir Auserwählte haben und Kandidaten haben. Es wird versucht per Backtracking die Kandidaten wieder an uR zu algin-en.
• Dabei werden die Kandidaten C grob an die ursprüngliche Hull-Edge-Kante uR (ursprünglicher Root ohne Punkte) sortiert cS.
• Für jeden c aus cS wird nun ein bester Partner bP für das Alignment an uR gesucht. Der Partner ist wiederum ein Punkt aus cS, welcher noch nicht verarbeitet wurde.
• Es wird die Korrelation zwischen c und bP bezüglich uR berechnet. D.h. es gibt drei Möglichkeiten c geht alleine an uR, c geht nicht an uR oder c geht mit bP an uR. Die beste Möglichkeit wird gewählt. Der Kandidat c und evtl auch bP werden nun als "auserwählt" markiert und an ihren besten Root aligned.
• Diese Schritte werden für c aus cS wiederholt.

Damit wird erreicht, dass die Punkte abwandern können zu einem ausgewählten Konkurrenten gR, und alternative Verbindungen eingehen können zu aA.

So kann A an 30 align-en und gleichzeitig B und C an 140.

Der ausgewählte Konkurrent wird durch die Reihe mit allen vorhanden Kanten variiert.

Es besteht die Hoffnung, dass dadurch eine globales Ziel (die Minimierung) erreicht wird.

Sehen Sie das auch so?


Mit freundlichen Grüßen, Sebastian Böhmer, München, den 3.10.2016

Welcher Raum ist für die Lösung des Travelling Salesman Problem zielführend?

Sehr geehrte Damen und Herren,

Sie haben sich sicherlich mit dem Travelling Salesman Problem (TSP) beschäftigt. Sie haben vielleicht schon einige Implementationen realisiert. Sie sind voraussichtlich darauf gestoßen, dass heuristische Verfahren in lokale Minima geraten. Daher soll hier die Frage nach dem passenden Raum für die Betrachtung des TSP diskutiert werden.

Generelle Vorstellung

Der Raum des TSP wird normalerweise als möglich Lösungen, d.h. round-trips der Input-Sequenz, und deren zugehöriger Länge betrachtet.
Das ist hier auch so. Jedoch mit einer anderen Norm.
Um nun zur Erklärung zu kommen, muss vorerst eine Abgrenzung und Auflösung typischer Annahmen getroffen werden.

Sehr oft wird vermutet, dass sich gute Lösungen des TSP in der Nähe der optimalen Lösung des TSP befinden. Das wird durch viele Beispiele widerlegt.
Die Kosten, die durch eine weniger optimale Lösung, d.h. die Änderung durch vielleicht eines Punktes, entstehen, sind verhältnismäßig hoch. Wird ein Punkt verändert, so kommt es schnell zu höheren Kosten. Das liegt daran, da sich dann die Reihenfolge der Punkte ändert und dies mindestens zwei andere Kanten zur Folge hat. Diese anderen Kanten haben andere Längen, welche in der Summe dann wieder zu einer höheren Länge führen. D.h. eine Änderung eines Punktes kann typischerweise eine sehr viel höhere Gesamtlänge zur Folge haben.
Es ist also so, dass der Raum der Lösungen des TSP nicht dicht, oder gar gleich-verteilt, um die beste Lösung liegt, sondern sehr "sparse" verteilt ist. Der Begriff "sparse" kommt aus der Mathematik und ist in der ersten Interpretation das Gegenteil von dicht.

Es ist nun so, dass die Punkte, wenn wir sie uns als eindimensionale Reihenfolge vorstellen, einen großen Abstand zischen einander haben.
Der Raum der Lösungen ist beim TSP multi-dimensional. D.h. jeder Punkt bildet durch seine Position in der Reihenfolge des round-trip's, eine neue Dimension.

Damit es verständlicher wird, kann der Lösungsraum des TSP als zweidimensionale Punktwolke vorgestellt werden. Diese ist sparse verteilt.
Das Ergebnis der Lösungen, d.h. die Länge des round-trip's, kann als eine weitere Achse in einem dreidimensionalen Raum vorgestellt werden. Dies ist dann die Z-Achse.
Auf der Z-Achse wird die Gesamtlänge des round-rips, also einer Lösung, aufgetragen.

Die generelle Vorstellung ist nun, dass bei geeigneter Norm für das TSP ein Raum entsteht, der viele lokale Minima enthält.
Als "geeignete Norm", wird oft die euklidische Länge betrachtet. Unter dieser Norm tendiert der Raum jedoch stärker zu lokalen Minima.
Daher stellt sich die Frage, ob der Raum mit euklidischer Länge geeignet ist um das TSP zu Lösen. Lösen, in dem Sinne, das auf effizienteste Art und Weise die optimale Lösung gefunden wird.

Neue Vorstellung

Das Problem des nicht geeigneten Raumes, kann durch eine andere Norm gelöst werden. Typischerweise wird die euklidische Länge als "geeignete Norm" betrachtet. Jedoch bietet sich die Norm des "Umweges" eher an.
In diesem hier präsentierten Lösungsansatz wird diese Norm des Umweges für die Lösung des TSP als sehr geeignet angesehen.
Es ergibt sich die Vermutung, dass unter der Norm des Umweges, welche gleich näher erläutert wird, der Raum keine lokalen Minima mehr enthält und man direkt mit Gradientenverfahren das kleinste Minima, also die optimale Lösung, bestimmen kann.

Die Norm des Umweges, in diesem Lösungsvorschlag auch SeboehDist genannt, berechnet die euklidische Länge des Weges, welcher zusätzlich notwendig ist, um von Punkt A nach Punkt B zu gehen, und dabei Punkt C auch zu besuchen.

Diese Norm bietet sich für das TSP besonders an, da vermutet wird, dass eine lokale Minimierung anhand dieser Norm, zu einem globalen optimalen kürzesten Weg nach der üblichen euklidischen Norm führt.

Resümee

In getesteten Beispielen, kann direkt gezeigt werden, dass die Verwendung der euklidischen Länge als Norm für die Lösung des kürzesten round-trip, nicht geeignet ist.
Damit ist klar, dass eine optimale Lösung nicht mit der reinen Betrachtung der euklidischen Länge erreicht werden kann.
Zusätzlich hat sich gezeigt, dass die Norm SeboehDist in allen bisherig getesteten Fällen zum Erfolg führte.

Mit freundlichen Grüßen, Sebastian Böhmer
PS: Sehen Sie das auch so?