In dieser Problemklasse gibt es nur Kantenlängen von 1 oder 2. Ein Beispiel dafür haben wir schon bei der Umwandlung eines Hamiltonschen Pfades ins TSP betrachtet.
Hier geht es darum eine Auswahl an Städten zu treffen. Der Handlungsreisende möchte k der n Städte besuchen. Bevor es sich auf eine Route festlegen kann, muß er sich entscheiden, welche der Städte er zuerst besucht.
Zusätzlich zum TSP verlangt das TSSP die Suche nach der kürzesten TSP-Tour durch k Städten mit k<=n. Welches ist also die kürzeste Tour, die man duch k Städte legen kann? Die Städte werden also im Gegensatz zum vorigen Beispiel nicht vorher bestimmt, sondern es sollen die k Städte ausgesucht werden, die die kürzeste Tour möglich machen.
|
|
|
|---|
Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996