[Talk-de] AIO - Routing über Fähren

[Frederik Ramm]

Hallo,

Carsten Moeller wrote:
> Oben: Dijkstra, Unten: Monav.
> Kann natürlich auch an der Bewertung der Straßen liegen.

Monav kann noch keine Turn Restrictions (Einbahn aber schon). Ansonsten 
fuehrt das CH-Verfahren nach allem, was ich verstanden habe, beweisbar 
zum besten Ergebnis - es ist also keine "wird im allgemeinen schon so 
klappen"-Heuristik, sondern ein exaktes Verfahren.

Ich bin auch kein Experte fuer Routingverfahren, aber Dijkstra ist m.E. 
von den "altertuemlichen" Verfahren am wenigsten fuer die statische 
Routenplanung geeignet. Dijkstra wuerde man hoechstens fuer eine 
dynamische Planung (Ziel konstant, Quelle beweglich) nehmen oder fuer 
eine Planung mit nicht-konkretem Ziel ("naechstgelegene Tankstelle"). 
Ansonsten nimmt man klassisch meistens A*, der hat die gleiche 
Komplexitaet wie Dijkstra, kommt aber meistens schneller zum Ziel. Doch 
zwischen diesen Verfahren, die sich ein schlauer Bastler noch mehr oder 
weniger selbst herleiten kann, und den modernen Alogrithmen wie CH 
liegen Welten, besonders dann, wenn es um den Serverbetrieb geht (wo 
u.U. tausende von Anfragen in der Sekunde beantwortet werden wollen, 
weil man vielen parallelen Nutzern "live" neue Routen praesentieren 
will, wenn sie die Maus bewegen).

Bye
Frederik

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