Algoritme Les 9

1 / 32
next
Slide 1: Slide
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4

This lesson contains 32 slides, with interactive quizzes and text slides.

time-iconLesson duration is: 50 min

Items in this lesson

Slide 1 - Slide

  • Je weet dat niet alle problemen door een computer opgelost kunnen worden.
  • Je kent het spanningsveld tussen correctheid en efficiëntie van een algoritme.
  • Je weet wat brute force is.
  • Je kent de werking van klassieke problemen, zoals het rugzakprobleem, het handelsreizigersprobleem en het Chinese postbodeprobleem.

Slide 2 - Slide

het rugzak probleem

Slide 3 - Slide

Slide 4 - Slide

Slide 5 - Slide

Er is geen snel algoritme dat het rugzakprobleem oplost. Daarom kunnen we twee dingen doen:

  • Een algoritme maken dat alle mogelijkheden langsgaat.
  • Een algoritme maken dat zo dicht mogelijk in de buurt van de oplossing probeert te komen.

Slide 6 - Slide

Brute force Algoritme
Als we alle mogelijkheden controleren, zullen we de oplossing zeker vinden. We maken dan een algoritme dat correct is. Natuurlijk is zo'n algoritme niet efficiënt, want het kan heel lang duren voordat de oplossing gevonden is. Soms zo lang dat we de oplossing in de praktijk misschien niet vinden.

Een algoritme dat alle mogelijkheden langsgaat, heet een bruteforce-algoritme.

In de praktijk probeer je altijd te voorkomen om een bruteforce-algoritme te gebruiken. Bij het rugzakprobleem is bruteforce nauwelijks een oplossing. Want als je 30 verschillende dozen hebt om uit te kiezen, moet je al meer dan 1 miljard mogelijkheden controleren. Voor kleine problemen is bruteforce soms wel een goede oplossing.

Slide 7 - Slide

Je kent drie sorteeralgoritmen: BubbleSort, MergeSort en QuickSort. Welke van de drie lijkt erg veel op een bruteforce-algoritme?
A
Bubblesort
B
Mergesort
C
Quicksort

Slide 8 - Quiz

Vraag
Een vrachtwagen moet spullen bezorgen in Amsterdam, Zwolle en Assen. De vrachtwagen vertrekt vanuit Utrecht en gaat eerst naar Amsterdam. De chauffeur kan voor die rit kiezen uit vier routes. Van Amsterdam naar Zwolle zijn er vijf routes mogelijk. En van Zwolle naar Assen ook vijf routes. Voor de terugreis van Assen naar Utrecht zijn er zes mogelijke routes. Om de beste route te bepalen voor de gehele reis gebruiken we een bruteforce-algoritme.
Hoeveel mogelijke routes moet het algoritme onderzoeken?

Slide 9 - Slide

Slide 10 - Slide

Benaderen van de oplossing
Er zijn veel algoritmen die het rugzakprobleem niet oplossen, maar de oplossing wel benaderen.
Dit zijn niet de allerbeste oplossingen. Maar ze zijn ook niet slecht.
Deze algoritmen zijn belangrijk omdat het rugzakprobleem in allerlei praktijksituaties voorkomt.

Slide 11 - Slide

Voorbeelden
Je hebt bijvoorbeeld een aantal houten onderdelen nodig die je zelf moet uitzagen. Je wilt daarvoor zo weinig mogelijk houten platen gebruiken. Welke onderdeel zaag je uit welk stuk hout? Een ander voorbeeld is het vervoeren van goederen door een containerschip. Welke goederen moet je in welke container stoppen om het laden en lossen zo efficiënt mogelijk te maken?

Slide 12 - Slide

verschillende manieren
  • het vereenvoudigen van het probleem, zodat het wel snel en correct oplosbaar is.
  • het vinden van een willekeurige oplossing.
  • een bepaalde hoeveelheid tijd geven om tot oplossingen te komen

Slide 13 - Slide

George Dantzig
De Amerikaanse wiskundige George Dantzig (1914 – 2005) publiceerde het volgende algoritme in 1957. Hij heeft ook een beroemd geworden optimaliseringalgoritme bedacht. Dit is de simplexmethode.

Slide 14 - Slide

Algoritme van Dantzig
Als oplossing voor het rugzakprobleem heeft de wiskundige Dantzig het volgende algoritme bedacht:
  1. Bereken voor elke doos de waarde per kilogram.
  2. Sorteer de dozen vervolgens op die waarde van groot naar klein.
  3. Vul de rugzak in diezelfde volgorde tot het niet meer past.
Dit algoritme is efficiënt, maar geeft niet de beste oplossing. Dat is niet erg: in de praktijk blijkt het goed te werken.

Slide 15 - Slide

Vraag
Voor het vinden van een kortste route kun je het algoritme van Dijkstra gebruiken. Voor het sorteren van data kun je bijvoorbeeld MergeSort of QuickSort gebruiken. Die algoritmen leveren altijd een correcte oplossing. Je zou ook een benaderingsalgoritme kunnen gebruiken dat nog sneller is.

Slide 16 - Slide

Bedenk voor zowel het kortstepadalgoritme als de sorteeralgoritmes of een benaderingsalgoritme een probleem oplevert.
A
Het levert een probleem op voor zowel het kortstepad- als de sorteeralgoritmes.
B
Het levert geen probleem op voor zowel het kortstepad- als de sorteeralgoritmes.
C
Het levert wel een probleem op voor het kortstepadalgoritme, maar niet voor de sorteeralgoritmes.
D
Het levert wel een probleem op voor de sorteeralgoritmes, maar niet voor het kortstepadalgoritme.

Slide 17 - Quiz

het Chinese postbodeprobleem
het kortstepadalgoritme van Dijkstra hebben we besproken. Daarmee is het mogelijk om de kortste afstand tussen twee punten te vinden. Er zijn twee bekende routeproblemen die echter lastig op te lossen zijn. Dit zijn het handelsreizigersprobleem en het Chinese postbodeprobleem

Slide 18 - Slide

Het handelsreizigersprobleem
Er is een reiziger die naar een aantal steden moet reizen. Hij wil alle steden maar één keer bezoeken. Hij wil daarnaast zo weinig mogelijk hoeven te reizen. Dit is één van de bekendste moeilijk op te lossen problemen. Je kunt het algoritme van Dijkstra hiervoor niet gebruiken. Dat berekent alleen de kortste route tussen twee verschillende steden.

Slide 19 - Slide

Het Chinese postbodeprobleem
Hierbij is het van belang dat iedere weg tussen de punten minstens één keer moet worden doorlopen. Dit probleem kun je heel goed vergelijken met het lopen van een folderwijk. Dan moet je natuurlijk ook alle straten aflopen. Het maakt niet uit dat je een kruispunt meerdere keren oversteekt. Je zult de folderwijk het meest efficiënt lopen als je alle straten maar één keer doorloopt. Soms is dat niet mogelijk.

Slide 20 - Slide

Ook bij het Chinese postbodeprobleem kunnen we gebruikmaken van een gewogen graaf. In het volgende voorbeeld zijn er negen straten waar de postbode zijn post moet bezorgen. Er zijn zes kruispunten waar meerdere straten samenkomen. De getallen langs de straten geven aan hoe lang een weg is.

Slide 21 - Slide

Slide 22 - Slide

Hoe vinden we nu de kortste route, waarbij alle straten minstens één keer worden doorlopen? In dit eenvoudige geval is het mogelijk om alle mogelijke routes te berekenen. Maar dit is praktisch ondoenlijk als het gebied zo groot is als een dorp. Zelfs met een zeer snelle computer.

Slide 23 - Slide

Sommige kruispunten hebben een even aantal aangesloten straten (groen: C en D). De andere hebben een oneven aantal aangesloten straten (blauw: A, B, E en F). Voor het berekenen van de kortste route is de volgende stelling van toepassing:
“Als er meer dan twee kruispunten met een oneven aantal aangesloten straten zijn, moeten sommige straten meerdere keren worden doorlopen.”

Slide 24 - Slide

Slide 25 - Slide

Slide 26 - Slide

Slide 27 - Slide

Slide 28 - Slide

Slide 29 - Slide

Slide 30 - Slide

Slide 31 - Slide

  • volgende keer gaan we verder met het Chinese postbodeprobleem

Slide 32 - Slide