Original Universität München: Siehe hier
Das Problem des Handelsreisenden
Der Handelsreisende (travelling salesman) steht für ein Problem der Optimierung: Es sollen nacheinander bestimmte Orte (zur Abwicklung von Geschäften) vom Handelsreisenden besucht werden, wobei die Reihenfolge so gewählt werden soll, dass der Gesamtreiseweg möglichst kurz wird. In vielfältigen Erweiterungen sind zusätzlich noch die Beschwerlichkeit bestimmter Verbindungsstraßen oder gar nur in eine Richtung passierbare Wege zu berücksichtigen (aus dem Graphen würde dann ein gewichteter bzw. gerichteter Graph).
Bereits der oben beschriebene, simpelste Fall ist ein NP-vollständiges1.7 Problem, weshalb Heuristiken1.8 hier Anwendung finden. Viele elementare Strategien (Nearest Neighbour, Greedy algorithm, Nearest Insertion, Strip) wurden immer weiter verbessert.
NP-vollständiges1.7
Es existiert also kein Algorithmus, der eine Lösung innerhalb einer Zeitspanne liefert, die lediglich polynomial mit der Problemgröße wächst. Vielmehr sind große Probleme in der Praxis nicht exakt lösbar.
Heuristiken1.8
Eine Heuristik liefert nicht notwendigerweise ein optimales Ergebnis, gelangt dafür aber oftmals sehr schnell zum Ziel.