Ein Handlungsreisender (= "salesman") muss eine Rundreise durch N vorgegebene Städte machen. Um Zeit und Benzin zu sparen, sucht er dazu nach demjenigen Weg, der unter allen dankbaren Routen die kürzeste Gesamtlänge aufweist. Mathematisch hießt das:

Gegeben seien N Punkte (Städte) in einer Ebene. Zu je zwei Punkten P_i und P_j gebe es eine positive Zahl d_ij, welche die "Entfernung" (im üblichen oder abstrakten Sinne) zwischen P_i und P_j misst. (Damit ist natürlich d_ij = d_ji .) Gesucht ist nun eine "Reihenfolge" ( = Permutation) σ :{P₁ , ... P_N} → {S₁ , ... S_N}, so dass die Summe aller Entfernungen d(S_n, S_n+1) , n = 1...N zwischen den jeweils aufeinanderfolgenden Städten S_n und S_n+1 minimal wird.

Die "brute-force"-Methode, d.h. Berechnung und Vergleich der Gesamtweglänge für alle denkbaren Wege, ist nur für sehr kleines N sinnvoll, da es bei N Städten insgesamt (N-1) ! = 1 * 2 * ... * (N-1) mögliche Rundwege gibt. Für N = 20 sind z. B. bereits 19 ! = 1,2 * 10¹⁷ Routen auszurechnen, was bei einer Millisekunde pro Weg ca. vier Millionen Jahre dauern würde.

Das "Problem des Handlungsreisenden" ist das klassische Beispiel für ein sog. NP-vollständiges Problem, was bedeutet, dass die Rechenzeit im worst case schneller als polynomial (hier sogar stärker als exponentiell) mit N wächst. Ein allgemeiner Algorithmus zu seiner Lösung ist nicht bekannt.