auch TSP, Problem des Handelsreisenden, oder Rundreiseproblem, besteht darin, eine kürzeste Reiseroute eines Handelsreisenden durch n Städte zu bestimmen.

Dabei möchte dieser jede Stadt genau einmal aufsuchen und am Ende wieder zum Ausgangsort zurückkehren. In welcher Reihenfolge soll er die Städte anfahren, damit seine Rundreise eine möglichst geringe Gesamtlänge aufweist?

Dieses wichtige und schwierige Problem der kombinatorischen Optimierung läßt sich beispielsweise graphentheoretisch wie folgt formulieren: In einem vollständigen bewerteten Graphen G = K_n mitpositiver Bewertung ϱ (k) > 0 für alle Kanten k ∈ K(G) wird ein Hamiltonscher Kreis minimaler Gesamtlängegesucht. Einen kürzesten Hamiltonschen Kreis in einem bewerteten Graphen nennen wir optimal. Das Abzählproblem ist einfach, denn es gibt genau n! verschiedene Hamiltonsche Kreise im K_n, oder, wenn wir einen festen Ausgangsort wählen (n − 1)!, womit natürlich mindestens ein optimaler Hamiltonscher Kreis existiert. Dagegen ist das Auffinden eines optimalen Hamiltonschen Kreises ein algorithmisch sehr schwieriges Problem.

Zunächst erkennt man deutlich, daß ein vollständiges Durchprobieren aller Möglichkeiten das exponentielle Wachstum (n − 1)! aufweist. Daß die Anzahl der Hamiltonschen Kreise exponentiell mit n wächst, ist natürlich noch kein Grund dafür, daß das Travelling Salesman Problem nicht trotzdem einen polynomialen Algorithmus zulassen könnte. Schließlich wächst auch die Anzahl der Wege in einem vollständigen bewerteten Graphen K_n exponentiell in n, aber dennoch sind z. B. die Algorithmen von Dijkstra oder Floyd-Warshall sehr effizient, um kürzeste Wege zu bestimmen.

Man kann jedoch nachweisen, daß die Entscheidungsvariante des TSP (Entscheidungsproblem) NP-vollständig ist. Das zugehörige Approximationsproblem ist für Güten (Güte eines Algorithmus) bis zu exponentieller Größe ein NP-schweres Problem.

[1] Grötschel, M.; Lovász, L.; Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988.
[2] Papadimitriou, C.H.; Steiglitz, K.: Combinatorial Optimization. Prentice-Hall, 1982.