|
Afgelopen augustus, 30 jaar nadat de Rubiks kubus voor het eerst verscheen, bewees een internationaal team van onderzoekers dat hoe vervormd een kubus ook is, deze in niet meer dan 20 zetten kan worden opgelost. Hoewel de onderzoekers enkele slimme trucs gebruikten om te voorkomen dat ze alle 43 quintillion van de mogelijke startposities van de kubus moesten evalueren, was hun bewijs nog steeds gebaseerd op het equivalent van 35 jaar aan rekenwerk op een goede moderne computer. Helaas, voor kubussen die groter zijn dan de standaard Rubiks kubus – met bijvoorbeeld vier of vijf vierkanten op een rij, in plaats van drie – kan het voldoende zoeken naar startposities de rekencapaciteit van alle computers in de wereld te boven gaan. Maar in een paper die zal worden gepresenteerd op het 19e jaarlijkse Europese symposium over algoritmen in september, stellen onderzoekers van MIT, de University of Waterloo en Tufts University de wiskundige relatie vast tussen het aantal vierkanten in een kubus en het maximale aantal zetten dat nodig is om op te lossen het. Hun bewijsmethode biedt ook een efficiënt algoritme voor het oplossen van een kubus die zich in de slechtste staat bevindt. De informatica houdt zich voornamelijk bezig met de vraag hoe lang het duurt voordat algoritmen worden uitgevoerd, maar computerwetenschappers meten het antwoord op deze vraag in termen van het aantal elementen waarop het algoritme inwerkt. De uitvoeringstijd van een algoritme dat bijvoorbeeld het grootste getal in een lijst vindt, is evenredig met de lengte van de lijst. Een “dom” algoritme voor het sorteren van de getallen in de lijst van klein naar groot, heeft echter een uitvoeringstijd die evenredig is met het kwadraat van de lengte van de lijst. Oplossing met een twist Erik Demaine, universitair hoofddocent informatica en engineering aan het MIT; zijn vader, Martin Demaine, een gastwetenschapper aan het MIT’s Computer Science and Artificial Intelligence Laboratory; afgestudeerde student Sarah Eisenstat; Anna Lubiw, die Demaines proefschriftadviseur was aan de Universiteit van Waterloo; en Tufts afgestudeerde student Andrew Winslow toonde aan dat het maximale aantal zetten dat nodig is om een Rubiks kubus met N vierkanten per rij op te lossen evenredig is met N2 / log N. “Dat dat het antwoord is, en niet N2, is verrassend”, zegt Demaine . De standaardmanier om een Rubiks kubus op te lossen, legt Demaine uit, is om een vierkant te vinden dat niet op zijn plaats is en het naar de juiste plaats te verplaatsen terwijl de rest van de kubus zo min mogelijk veranderd blijft. Die aanpak zal inderdaad een worst-case oplossing opleveren die evenredig is met N2. Demaine en zijn collega’s erkenden dat onder bepaalde omstandigheden een enkele reeks wendingen meerdere vierkanten naar de juiste plaats kon verplaatsen, waardoor het totale aantal bewegingen werd verminderd. Maar het was geen gemakkelijke taak om een manier te vinden om die omstandigheden wiskundig te beschrijven en te bepalen hoe vaak ze zouden voorkomen wanneer een kubus zich in de slechtste staat bevond. “In het eerste uur zagen we dat het minimaal N2 / log N moest zijn”, zegt Demaine. “Maar toen duurde het vele maanden voordat we konden bewijzen dat N2 / log N voldoende bewegingen waren.”
|
| https://breinbrekers.be |
