Hallo,
zur Lösung des Travelling Salesman-Problems, bei dem eine effiziente Route durch verschiedene Knotenpunkte gesucht wird, gibt es ja den einfachen Nearest Neighbor-Algorithmus.
Man geht vom Startpunkt immer zum nächstgelegenen Punkt und betrachtet jeden besuchten Punkt als abgearbeitet.
So weit so gut, der Algorithmus ist sehr einfach und selbst ich habe es geschafft, ihn programmtechnisch umzusetzen (in Matlab).
Ich benötige aber abgewandelte Formen des Nearest-Neighbor-Algorithmus.
Ich habe ein Rechtecks-Gitter aus Punkten und man soll immer nur einen Schritt laufen, auch wenn evt. der Punkt schon abgearbeitet ist. Also falls der nächstgelegene, noch nicht besuchte Knoten weiter weg ist, soll zu diesem Knoten über die dazwischenliegenden Knoten gegangen werden.
Wie lässt sich dies in das Programm einbinden?
Jegliche Ideen oder auch Pseudocode würde mir weiterhelfen!
Vielleicht gibt es ja auch irgendwo schon ein fertiges Skript (könnte mir gut vorstellen, dass auch andere an so einer Aufgabe mal gearbeitet haben.)
Ich bedanke mich herzlich für eure Hilfe!