zaterdag, oktober 06, 2007

Labyrinth

Of moet ik doolhof zeggen? Ik moet doolhof zeggen. Een labyrinth heeft één weg naar het centrum. Nergens hoef je een keuze te maken. Als je in het midden bent aangekomen brengt de enig mogelijke wandeling je weer veilig naar buiten. Het doolhof is geheel anders. Daar moet je constant kiezen. Er zijn doodlopende trajecten, en als je er daarvan drie gehad hebt ben je de draad volledig kwijt. Bij toeval bereik je het centrum van het doolhof. Er staat een bankje, maar je bent te rusteloos om er te gaan zitten. Je moet weer naar buiten. Shit man! Was er maar een strategie die ervoor zorgt dat je de uitgang vindt. Altijd rechts afslaan. Of was het links?
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:

Blogger Marco said...

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

10:05 p.m.  

Een reactie posten

<< Home