Algoritme Les 9

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

vandaag

• rugzakprobleem
• George Dantzig
• het chinese postbodeprobleem
  

het rugzak probleem

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