Les 7 - Onoplosbare problemen - over tijdcomplexiteit

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

Bubble sort

Over tijdcomplexiteit

Onoplosbare problemen

Leerdoel

Aan het eind van deze les kun je uitleggen waarom verschillende problemen een andere tijdcomplexiteit hebben. Ook ken je een voorbeeld van een onoplosbaar probleem en kun je rijk worden door het P- vs NP-probleem op te lossen.

Onoplosbare problemen?

• Niet voor alle problemen is er een perfect algoritme
  
• Hoe dat zit en wat voor problemen zijn dat?

Het rugzakprobleem

Stel...

• In je rugzak past maximaal 12 kg.
• Je wilt zoveel mogelijk waarde
  (in euro’s) meenemen
  

Welke dozen moet je in je rugzak
stoppen?

Sleep de dozen die samen zoveel mogelijk waarde (in euro's) vormen in de rugzak

Oplossing van het rugzakprobleem

De doos van €12 heeft weliswaar de hoogste waarde, maar als je deze doos kiest, mag er nog maar 1 kilogram in de rugzak. Je kunt dan maximaal €2 aan waarde toevoegen,
voor een totaal van €14. De combinatie
van de lichtere dozen
(€2 + €2 + €3 + €8 = €15) is meer waard.

Het rugzakprobleem in de praktijk

• Het rugzakprobleem komt in de praktijk vaak voor, bijvoorbeeld bij het laden van een vrachtwagen
• Of wanneer jij bepaalt waaraan je je zuur verdiende geld uitgeeft.
• Bij veel voorwerpen bestaat er geen snel
  algoritme dat dit probleem kan oplossen

Wat is er dan wel mogelijk?

Correctheid en efficiëntie

Een algoritme maken dat alle mogelijkheden langsgaat

• Dit heet een brute-forcealgoritme
  
• Het levert altijd een correcte oplossing
  
• Maar het is niet efficiënt
  
  

Een algoritme maken dat zo dicht mogelijk in de buurt van de oplossing probeert te komen

• Zo’n algoritme is wel efficiënt, maar niet (helemaal) correct

Je kent drie sorteeralgoritmen: bubble sort, merge sort en quicksort.

Welke van de drie lijkt erg veel op een bruteforce-algoritme?

1. Bubble sort
2. Merge sort
3. Quicksort

Bruteforce sorteeralgoritme

Bubble sort doorloopt steeds de hele lijst en verwisselt eventuele verkeerde combinaties van twee getallen, tot die er niet meer zijn. Dat lijkt erg op het langslopen van alle mogelijkheden, wat een bruteforce-algoritme doet.

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 langer is deze alternatieve route?

1. 50 km
2. 90 km
3. 140 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 Dijksta 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?

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 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