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

[Frederik Ramm]

Hallo,

> 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.

Das ist falsch. A* und Dijkstra finden beide eine optimale Loesung
(sofern A* eine geeignete Heuristik verwendet, was bei Routing auf
Geodaten trivialerweise mit der Luftlinie der Fall ist). A* benutzt
zwar eine Heuristik, aber nur, um den Graphen moeglichst ideal zu
durchsuchen. Wenn Du eine sehr schlechte Heuristik verwendest, naehert
sich die Laufzeit von A* der von Dijkstra an, aber das Ergebnis ist
immer noch optimal.

Die Staerke von Dijkstra liegt da, wo das Ziel nicht eindeutig iden-
tifiziert ist ("bitte zur naechstgelegenen Tankstelle") - das kann A*
naemlich nicht. Ich glaube, dass der Dijkstra auch zuweilen benutzt
wird, um mobil zu navigieren, weil Du ihn rueckwaerts anwenden kannst
und dann den vorverarbeiteten Graphen fuer verschiedene aktuelle
Positionen des Fahrzeugs verwenden kannst, aber so tief steck' ich da
nicht drin.

Bye
Frederik
 
-- 
Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00'09" E008°23'33"