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. Dabei soll die gesamte Route möglichst kurz sein. Dieses Problem kann als ganzzahliges Programm (IP) formuliert werden. Eine detaillierte Beschreibung kann dem folgenden Dokument entnommen werden.
Beispiel
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