Eine neue Forschungsarbeit eröffnet die Beziehung zwischen der Anzahl der Quadrate in Rubiks-Cube-ähnlichen Rätseln und der maximalen Anzahl der Schritte, um sie zu lösen.
Im letzten August, 30 Jahre nach dem ersten Erscheinen des Rubiks Cube (hierzulande auch Zauberwürfel genannt), bewies ein Team internationaler Wissenschaftler, dass ein Zauberwürfel in nicht mehr als 20 Schritten gelöst werden kann, egal wie ungeordnet er ist. Obwohl die Forscher einige clevere Tricks benutzten, um es zu vermeiden, alle 43 Trillionen mögliche Anfangspositionen zu berechnen, basierte ihr Beweis dennoch auf dem Äquivalent von 35 Jahren Rechenzeit eines guten modernen Computers.
Unglücklicherweise übersteigt die genaue Überprüfung größerer Zauberwürfel – mit sagen wir vier oder fünf Quadraten in einer Reihe anstelle von dreien – die Rechenkapazität aller Computer auf der Welt bei weitem. Aber in einer Abhandlung, die im September auf dem 19. Annual European Symposium on Algorithms präsentiert wird, eröffnen Forscher des MIT, der University of Waterloo und der Tufts University die mathematische Beziehung zwischen der Anzahl der Quadrate in einem Zauberwürfel und der maximalen Anzahl der zur Lösung notwendigen Schritte. Ihre Beweismethode liefert auch einen effizienten Algorithmus zur Lösung eines Zauberwürfels, der sich im denkbar kompliziertesten Zustand befindet.
Computerwissenschaften beschäftigen sich hauptsächlich mit der Frage, wie lange ein Algorithmus zur Ausführung braucht, aber Wissenschaftler messen die Antwort auf diese Frage in Bezug auf die Anzahl der Elemente, die der Algorithmus bearbeitet. Die Ausführungszeit eines Algorithmus, der die größte Zahl in einer Liste findet, ist beispielsweise proportional zur Länge der Liste. Ein „dummer“ Algorithmus zum Sortieren der Zahlen in einer Liste von der kleinsten zur größten wird allerdings eine Ausführungszeit aufweisen, die proportional zum Quadrat der Listenlänge ist.
Lösung mit einer Drehung
Erik Demaine, ein Dozent für Computerwissenschaften und Ingenieurswesen am Massachusetts Institute of Technology (MIT), sein Vater Martin Demaine (Gastwissenschaftler am Computer Science and Artificial Intelligence Laboratory des MIT), die Studentin Sarah Eisenstat, Demaines Doktormutter Anna Lubiw von der University of Waterloo und der Student Andrew Winslow von der Tufts University waren an der Arbeit beteiligt. Sie zeigten, dass die maximale Anzahl der zur Lösung eines Zauberwürfels mit N Quadraten pro Reihe benötigten Schritte proportional zu N2/log N ist. „Es ist überraschend, dass dies die Antwort ist und nicht N2„, sagte Demaine.
Die Standardmethode zur Lösung eines Zauberwürfels sei es, ein Quadrat zu finden, welches sich nicht in der richtigen Position befindet, und es an den korrekten Platz zu bewegen, während der Rest des Zauberwürfels so wenig wie möglich verändert wird, erklärte Demaine. Dieser Ansatz wird schlimmstenfalls tatsächlich zu einer Lösung führen, die proportional zu N2 ist. Demaine und seine Kollegen erkannten, dass eine einzige Sequenz aus Verdrehungen unter gewissen Umständen mehrere Quadrate an ihre korrekten Positionen bewegt, was die Gesamtanzahl der Schritte heruntersetzt.
Aber es war keine leichte Aufgabe, einen Weg zu finden, diese Umstände mathematisch zu beschreiben und zu bestimmen, wie oft sie auftreten, wenn ein Zauberwürfel in seinem kompliziertesten Zustand war. „In der ersten Stunde sahen wir, dass es mindestens N2/log N sein musste“, sagte Demaine. „Aber das war viele Monate bevor wir beweisen konnten, dass N2/log N genug Schritte waren.“
Weil ihre Analysemethode den Fall beschreibt, wonach mehrere Quadrate gleichzeitig an ihre richtigen Positionen bewegt werden können, liefert sie auch eine Möglichkeit, diese Fälle zu erkennen und damit einen Algorithmus, um einen ungeordneten Zauberwürfel zu lösen. Der Algorithmus ist nicht optimal: Er benötigt immer ein paar Extraschritte. Aber wenn die Anzahl der Quadrate pro Seitenfläche ansteigt, verlieren diese Schritte an Bedeutung.
Ein Konfigurationsproblem
Der Zauberwürfel ist ein Beispiel für etwas, das man als Konfigurationsproblem bezeichnet. Das bekannteste Beispiel dafür ist es, den effizientesten Weg zu finden, um Kisten in einem Lager zu reorganisieren. Demaine sagt, es sei möglich, dass die von ihm und seinen Kollegen zur Untersuchung des Zauberwürfels entwickelten Werkzeuge auf solche Probleme angewandt werden könnten.
Aber Demaine ist auch ein Verteidiger von Forschungsprojekten, die keine offensichtlichen Anwendungen haben. „Mein Leben wurde bestimmt durch die Lösung von Problemen, die ich als Spaß betrachte“, sagt er. „Es ist für den Moment immer schwierig zu sagen, was wichtig werden wird. Die Untersuchung von Primzahlen war nur eine Freizeitaktivität. Hunderte Jahre lang gab es keinen praktischen Nutzen dafür, bis die Kryptografie Einzug hielt.“
Er ergänzt: „Die Ästhetik ist es, nicht nur Dinge zu untersuchen, die Spaß machen, sondern auch Probleme, die einfach sind. Ich denke, je einfacher das mathematische Problem, desto wahrscheinlicher wird es in einer wichtigen praktischen Anwendung in der Zukunft eingesetzt. Und der Zauberwürfel ist eine Art Inbegriff der Einfachheit.“
„Erik ist immer sehr interessiert daran, die Reichweite populärer Mathematik zu vergrößern“, sagt Marc van Kreveld, ein Dozent am Department of Information and Computing Sciences der Utrecht University in den Niederlanden, der in seiner Freizeit Rätsel entwickelt. „Er versucht wirklich zu vermitteln, dass Mathematik nicht nur ein langweiliger Forschungsbereich ist, sondern Spaß macht und man eine Menge damit anfangen kann, und sie ist schön.“
„Erik ist eine sehr brillante Person“, fügt van Kreveld hinzu. „Er ist schon sehr erfolgreich in seiner komplexen Forschung. Aber das Popularisieren ist auch notwendig, denke ich. Man sollte die Bedeutung unterschätzen, Studenten zum Lernen anzuregen.“
Quelle: http://web.mit.edu/newsoffice/2011/rubiks-cube-0629.html
(THK)
Antworten