Das Rundreiseproblem (Begrenzte Enumeration)

Das Rundreiseproblem gehört in den größeren Problemkreis der Reihenfolge-Probleme. Es ist unter ihnen wohl das populärste und unter der Bezeichnung „travelling salesman“ bekannt: Von einem Ausgangsort ist die optimale Reiseroute durch die anderen vorgegebenen Orte gesucht. Dabei soll jeder Ort genau einmal erreicht werden und die Reise soll im Ausgangsort enden. Bekannt sind die Entfernungen zwischen den Orten. Unter dem Optimum wird meist der kürzeste Weg der Rundreise (geringste Kosten, geringster Zeitaufwand) verstanden. Als Optimum kann aber auch das Maximum (z. B. bei einer Inspektions- oder Besichtigungsrundreise) gesucht sein.