bfsdasauge
Erfahrenes Mitglied
Hallo zusammen,
weiß jemand, nach welchem Verfahren herkömmliche Routenplaner arbeiten? Gibt es da irgendwelche mathematischen Tricks?
Bislang bin ich davon ausgegangen, das man das ganze geometrisch lösen kann. D.h. jeder Ort erhält eine eindeutige Koordinatenzuweisung. Zudem wird in einer Datenbank jede Ort-Ort Verbindung als Vektor hinterlegt.
Wenn man nun eine Routenanfrage stellt, errechnet das Programm zuerst den Vektor (A->B) und versucht dann anhand der Verbindungsinformationen über die Richtung der einzelnen Verbindungsvektoren verschiedene mögliche Strecken zu finden.
Konkret würde das heißen, er versucht sich von Ort zu Ort durchzuhangeln, und verwendet dabei die Verbindung, deren Vektor dem der gesuchten Strecke (A->B) am ähnlichsten ist (Winkel). Zudem wird der Vektor der gesuchten Strecke permanent neu berechnet. Quasi nach jedem Erreichen eines neuen Ortes.
Das ganze funktioniert aber nur stark eingeschränkt, weil bei langen Strecken eine totale Unschärfe reinkommt. Das liegt vorallem daran, daß bei jeder Entscheidung welche Verbindung nun die beste ist, immer nur das Detail betrachtet wird und nicht die gesamte Anfrage.
Da verennt sich das System z.B. in Sackgassen, oder es rechnet im Kreis.
Wie also lässt sich das Problem lösen?
Gruß
weiß jemand, nach welchem Verfahren herkömmliche Routenplaner arbeiten? Gibt es da irgendwelche mathematischen Tricks?
Bislang bin ich davon ausgegangen, das man das ganze geometrisch lösen kann. D.h. jeder Ort erhält eine eindeutige Koordinatenzuweisung. Zudem wird in einer Datenbank jede Ort-Ort Verbindung als Vektor hinterlegt.
Wenn man nun eine Routenanfrage stellt, errechnet das Programm zuerst den Vektor (A->B) und versucht dann anhand der Verbindungsinformationen über die Richtung der einzelnen Verbindungsvektoren verschiedene mögliche Strecken zu finden.
Konkret würde das heißen, er versucht sich von Ort zu Ort durchzuhangeln, und verwendet dabei die Verbindung, deren Vektor dem der gesuchten Strecke (A->B) am ähnlichsten ist (Winkel). Zudem wird der Vektor der gesuchten Strecke permanent neu berechnet. Quasi nach jedem Erreichen eines neuen Ortes.
Das ganze funktioniert aber nur stark eingeschränkt, weil bei langen Strecken eine totale Unschärfe reinkommt. Das liegt vorallem daran, daß bei jeder Entscheidung welche Verbindung nun die beste ist, immer nur das Detail betrachtet wird und nicht die gesamte Anfrage.
Da verennt sich das System z.B. in Sackgassen, oder es rechnet im Kreis.
Wie also lässt sich das Problem lösen?
Gruß