Autoren

Hannes Kretschmer

Julian Hilsberg

Bewerten, auswählen und expandieren

Anwendung auf das Rucksackproblem

Das Rundreiseproblem

Problemstellung

Ein Geschäftsmann (auch Handlungsreisender) muss bei einer Rundreise n vorgegebene Städte besuchen. Er startet in einer dieser Städte, besucht nacheinander alle anderen Städte und kehrt am Ende in seine Ausgangsstadt zurück.
Das Optimierungsproblem besteht jetzt darin, die Rundreise so zu planen, dass ihre Gesamtlänge minimal wird. Die Entfernung zwischen den einzelnen Paaren von Städten sind angegeben, z.B. in einer Tabelle.

Naiver Algorithmus

Lösung mit Verzweigen und beschränken