Das Traveling Salesman Problem

Schnell und fast exakt.

Da die exakte Lösung des Problems des Handlungsreisenden in der Praxis meistens nicht praktikabel ist, weil sie zu lange dauert, bedient man sich verschiedener Annäherungsverfahren, sogenannter Heuristiken, die zwar nicht exakt die kleinste Route berechnen, sondern die annährend Kleinste, im Gegenzug dafür aber um ein Vielfaches schneller sind.

Es gibt sehr viele Heuristiken, die mittlerweile sehr gut ausgereift sind und Routen berechen, die nur maximal 1.5 mal so lang sind wie die Exakte. Zwei dieser Heuristiken möchten wir im Folgenden vorstellen und anschließend mit einem Programm demonstrieren, dessen Quellcode Sie sich unter downloads herunterladen Können.