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
