Labyrinth

Is er een algoritme, een routebeschrijving door een probleem waarbij je zeker weet dat de oplossing een keer voorbij komt, voor het vinden van de uitgang van een doolhof? Strikt genomen is het antwoord: "nee". Maar er is wel een algoritme dat ervoor zorgt dat je elk weggetje in een doolhof precies twee keer loopt, in beide richtingen. Als je dat netjes doet komt de uitgang van het doolhof wel een keer voorbij.
Het werkt als volgt (uitgaande van een doolhof met een vloer van zand): bij elke splitsing of kruising die je tegenkomt zet je met een stok een rondje in het pad waar je uitkomt, en een kruis in het pad waar je inloopt. Ga hiermee door met inachtneming van de volgende twee regels: 'ga nooit een pad in waar een kruis staat' en 'ga alleen een pad in waar een rondje staat als het echt niet anders kan'. Het resultaat zal zijn dat je alle paden (dat zijn de verbindingen tussen kruisingen of splitsingen) in het doolhof precies twee keer loopt. De weg naar buiten dus ook.
Jaren geleden hebben we het geprobeerd, met Anna en Joost, in het prachtige doolhof van Paterswolde. Het bleek te werken. Natuurlijk bleek het te werken. Leg maar eens uit waarom!
1 Comments:
nouuu, deze methode zorgt ervoor dat je elke keer terug moet lopen, dus in een rechte pad kom je bij t begin terug, met een pad dat een keer een afslag naar een dood einde loopt, ga je die dode einde in en weer terug.
En een doolhof is dat, maar gewoon heeeel erg uitgebreid :D
Een reactie posten
<< Home