Wat is het datamodel (en/of algorithme) achter een navigatiesysteem?

Een navigatiesysteem is een bak met GPS-coördinaten, waartegen de huidige positie wordt aangehouden om de route te bepalen.
Ik zou verwachten dat daar veel gegevens voor nodig zijn. Geen probleem tegenwoordig, we proppen 120 Gb in een vestzakje, maar hoe komt een navigatiesysteem zo zuinig?
Hoe weet mijn systeempje nou dat ik op de provinciale weg N201 rijd? Die weg is 56 kilometer lang (Zandvoort-Hilversum), met flink wat bochten erin: volgens welk datamodel of algorithme kun je het label N201 hangen aan een verzameling coördinaten? En die honderden zijstraten herkennen?
En dat in m.b.v een database die maar 27 Mb groot is ?
(Of nog gekker, de database met gegevens van Noorwegen is maar 8 Mb. Frankrijk 32 Mb.)

Weet jij het antwoord?

/2500

Het beste antwoord

In een navigatiesysteem zitten verschillende intelligente algoritmes. Het belangrijkste probleem van een navigatiesysteem is eigenlijk het bepalen van de korte route van het ene punt naar het andere punt in een graaf. Dit probleem wordt omscherven door het kortstepadprobleem. Onze vriend Dijkstra heeft een algoritme bedacht om dit op te lossen (zie bron). Echter komt hier natuurlijk wel iets meer bij kijken dan beschreven staat op wikipedia, want als je niet in een vroeg stadium uitsluit welke routes zinloos zouden zijn, dan krijg je een veel te grote boom aan mogelijkheden. Wat betreft die ruimte is gewoon een kwestie van efficient gegevens in een database opslaan (denk aan opslaan in vectoren). Daarvoor is wat terug te vinden in de tweede bron, wel Engelstalig helaas.

Bronnen:
http://en.wikipedia.org/wiki/Map_database_...
http://nl.wikipedia.org/wiki/Kortstepadalgoritme

Ze hangen niet aan iedere individuele weg een set coördinaten maar geven de kaar als geheel een set coördinaten en vertellen de software dat de auto zich op de weg moet bevinden als het in de buurt van de coördinaten van de weg komt. De software berekend ter plekke waar op de kaart je huidige GPS coördinaten zijn en is geprogrammeerd om een weg te herkennen als een plaats waar je kan rijden. Eigenlijk werkt dat deel niet anders dan dat windows is geprogrammeerd om te herkennen wanneer je muis over een knop heen gaat en bedenkt dat je daar wel kan klikken. Erg eenvoudig principe. Pas vervolgens wat slimme 21e eeuwse data compressie systemen toe op je kaart en voila...... De prijs zit hem voornamelijk in de kaart (zijn vrij dure dingen om te maken en zitten de nodige copyrights op) en de GPS ontvanger. De eigenlijke software is vrij eenvoudig.

Het is een kaartje van niks met coördinaten en wegen... Ik weet niet welk navi-systeem dat jij hebt, maar het stelt toch niet veel voor, grafisch gezien... Maar elk punt op de kaart krijgt een plek en coördinaten, en die behoeven niet de werkelijke data te zijn, gecodeerd kan ook ten opzicht van elkaar. En elk stukje weg krijgt een gewicht mee... Ik weet niet anders hoe dat uit te leggen, een factor kan ook... Het kaartje wordt doorzocht volgens een algoritme door de kleinste oplossing van A naar B. Dan wordt elk stukje met de factor opgeteld en bij elkaar genomen en als voor die instelling (kortste of snelste enz enz) het optimum bepaald. Het geluid zit in zeer zwaar gecomprimeerde stukjes mp3 files, dus dat is ook heel klein... Je vroeg toch niet naar hoe dat tot stand komt, hoe dat je gps weet waar je zit... De satellieten in een geostationaire baan die elke 30 seconden een seintje afgeven van de exacte tijd en dan via driehoeksmeting met andere satellieten kan berekenen waar je zit op de kaart van je gps-navigatie-systeem...

Stel zelf een vraag

Ben je op zoek naar het antwoord op die ene vraag die je misschien al tijden achtervolgt?

/100