Das Travelling Salesman Problem (,,Problem des Handlungsreisenden``) ist ein prinzipiell einfach zu lösendes Problem - zumindest für kleine Problemgrößen.
Es besteht aus folgender Aufgabenstellung: Ein Handlungsreisender muß eine bestimmte Menge von Orten in einer beliebigen Reihenfolge besuchen. Zum Schluß soll er wieder am Ausgangsort sein; er muß also eine Rundreise machen. Gesucht ist eine Reihenfolge der Orte, die insgesamt einen möglichst kurzen zurückgelegten Weg ergibt.
NP-vollständig, kein schneller exakter Algorithmus bekannt und möglich
Näherungslösung würde in der Praxis in der Regel oft auch reichen.