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

[Stefan Hirschmann]

Frederik Ramm wrote:
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).

Habe mir Wiki Artikel übe A* und AmeisenAlg 
<http://de.wikipedia.org/wiki/Ameisenalgorithmus> noch einmal 
durchgelesen. A* und Ameisen sind entgegen meiner Erinnerung zwei 
versch. Algorithmen. Also nehme ich alles zurück und behaupte das Gegenteil.

Für A* hast du Recht, es liefert wirklich optimale Ergebnisse. Der 
Ameisen-Alg wird aber laut Wikipedia nicht für normales Routing, sondern 
erst für viel komplexere Sachen (das Problem des Handlungsreisenden, TSP 
[nicht das Prog, das Problem]) verwendet.

Hoffe ich konnte meinen Irrtum erklären.

MfG Stefan