[Talk-de] Traveling Salesman für OSM-Routing mit OpenLayers

[Stefan Keller]

Der Ameisenalgorithmus ist ein heuristisches Optimierungsverfahren,
inspiriert vom Verhalten futtersuchender Ameisen. Er findet also meist nur
das Suboptimum, ist dafür wesentlich schneller als Dijkstra. Seine Stärken
liegen u.a. darin, dass lokale Routenänderungen auch nur lokal nachberechnet
werden müssen. Siehe Wikipedia.

@Marcus: Code dazu findest du hier: Siehe www.ameisenalgorithmus.de
--S.

Am 09.04.08 schrieb Stefan Hirschmann <krasnoj at gmx.at>:
>
> Marcus Wolschon wrote:
> > Hallo Stefan,
> >
> > wenn du ihn drin haben willst,
> > bräuchte ich von dir nur eine Implementierung der
> > zwei Methoden des IRouter-Interfaces.
> > http://travelingsales.wiki.sourceforge.net/IRouter
> >
> > Den kann ich dir dann problemlos in TS aufnemen.
>
> Wenn mich nicht alles täuscht, ist A* und Ameisenalg. der selbe Alg.
> Da              DirectedDepthFirstRouter (A*)
> bereits existiert, könnte dieser verwendet werden.
>
> Falls ich mich täuschen sollte, bitte korrigieren.
>
> Dijkstra hat übrigens ein optimales Ergebnis, dafür eine
> Laufzeitkomplexität von O(n Quadrat), d.h. doppelt so viele Straße,
> viermal so viel Rechenaufwand.
>
> A* ist viel schneller, dafür nur Heuristisch, d.h. die Lösung ist nur
> eine Näherung an das Optimum.
>
> MfG Stefan
>
> _______________________________________________
> Talk-de mailing list
> Talk-de at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-de
>
-------------- nächster Teil --------------
Ein Dateianhang mit HTML-Daten wurde abgetrennt...
URL: <http://lists.openstreetmap.org/pipermail/talk-de/attachments/20080409/02a62f96/attachment.htm>