Traveling Salesperson Problem (TSP):

Branch - and - Bound Algorithmen.

In Ramen des Projektes "Routen-Rechner" musste ich so genannte Traveling Salesperson Problem (TSP) lösen. Es gibt eine Menge von verschiedenen Verfahren, die das Problem knacken. Da der "Router-Rechner" auf einem mobilen Gerät laufen sollte, hatte ich noch ein zusätzliches Problemchen: knappe Ressourcen und zwar: CPU ist schwach. Deswegen nach Anschauen mehreren Algorithmen bin ich zum Branch - and - Bound Algorithmen gekommen. Hier finden Sie eine Implementation in Java mit Beschreibung. Hier ist die Fortsetzung. In dieser Beschreibung fällen zwei Klassen: "Cost.java" und "TimeInterval.java". Ausgehend von der Logik des Programms habe ich die Klassen selbst geschrieben. Hier finden Sie noch eine Multithreading Implementierung in Java. Alle diese Links führen zum Magazin "JOURNAL OF OBJECT TECHNOLOGY ". Ich empfehle ihn regelmäßig zu lesen. Noch eine interessante Webseite, wo Sie eine rekursive Implementation in Java finden. Hier ist die direkte Link zur Beschreibung und Quelltext.

Falls die oben gegebene Links nicht funktionieren:

Hier ist der Teil 1 und Teil 2 der Implementierung in Java (ohne Threads).
Hier ist die Implementierung in Java (Multithreading).
Hier ist die rekursive Implementierung in Java.

So weit, so gut. Aber....

Die Implementation ohne Threads funktioniert toll, aber zu langsam. Die rekursive Implementation arbeitet viel schneller, aber schon bei 30 Punkten(Anzahl der Punkten, die man besuchen muss) liefert das Programchen StackOverFlow Exception. Deswegen musste ich wieder suchen. Ich habe eine wirklich alte(40 Jahtre alt) Implementation in Pseudocode gefunden. Die Implementation realisiert Algoritmus von Little. Da diese Implementation rein procedural ist, arbeitet die richtig schnell! Ich dürfte behaupten, die Implementation ist eine der schnellsten, die überhaupt existieren! Diese Implementation finden Sie hier als eine DLL-Datei. Die habe ich in C# geschrieben. Die Bibliothek hat zwei Begrenzungen:

• Die Anzahl zu besuchten Punkten ist auf 35 begrenzt.
• Die Klassenelementen habe ich statisch gemacht, das heißt Sie können nicht mehr als eine Route gleichzeitig berechnen lassen.

Die DLL ist so zu benutzen:

"abstande" ist hier ein zweidimensionaler Array, der die Abstandmatrix darstellt. In Array "tour" ist die Reihenfolge gespeichert, in derer die Orten besucht werden sollen. Also die Route soll so aussehen: "tour[1]->tour[2]->tour[3]->....->". Im "tour[0]" ist die Lange der Route.

Falls Sie eine "normale" Bibliothek haben wollen, nehmen Sie mit mir Kontakt auf!