Immer wieder muß sich jemand mit einer zurückzulegenden Route beschäftigen… und mir ist der Lösungsansatz gänzlich unbekannt.
Wie kann eine Wegstrecke berechnet werden, bei der alle Ziele mit der kürzesten zurückgelegten Gesamttentfernung erreicht werden?
Bei drei wahllosen Punkten auf einem Stück Papier gelingt einem das noch durch schlichte Betrachung.
Aber wie ein Postbote (wenn er es dürfte) seinen Zustellbezirk optimieren könnte… oder wie alle deutschen Städte mit der geringstmöglichen Gesamtentfernung nacheinander angefahren werden können… das Problem wird mit zunehmender Anzahl der Zielpunkte immer komplexer!
Ändert sich der Lösungsansatz, wenn wir die Aufgabenstellung von den Zielen auf einer Fläche auf die Ziele im Raum ausdehnen?
das ist unter Traveling Salesman Problem (TSP) zu finden. Das Problem, ob die minimale Streckenlaenge unter einen bestimmten Wert liegt, ist NP-vollstaendig, d.h. einfach zu pruefen wenn man die minimale Strecke hat, aber diese ist schwer zu finden. Es gibt nur Naehreungsverfahren, die alle irgendwo einen Zufallsgenerator bemuehen.
Eine Variante ist, sich einen Ausgangsweg zu bauen (z.B. ueber eine zufaellige Reihenfolge) und dann folgende Schleife laufen zu lassen, solange man will:
Waehle zwei verbundene Punktepaare (meist per Zufall),
pruefe, ob eine Ueberkreuzverbindung die Weglaenge verkuerzt,
aendere gegebenenfalls den Weg.
Andere Varianten verwenden genetische Algorithmen oder aehnlichen Hokupokus, manchmal funktioniert’s.