Algoritme Les 8

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

Deze les

• Toestandsdiagram
• antwoorden
• onoplosbare problemen
  

1. 7 paden
2. 27 mogelijkheden
3. 3 mogelijkheden
4. ...........
   

onoplosbare problemen

Er zijn heel veel problemen waar geen snelle oplossing voor bestaat. Van sommige problemen is het zelfs maar de vraag of er wel een oplossing voor is.

Het bijzondere is dat veel van die problemen heel eenvoudig te begrijpen zijn. Ook komen ze in de dagelijkse praktijk voor.

Stel je de volgende situatie voor.

Je bent op een plek waar een verzameling dozen staat. Die dozen bevatten waardevolle spullen. Deze dozen hebben niet allemaal hetzelfde gewicht en dezelfde waarde.

Je hebt een rugzak bij je waarmee je maximaal 12 kg kunt vervoeren.

Je kunt je afvragen welke dozen je in je rugzak moet stoppen zodat er zo veel mogelijk waarde (in euro's) in zit. Dit probleem is beroemd en wordt het rugzakprobleem genoemd. Het is een heel eenvoudig probleem, maar er bestaat geen snel algoritme om het op te lossen. In dit voorbeeld is dat niet zo erg. Want er zijn maar vijf dozen en er mag maar 12 kg mee.

Vraag

Probeer een oplossing te vinden voor deze situatie.

Kies de dozen die je in je rugzak stopt om zo veel mogelijk waarde mee te nemen.

Oplossing

Na even puzzelen kon je in dit geval de oplossing vinden. Maar dat lukt niet meer als je een hele vrachtwagen mag vullen en je kunt kiezen uit honderden dozen.

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

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

Alle mogelijkheden langsgaan

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.

bruteforce-algoritme

Iemand neemt een getal tussen 1 en 100 in gedachten. Jij moet raden welk getal dat is.

Een bruteforce-oplossing is dan dat je de getallen één voor één langsgaat. Je raadt 1, dan 2, enzovoort.

Bij het rugzakprobleem is bruteforce nauwelijks een oplossing. Voor kleine problemen is bruteforce soms wel een goede oplossing.

Je kent drie sorteeralgoritmen: Bubble, Merge en Quick. Welke van de drie lijkt erg veel op een bruteforce-algoritme?

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?

4 * 5 * 5 * 6 = 600 mogelijke routes

Volgende les

• het benaderen van de oplossing van een onoplosbaar probleem

• het Chinese postbodeprobleem