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.