taramath
Problem des Handlungsreisenden
formuliert als ganzzahliges Programm
Beschreibung
Gegeben seien feste Orte in der Ebene. Das Problem des Handlungsreisenden oder das Traveling Salesman Problem besteht darin, alle Orte genau einmal zu besuchen und anschließend wieder zum Ausgangspunkt zurückzukehren, wobei die gesamte Reisetour möglichst kurz sein soll. Dieses Problem kann als ganzzahliges Programm formuliert werden. Eine detaillierte Beschreibung kann dem folgenden Dokument entnommen werden.
tsp.pdf
Beispiel 1
Im folgenden Beispiel lösen wir das Problem des Handlungsreisenden mit Orten, welche zufällig in der Ebene verteilt werden. Anschließend wird das Ergebnis graphisch dargestellt.
Tipp: Verändere die Anzahl der Orte. Dabei ist darauf zu achten, dass die Laufzeit zur Lösung des Problems exponentiell in wächst. Bereits für Probleme mit etwa kann die Rechenzeit unangenehm groß sein. Vorschau aktualisieren