Travelling Salesman
Optimierung
Basiswissen
Der kürzeste Weg durch viele Städte: das Travelling Salesman Problem geht davon aus, dass ein Handlungsreisender durch eine bestimmte Anzahl von Städten reisen will. Dabei will er jede Stadt genau einmal besuchen. Den dafür kürzesten Weg zu finden ist die Aufgabe.
Beispiel
Um beispielweise die kürzeste Variante zum Besuch der 15 größten Städte Deutschlands zu finden, müsste man 43.589.145.600 verschiedene Möglichkeiten durchprobieren. Da ein Durchrechnen aller Möglichkeiten (brute force Methode) meist zu aufwändig wäre, geht man heuristisch vor. Heuristisch heißt, dass man nicht alles durchprobiert, aber trotzdem ein möglichst gutes Ergebnis will. Lösungsstrategien fallen oft in das Gebiet der Graphentheorie ↗