Waar is hier de uitgang?
De ouders van Hans en Grietje kunnen in een periode van grote schaarste hun kinderen niet langer te eten geven. Hun stiefmoeder wil ze daarom tegen de zin van hun vader midden in het bos de hongerdood laten sterven. Hans hoort zijn ouders hierover praten en stopt 's nachts uit voorzorg kiezelsteentjes in zijn zak. 's Morgens gaan ze met hun ouders hout zoeken in het bos. Hans gooit telkens ongemerkt een kiezelsteen op de grond. Hun ouders laten ze vervolgens alleen in het bos achter. Wanneer de maan op is gekomen, vinden Hans en Grietje met behulp van de kiezelsteenjes de weg terug naar huis. bron: Meertens Instituut [helaas blijft de link veranderen](demo depth-first search)
Een Formule voor Doolhoven?
voordracht: pdf file
TRiV 06/2007 De weg kwijt... (pdf 10MB)
(tekst Ben de Dood)
Algoritmen in het doolhof
Hans en Grietje wisten het al. Met een hand vol kiezelsteentjes kun je het spoor naar huis weer terugvinden. Ook in een doolhof werkt zoiets. Je kunt de paden markeren met een kiezel om te verhinderen dat je rondjes blijft lopen. We laten een aantal technieken zien om uit het doolhof te komen. Dat is ook nuttig als we ons niet in een doolhof begeven, omdat achter veel problemen een doolhof verborgen blijkt te zijn.
Klein Duimpje
Bij de colleges Algoritmiek en Datastructuren leer je hoe je een doolhof kunt doorzoeken. De meest gebruikte methode heet depth-first search: je loopt zover mogelijk door, willekeurig gangen inlopend, en wanneer het pad doodloopt, keer je op je schreden terug tot het laatste punt waar je afgeslagen bent, om daar een andere, en hopelijk nieuwe, gang te kiezen. In de praktijk betekent dit dat je een krijtje mee moet nemen om de plekken te markeren waar je al geweest bent, om niet nodeloos rond te lopen.Klein Duimpje, geschreven voor studentenblad Eureka! (Jaargang 2, Januari 2005, Nummer 8, blz. 18-19.) [scherpere plaatjes]