Als we ergens heen willen gaan kunnen we gebruik maken van een navigatieapparaat.Natuurlijk willen we een zo snel en kort mogelijke route naar onze eindbestemming. Zo als het spreekwoord het al zegt vele wegen leiden naar Rome, kunnen we ook in de echte wereld vele routes nemen om op onze bestemming te komen.
Verschillende locaties binnen Nederland.
Je ziet hierboven de kaart van Nedewrland met daarop ene groot aantal plaatsen aangegeven.Wanneer je verschillende plaatsen wilt bezoeken, heb je heel veel mogelijkheden om je route te kiezen. Je kunt de keuze voor de route ook laten bepalen door een navigatieapparaat. Hoe weet het navigatieapparaat dat wij de kortste route nemen om op onze eindbestemming te komen
Algoritmes
Het navigatieapparaat maakt hierbij gebruik van algoritmes.Een algoritme is een wiskundige methode om problemen op te lossen vanaf het begin tot het einde.
Het oplossen van een probleem wordt gedaan door een aantal vaste instructies uit te voeren zodat er een oplossing ontstaat voor het probleem.Een algoritme kun je zien met de handelingen die je in de ochtend moet verrichten om je klaar te maken om naar school te gaan. Eerst ga je opstaan om daarna vervolgens te ontbijten, te douchen, je aan te kleden en tanden te poetsen.
Kortste paden algoritme, beginstappen
Stel je voor we willen van punt S naar punt T gaan we zien dat dit op meerdere manieren kan we kunnen namelijk de route S-A-T nemen maar we kunnen ook de route S-B-C-T nemen. Hoe kunnen we nu weten wat de snelste route is?
Je begint met startsituatie S, hierbij komt een 0 te staan omdat we op dat moment nog maar 0 kilometer hebben gereden.
We hebben nu de mogelijkheid om van S naar A te gaan, om van S naar B te gaan, om van S naar C te gaan en om van S naar D te gaan.
- Van S naar A is 7
- Van S naar B is 4
- Van S naar C is 9
- Van S naar D is 7
Kortste paden algoritme, vervolgstappen
Nu vertrekken we vanuit punt B en gaan naar de aangrenzende steden A en C. Er is voor B gekozen omdat dit op het moment het kortste pad is.
We zien dat vanuit S naar B en daarna naar A sneller gaat dan rechtstreeks van uit S naar A te rijden. Daarom is de kortste route op dit moment naar punt A 5. Zo zien we ook dat punt C nu afstand 7 krijgt.
We weten tot nu toe dat de kortste afstand naar A 5 is, naar B 4 is, naar C 7 is en naar D 7 is. We vertrekken nu weer vanuit het punt met het laagste cijfer. We hebben de keuze uit punt A, C of D omdat deze punten direct verbonden zijn met het eindpunt.We zien dat er bij punt A het laagste getal staat namelijk 5. Om naar T te gaan moet er 6 bij opgeteld worden en dan zien we dat het eindtotaal op 11 komt. Maar is dit dan de snelste route?
Nee, van A naar T was niet de snelst mogelijke route. Als we van C naar T gaat zien we dat je op 10 uitkomt.Dus 10 is onze kortste route.
Om nu te zeggen welke route je hebt genomen moet je weer terug rekenen. 10-6=4 dus we zijn niet via punt A gegaan. 10-3=7 dus we zijn via punt C gegaan.7-3 =4, dus we zijn via punt B gegaan. 4-4=0 dus S is het startpunt.De snelste route in dit voorbeeld is dus vanuit S naar B naar C naar T.Het navigatieapparaat werkt ook op deze wijze om een kortste route te vinden