Funktionsweise Navigerät

[magic_halli]

Hi,

mich beschäftigt schon länger die Frage: Wie funktioniert eigenlich ein Navi fürs Auto?
Ich meine damit, wie wird für den User die schnellste Route von A nach B berechnet??? Das scheint mir ziemlich komplex und schwierig.
Hat jemand ne Ahnung, wie sowas algorithmisch gelöst wird oder hat vielleicht nen Link zu einer guten Erklärung... ?!

Danke

 

[SnooP]

So ne Art Mischung aus dem tatsächlich sehr komplexen Problems des Handlungsreisenden und eine geometrische Lösung... sprich, zieh ne Linie von Ort A nach B und gucke dann darum herum, welche Knoten dazwischenliegen, mit welchen Strecken und welchen Gewichten an diesen Strecken...

der Wiki-Artikel ist sehr gut: http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

welche Form der Optimierungen und welche zusätzlichen Berücksichtigungen/Annahmen da real noch dazukommen, weiß ich allerdings auch nicht ... bzw. kann auch nur Mutmaßungen anstellen.

 

[magic_halli]

Ah ok, danke.
Also das ganze ist auf jeden Fall ein Optimierungsproblem... Das würde ja dann bedeuten, dass über so eine Karte (z.B. von Deutschland) tausende kleine Punkte (quasi ein Rasternetz) gelegt sind, welche die Knoten darstellen (und irgendwie mit einer Wertigkeit versehen sind). Anhand dieser Punkte wird dann also das Optimierungsproblem "kürzester Weg von A nach B" gelöst?! :idea:

Mh, so stell ich mir das jetzt vor... :wink:

 

[SlaterB]

die Punkte sind die Kreuzungen, dort kommt man ja vorbei,

wenn man bei > x Kilometer eh grundsätzlich die Autobahn bevorzugt, soweit vorhanden,
dann sind es auch nicht mehr soviele Punkte

 

[fab!]

ich stell mir das so vor:

da wird "einfach" über ein gegebenes Kartenmaterial ein Algorithmus, wie z.B. dieser "Shortest-Path" laufen gelassen...