Das Ziel aller Anstrengungen ist es, einen Algorithmus zu finden, der eine optimale Lösung innerhalb einer polynomial von n abhängenden Zeit findet. Das beste, was bisher erreicht wurde, sind Lösungen innerhalb einer Zeit, die exponentiell von n abhängt. Solchen Algorithmen kommen mit ihrer Berechnung aber nicht sehr weit, unabhängig von der Rechenleistung des Computers. Wenn die Zeit z.B. 2^n von der Problemgröße abhängt, wird tausendfache Rechenleistung lediglich ein Hinzufügen von 10 Städten zulassen.

Es gibt Lösungsansätze für das TSP, die auch für große n relativ schnell eine gute Lösung anbieten, allerdings kann man nicht sagen, wie weit sie von einer optimalen Lösung entfernt sind.

• Heuristic
• Memetic Algorithms
• Ant Colony Optimization
• Simulated Annealing (mit Java-Applet)
• Genetic Algorithms
• Neuronale Netze (z.B. Kohonen-Netze)
• Branch-and-Bound (mit Java-Applet)
• Nearest Neighbor (wird nachher noch ausführlicher besprochen)

• TSP mit Abständen 1 und 2
• Prize-Collecting TSP
• Euclidean TS Selection Problem
• Circulant TSP
• Time-dependent TSP

Eine Vielzahl weiterer Verweise auf TSP-bezogene Seiten findet man in der TSPBibliothek.

Noch eine kleine Übungsaufgabe:
Kann einer dieser Algorithmen ein Optimum garantieren?

• Ja, Ant Colony Optimization kann das
• Ja, Simulated Annealing kann das
• Ja, Branch and Bound kann das
• Nein, das kann keiner

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