Neuer Algorithmus löst beliebig große Zauberwürfel

[Snitlev]

Erik Demaine, ein Informatiker am renommierten Forschungsinstitut MIT in Boston, ist es gelungen, einen Algorithmus zu entwickeln, mit dem Zauberwürfel einer beliebigen Größe mit einer vorhersagbaren Zahl an Zügen gelöst werden können. Das berichtete das Wissenschaftsmagazin 'New Scientist'.
Das Problem liegt darin, in dem Computer-Programm eine Strategie umzusetzen, die nicht auf dem Zufallsprinzip beruht. Einen herkömmlichen Zauberwürfel mit 3 x 3 x 3 Feldern kann man durchaus noch lösen, in dem man alle denkbaren Züge durchprobiert. Schon dies erfordert eine größere Rechenleistung. Allerdings geht dies nicht bei größeren Würfeln.

Quelle: Neuer Algorithmus lst beliebig groe Zauberwrfel - WinFuture.de (http://winfuture.de/news,64065.html)

Das ist aller ehrenwert, und mich überfordert schon 1 oder 2 Seiten des Zauberwürfels :tongue:

mfg

[v6ph1]

Neu?

In der Künstlichen Intelligenz gibt es viele dieser Funktionen, die genau das schaffen:
Man nimmt eine Heuristik als Hilfe, die einem etwa die Entfernung zum Ziel verrät. (Diese Funktion darf nicht überschätzen!)
Dann ändert man die Reihenfolge, indem die möglichen Operationen untersucht werden so, dass immer die Fälle, bei denen die erwartete Gesamt-Zahl der Operationen (also aktuelle + erwartete bis zum Ziel) am niedrigsten ist und ermittelt dann dort die Nachfolgeknoten.

Mit einer einfachen Formel, wieviele Züge welcher Zustand benötigt, könnte man das Problem extrem schnell lösen - mit einer Abschätzung geht es (je nach dieser) etwas schlechter.

Dieses Prinzip nennt sich A*-Suche.

Um wieviel jetzt diese neue Lösung besser ist, kann ich nicht beurteilen (dazu steht indem Artikel nix drin).
Möglicherweise ist es auch einfach eine neue Heuristik. - (n^2/log n) klingt zumindest gut.

Den Algorithmus würde ich zugerne mal sehen.

mfg
v6ph1

[LongbowArcher]

Neu?

In der Künstlichen Intelligenz gibt es viele dieser Funktionen, die genau das schaffen.

Es scheint sich von anderen Arten sehr zu unterscheiden, sonst würde ein Informatiker des berühmten MIT sicher nicht so einen Tarram darum machen und eines der bekanntesten Wissenschaftsmagazine der Welt darüber berichten.

So, ich bin dann mal durch null teilen (http://www.willis-witze.de/Chuck-Norris-Witze/Chuck-Norris-kann-durch-Null-teilen,witz-15112.html) und diese blöden Zauberwürfel gingen mir schon immer auf den Keks :D

[ghostfucker]

So, ich bin dann mal durch null teilen (http://www.willis-witze.de/Chuck-Norris-Witze/Chuck-Norris-kann-durch-Null-teilen,witz-15112.html)
nichts besonderes, kann ich auch: 1/0.0

[v6ph1]

Es scheint sich von anderen Arten sehr zu unterscheiden, sonst würde ein Informatiker des berühmten MIT sicher nicht so einen Tarram darum machen und eines der bekanntesten Wissenschaftsmagazine der Welt darüber berichten.
Deswegen hätte ich ja gerne mal den Algorithmus gesehen. - Heuristische Ansätze leisten prinzipiell ähnliches.
Das hat auch nix mit Zufall zu tun und ist ebenso schnell.


nichts besonderes, kann ich auch: 1/0.0
= 0x7F80 0000
oder
= 0x7FF0 0000 0000 0000

mfg
v6ph1