Les 4 - Routeplanning & Het kortstepadalgoritme

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Bubble sort

Routeplanning & het kortstepadalgoritme

Standaard algoritmen

Leerdoel

Aan het eind van deze les kun je uitleggen waarom het lastig is om een efficiënt algoritme te bedenken voor een routeplanner. Ook kun je een gewogen graaf maken en interpreteren en het kortstepadalgoritme van Dijkstra toepassen op gewogen grafen.

Sorteer de volgende lijst getallen met MergeSort: 9 2 7 3

Sorteer met MergeSort

Hiernaast zie je de lijst getallen 9 2 7 3 juist  met MergeSort gesorteerd.

Bekijk de volgende lijst getallen: 4 8 2 9 1 5. Deze lijst wordt gesorteerd met behulp van quicksort. Als pivot wordt het getal 4 gekozen. De volgende pivots zijn ook altijd het linkergetal.

Wat is GEEN juiste tussenstap die moeten worden gezet om deze lijst te sorteren.

1. 2 1 4 8 9 5
2. 1 2 4 5 9 8
3. 1 2 4 5 8 9

Wat is GEEN juiste tussenstap?

1 2 4 5 9 8 is geen juiste tussenstap want 9 8 is een situatie die nooit op kan treden.

Hoe werkt een routeplanner?

• Routeplanner: snelle (snelste) route van A naar B

• Planner kent alleen de afstanden tussen aangrenzende plaatsen

• Gaat efficiënt alle
  combinaties af en vindt
  zo een route.

De kortste route...

Een route vanuit Rotterdam naar Den Helder loopt volgens de wegen in bijgevoegde kaart altijd via Amsterdam. Maar er zijn twee routes vanuit Rotterdam naar Amsterdam

Vraag: Loopt de kortste
route via Den Haag of via
Utrecht?

Loopt de kortste route tussen Rotterdam en Den Helder via Den Haag of via Utrecht?

Gebruik de gegevens uit de bovenstaande kaart en tabel.

1. Den Haag
2. Utrecht

De kortste route...

De route via Utrecht is 90 + 50 + 60 = 200 km lang. De route via Den Haag is 90 + 55 + 25 = 170 km lang. Via Den Haag is dus het kortst.

Korstepadalgoritme

• Gemaakt door de Nederlandse wiskundige
   Edsger Dijkstra (1930 - 2002).

• Het algoritme van Dijkstra berekent in een gewogen
   graaf het kortste pad tussen twee plaatsen.  

Korstepadalgoritme

• Om de kortste route te bepalen, is het handig om
  de plaatsen weer te geven in een schema.
  Zo'n schema wordt ook wel een graaf genoemd. 
  
  

• Op de verbinding tussen de plaatsen kan de afstand in kilometers worden weergegeven. Een graaf waarin ook afstanden vermeld staan, heet een gewogen graaf.

Korstepadalgoritme

• Cirkels zijn plaatsen.
• Lijnen zijn mogelijke reizen.
• Cijfers zijn afstanden in kilometers. Dit
  maakt dat het een gewogen graaf is.

Het algoritme vindt efficiënt de afstanden
tussen alle punten. 

Korstepadalgoritme

Werking

Opdracht 1

• Voeg twee extra plaatsen toe aan
  de gewogen graaf: Arnhem en Zwolle.
• Gebruik de kaart om te zien waar de
  plaatsen ongeveer moeten komen.
  In de volgende tabel staan de afstanden
  om de gewogen graaf compleet te maken.

Uitwerking opdracht 1

Vraag 2

Kijk goed naar je uitwerking van

opdracht 1.

Via welke plaatsen, behalve Utrecht,
loopt de kortste route tussen
Den Haag en Arnhem?

Via welke plaatsen, behalve Utrecht,loopt de kortste route tussen Den Haag en Arnhem?

1. Den Helder
2. Amsterdam
3. Rotterdam
4. Zwolle

Uitwerking vraag 2

Het juiste antwoord is Rotterdam.

Als je de kilometers tussen
de plaatsen bij elkaar optelt,
is dit de kortste route.

Vraag 3

De weg tussen Utrecht en
Amsterdam is afgesloten vanwege
een ongeval. Daardoor moet er een
alternatieve route genomen worden
tussen Arnhem en Den Helder.

Hoeveel kilometer langer is deze
alternatieve route?

Hoeveel kilometer langer is deze alternatieve route?

1. 50 km
2. 90 km
3. 140 km

Antwoord vraag 3

De kortste route was
65 + 50 + 90 = 205 km.

De nieuwe route is via Rotterdam
en Den Haag:
65 + 60 + 25 + 55 + 90 = 295,
dat is 90 km langer.

Vraag 4

Bereken met het algoritme van
Dijkstra de kortste afstand tussen
Den Haag en Zwolle.

Vul hierbij eenzelfde tabel in zoals
die gebruikt is in het voorbeeld
in de tekst en de video.

Hoeveel kilometer bedraagt de kortste afstand tussen Den Haag en Zwolle?

1. 85 km
2. 120 km
3. 150 km
4. 220 km

Uitwerking
vraag 4

De korste route is:
Den Haag - Rotterdam
- Utrecht - Zwolle.

Vraag 5

Hiernaast zie je een gewogen graaf
van de plaatsen A t/m E en hun
onderlinge afstanden. Bepaal met
behulp van het algoritme van Dijkstra
de kortste route van A naar E. 

Vul hierbij eenzelfde tabel in zoals die gebruikt is in het voorbeeld
in de tekst en de video. Wat is de kortste route?

Wat is de kortste route?

1. A-B-E
2. A-C-E
3. A-B-C-E
4. A-C-D-E

Uitwerking vraag 5

De kortste route is:
A - C - D - E en
is 60 km lang.

Met het algoritme van Dijkstra kun je de kortste route bepalen tussen twee plaatsen in de graaf. Je kunt in plaats van de afstand ook de reistijd tussen de plaatsen vermelden.

Welke informatie kun je op die manier berekenen aan de hand van het algoritme van Dijkstra?

1. De snelste route
2. Hiermee bereken je óók de kortste route
3. De langste route
4. De meest efficiënte route

Welke informatie kun je berekenen?

"De snelste route" kun je altijd berekenen aan de hand van de reistijd. Wellicht heb je "de meest efficiënte route" gekozen. Echter, voor de meest efficiënte route mis je de context. Dit antwoord is dus niet zo maar juist. In dit voorbeeld wordt de reistijd tussen de plaatsen aangegeven. Dan is de efficiëntie dus in tijd. Echter als jij op zoek bent naar de kortste route in kilometers, is dat niet altijd de kortste route in tijd, en dus niet per definitie de meest efficiënte route.

Leerdoel gehaald?

Aan het eind van deze les kun je uitleggen waarom het lastig is om een efficiënt algoritme te bedenken voor een routeplanner. Ook kun je een gewogen graaf maken en interpreteren en het kortstepadalgoritme van Dijkstra toepassen op gewogen grafen.

Doornemen

LessonUp

Les 4 - Standaard algoritmen - Routeplanning & Het kortstepadalgoritme

Fundament 

B: Grondslagen -> Algoritmen (B1) -> 2. Standaard algoritmen 2.7 - 2.8