Ein Handelsreisender (Traveling Salesman) plant eine Rundreise durch n Städte. Jede Stadt soll dabei genau einmal besucht werden, und am Schluß möchte er (oder sie) wieder am Ausgangspunkt ankommen. Soweit ganz einfach. Jetzt kommt der problematische Teil. In welcher Reihenfolge sollen die Städte besucht werden, um die Kosten zu minimieren? Die Kosten können dabei als Reisekosten, Entfernungen der Städte, Reisezeit usw. verstanden werden.

Wer noch etwas Motivation braucht, kann an dem Beispiel der Kanzlerrundreise auf einer Karte selber probieren, daß eine gute Lösung schwer zu finden ist.

Hier sehen Sie ein Beispiel einer Rundreise durch 6 Städte. Es gibt zwei unterschiedliche Problemstellungen, die für gewöhnlich unterschieden werden: Entscheidungs- und Optimierungsproblem.

Bezogen auf dieses Beispiel bedeutet das:

1. Kann man eine Rundreise mit Kosten kleiner als 30 machen? (Entscheidungsproblem)
2. Welches ist die Rundreise mit den wenigsten Kosten? (Optimierungsproblem)

Welches ist Ihrer Meinung nach die richtige Lösung?

• Ja und 28
• Ja und 29
• Nein und 30
• Nein und 28

Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996