Algoritme Les 9

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

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

het rugzak probleem

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.

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.

Je kent drie sorteeralgoritmen: BubbleSort, MergeSort en QuickSort. Welke van de drie lijkt erg veel op een bruteforce-algoritme?

1. Bubblesort
2. Mergesort
3. Quicksort

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?

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.

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?

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
  

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.

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.

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.

Bedenk voor zowel het kortstepadalgoritme als de sorteeralgoritmes of een benaderingsalgoritme een probleem oplevert.

1. Het levert een probleem op voor zowel het kortstepad- als de sorteeralgoritmes.
2. Het levert geen probleem op voor zowel het kortstepad- als de sorteeralgoritmes.
3. Het levert wel een probleem op voor het kortstepadalgoritme, maar niet voor de sorteeralgoritmes.
4. Het levert wel een probleem op voor de sorteeralgoritmes, maar niet voor het kortstepadalgoritme.

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

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.

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.

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.

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.

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

• volgende keer gaan we verder met het Chinese postbodeprobleem