Wie funktioniert die Routenoptimierung..??

    Irgendwie finde ich es faszinierend, dass man in ganz Eurp zwei Punkte angeben kann, und dann dieses kleine Gerät ein Routenoptimierung vornimmt... ?( ?(


    Gibt es irgendwo im weltweiten Netz eine leichtverständliche Beschreibung, wie das diese kleinen Dinger eigentlich machen bzw. ein Hinweis zu den angewendeten Algorithmen .... ?( ?(

    Hallo NikNolte7,


    meine Vermutung wäre folgende:


    In Matheunterricht in der Schule gabs folgendes Kapitel: Extremwertaufgaben mit Nebenbedingungen.


    Also zu berechnen ist eine Route von A nach B unter der Bedingung, dass die Zeit ein Minimum ist = schnellste Route.
    Dazu muß das Programm wissen, wie schnell man auf jeder Straße fahren darf. Dann analysiert das Programm verschiedene Routen mit oben genannten Algorithmus.
    So funktionierts in meiner Vorstellung...


    Gruß, PLD


    na toll.... Aber wenn ich mir Vorstelle, wieviel Möglichkeiten es gäbe ( z.B. von Hamburg nach Lissabon !!) , muß es schon ein sehr effizienter Algorithmus sein ( Binäre Bäume etc. ).. :P

    Also wie das programmiertechnisch gelöst wird, keine Ahnung ?(


    Aber ich hab mal die Route Hamburg-Lissabon in TTN5 eingegeben:
    - für die schnellste Route hat er ca. 150.000 Straßen analysiert, dafür brauchte er etwa 30sek.
    - für die kürzeste Route waren es ca. 2.300.000 Straßen und hat 10 mal länger gedauert.


    Da muß er sich ganz schön abrackern der Kleine...

    Routenfindung für Naviprogramme ist im Prinzip gleichzusetzen mit dem Problem aus der Graphentheorie, in einem gewichteten, gerichteten Graphen kürzeste Wege von a nach b zu finden. Die Knoten des Graphen wären Straßenkreuzungen, die Kanten die Straßen, Gewichte wären Länge der Straße dividiert durch die mögliche Geschwindigkeit.


    Es gibt etliche Algorithmen zur Lösung des Problems, einer der bekanntesten ist der Algorithmus von Dijkstra. Dieser löst das Problem in Zeit O(m+n log(n) ). Also schon recht effizient. :)


    Bei so vielen beteiligten Straßen und Kreuzungen MUSS der Algorithmus auch effizient sein, sonst müßte man auf einem Rechnerchen wie einem PDA für längere Strecken Stunden aufs Ergebnis warten.

    2 Mal editiert, zuletzt von Loc2262 ()

    Zitat

    Original von PLD
    In Matheunterricht in der Schule gabs folgendes Kapitel: Extremwertaufgaben mit Nebenbedingungen.


    Also zu berechnen ist eine Route von A nach B unter der Bedingung, dass die Zeit ein Minimum ist = schnellste Route.


    Dazu müßte das Naviprogramm aber eine Funktion aufstellen, die es minimieren kann, die also alle möglichen Wege enthält. Das wär viel zu viel, außerdem würde es das Problem in eine ganz neue Dimension heben, da mit Floating-Point und kontinuierlichen Verfahren wie Ableitungen zu rechnen. ;)

    Hab mir schon gedacht, dass meine "Theorie" ein wenig zu verwegen war, aber mit der Graphentheorie hab ich mich bisher noch nicht beschäftigen müssen.
    Da sieht man(n) wieder, man lernt nie aus...


    thanx
    PLD

    funky44: Gern. Im Informatik-Studium muß man sich mit solchem Krims wie Graphentheorie leider mehr als genug herumschlagen. :)