Greedy de wereld rond: hoe kom je het snelst aan de top van de berg?

03/02/2021

Het kiezen van een route aan de voet van de berg is een serieuze zaak, je wilt immers zo snel mogelijk van het panoramische uitzicht gaan genieten. Je werpt een korte blik op de plattegrond die je zojuist aan de toeristenbalie hebt ontvangen. Bij het zien van alle verschillende paden begint het je te duizelen. Weg met die kaart! Je besluit voor een eenvoudige strategie te gaan: op ieder van de splitsingen die je onderweg tegenkomt neem je het pad dat het steilst naar boven loopt. Een slimme strategie, maar ben je zo het snelste aan de top? Of is het verstandiger voor het niet voor de hand liggende pad te kiezen? 
 

Romeo’s, Julia’s en algoritmes

Veel problemen die we in het dagelijkse leven tegenkomen zijn optimalisatieproblemen. Hoe kun je de totale afstand die wordt afgelegd bij het picken van artikelen op rolcontainers minimaliseren? Wat is de kortste route naar de supermarkt? Hoe maximaliseer je het aantal gelukkige Romeo’s en Julia’s door middel van matching algoritmes op een datingsite? Hoe verbind je een set steden met zo weinig mogelijk kilometers asfalt? Veel van deze problemen zijn op te lossen door gebruik te maken van Greedy rekenregels. Greedy algoritmes maken gebruik van een simpele strategie. Het probleem wordt opgelost door het maken van een serie opeenvolgende (lokale) keuzes die op dat moment de hoogste directe winst oplevert, zonder rekening te houden met toekomstige implicaties. Op deze manier denk je zo snel mogelijk de beste oplossing te bereiken. Een Greedy algoritme neemt beslissingen door één stap vooruit te kijken. Helaas resulteert dit echter niet altijd in een globaal optimale oplossing.

Figuur 1 geeft een goed voorbeeld van zo’n Greedy strategie. Dit netwerk heeft als doel het bepalen van het pad met de hoogste som. Een Greedy algoritme kiest altijd de meest voor de hand liggende keuze en gaat als volgt te werk: bij ieder knooppunt kiest hij het daaropvolgende knooppunt met het hoogste nummer, zie figuur b. De optimale oplossing is echter 0 – 5 – 90 (figuur c). 95 vs. 45 is een significant verschil! Het Greedy algoritme is niet in staat de optimale oplossing te vinden gezien het een vooruitziende blik mist.

 

Fietsen langs Rijksmonumenten

Dan een voorbeeld uit de praktijk. Het is een zonnige dag en je besluit een drietal Rijksmonumenten te bezoeken. Het startpunt is Deventer en je doel: de route tussen de rijksmonumenten minimaliseren zodat je zoveel mogelijk tijd overhoudt op locatie. Figuur 2a geeft het netwerk met bijbehorende afstanden (km) tussen de verschillende locatiepunten weer. Je besluit vanaf ieder locatiepunt de kortste route naar de volgende locatie te nemen.

In Deventer heb je de keuze om 18, 60 of 33 kilometer af te leggen naar de eerste bestemming van de dag. De keuze is simpel: allereerst reis je naar Zutphen (18 km). Na een stop in Zutphen is de keuze 40 kilometer naar Rijssen of 45 kilometer naar Haaksbergen (figuur 2b). Je besluit om via Rijssen naar Haaksbergen te gaan en aan het einde van de dag van Haaksbergen terug naar Deventer te keren. Figuur 2b laat het resultaat van de Greedy oplossing zien, figuur 2c de optimale oplossing. In deze optimale oplossing leg je slechts 125 km af, terwijl de je in de Greedy variant 147 km moet fietsen!

 

Kortdurend geluk vs. lange termijn happiness

Gezien een Greedy algoritme zijn keuzes in latere iteraties nooit heroverweegt, zijn Greedy rekenregels niet altijd in staat de optimale oplossing te vinden zoals bovenstaande voorbeelden laten zien. Met eenzelfde redenatie zien we dat het kiezen van het steilste pad aan de voet van de berg niet direct betekent dat je dan ook het snelst boven aan de top staat. Een meer geavanceerd optimalisatie-algoritme zoals simulated annealing is in staat een betere oplossing te vinden. Het kiezen van een suboptimale oplossing in de huidige iteratie betaalt zich aan het einde terug in een betere totaaloplossing. Door slechtere oplossingen te accepteren kan er uitgebreider worden gezocht naar de globale optimale oplossing. Kortom: door eerst een minder steil pad te nemen kun je uiteindelijk alsnog sneller aan de top van de berg zijn!


Hoe pas je dit toe in de praktijk

Bovenstaand voorbeeld aan de hand van Rijksmonumenten is slechts een klein voorbeeld waarbij dit een besparing oplevert van slechts enkele kilometers. Echter op grotere schaal kan dit een forse besparing en vele gelukkige Romeo's en Julia's opleveren! En natuurlijk een nog sneller - en meer voldaan! - uitzicht aan de top van de berg. Ben je benieuwd welke slimme algoritmes jou veel geluk of besparing kunnen opleveren? Neem dan contact met mij op.

 

Wil je op de hoogte blijven van het laatste nieuws van CQM, volg ons op LinkedIn of meld je aan voor onze digitale nieuwsbrief


Fotocredit: Pixabay.
Carien Leushuis MSc

Carien Leushuis MSc

Junior Consultant