Annäherung für das "Traveling salesman"-Problem

[alexdrik]

Hallo,

ich hab eine Annäherung an das Problem des Traveling Salesman geschrieben, also einen Algorithmus, der in einer vorgegebenen Punktemenge idealerweile den kürzesten Weg sucht. Das kann man z.b. zum Anfahren von Positionen für das Bohren von Löchern brauchen.

Der Algorithmus testet in einer (anfangs kleinen) Liste, an welcher Stelle ein weiterer Punkt eingesetzt werden muß, damit der Gesamtweg am kleinsten ist. Sind alle Stellen ausgestetet, wird die kürzste Reihenfolge verwendet und der nächste Punkt durchgetestet, solange bis alle ursprünglichen Punkte in der Liste enthalten sind.
Damit lässt sich zwar in vielen Fällen nicht der kürzeste Weg finden, allerdings oftmals eine deutliche Verkürzung des Weges.

Um die Entfernungsberechung nicht jedesmal durchführen zu müssen, werden die Werte in einem Array gespeichert. Braucht Speicher, bringt Rechenzeit.

Der kürzeste Weg läßt sich nur finden, wenn man alle Kombinationen ausprobiert, dann muß man aber (n = Anzahl der Punkte) n-Fakultät Wegberechnungen durchführen, dieser Algorithmus kommt mit ungefähr n hoch 3 Wegberechnungen aus.

Für eine große Anzahl an Punkten liese sich eine weitere Verbesserung der Rechenzeit (und effektive Verkleinerung des Caches), natürlich mit Verschlechterung der Wegberechnung, erzielen, indem man z.B. ein zweidimensionales Array in mehrere (örtlich zusammenhängende) Arrays aufteilt und diese dann nacheinander abfährt.



[gelöscht durch Administrator]

[hugo]

das hört sich gut an, das sollten wir im entwicklerforum diskutieren