22.04.2014, 22:39
Ich nehme mal an, dass du die optimale (kürzeste) Lösung zu einem Würfel suchst. Da kann ich jetzt schon sagen, dass dir das nicht gelingen wird. Nicht böse gemeint, aber der Verzweigungsfaktor ist einfach zu groß. Ich habe noch nie ein Programm gesehen, dass mir zu einem zufälligen Würfel die optimale Lösung sagen konnte. Zumindest wenn die optimale Lösung 19 oder 20 Züge lang ist.
Übrigens, der Faktor 12 ist falsch. Im einfachsten Fall hast du einen Faktor von 15. Wenn du dann doch Drehungen ignorierst, die sich kürzen (z.B. R L R = R2 L) oder die doppelt vorkommen (R L = L R), kommst du nur auf einen Faktor von 13.35 (Ganz genau gesagt 6 + 3 * Wurzel(6)). Für die Tiefe 10 hättest du dann schon 269.405.157.600 Knoten. Viel zu viel für einen Rechner. Zumindest 20 wird er nicht erreichen, denn dort gibt's schon 48.386.092.616.942.490.160.128 Knoten.
Trotzdem gibt es einige Techniken, wie man einigermaßen gute Ergebnisse bekommt. Ich habe mich selbst im letzten Monat wieder ein mal damit beschäftigt, und ich kann zum Teil 15 Züge-Lösungen in ca. 1 Minute optimal ermitteln. Wenn die Steine etwas unpassend liegen, dann komme ich allerdings höchstens bis 13 Züge.
Eine gute Seite, mit vielen dieser Techniken, ist http://www.jaapsch.net/puzzles/compcube.htm.
Eine Alternative ist, den Würfel nicht optimal zu lösen, sondern nur pseudo-optimal. Mit Kociemba's Algorithmus kann man jeden Würfel in ca. 21-23 Züge im Bruchteil einer Sekunde lösen. Diese Lösung ist im allgemeinen nicht die kürzeste, aber eine gute Näherung. Den Algorithmus findest du ebenfalls unter der oberen Seite oder unter Sébastien's Link.
Übrigens, der Faktor 12 ist falsch. Im einfachsten Fall hast du einen Faktor von 15. Wenn du dann doch Drehungen ignorierst, die sich kürzen (z.B. R L R = R2 L) oder die doppelt vorkommen (R L = L R), kommst du nur auf einen Faktor von 13.35 (Ganz genau gesagt 6 + 3 * Wurzel(6)). Für die Tiefe 10 hättest du dann schon 269.405.157.600 Knoten. Viel zu viel für einen Rechner. Zumindest 20 wird er nicht erreichen, denn dort gibt's schon 48.386.092.616.942.490.160.128 Knoten.
Trotzdem gibt es einige Techniken, wie man einigermaßen gute Ergebnisse bekommt. Ich habe mich selbst im letzten Monat wieder ein mal damit beschäftigt, und ich kann zum Teil 15 Züge-Lösungen in ca. 1 Minute optimal ermitteln. Wenn die Steine etwas unpassend liegen, dann komme ich allerdings höchstens bis 13 Züge.
Eine gute Seite, mit vielen dieser Techniken, ist http://www.jaapsch.net/puzzles/compcube.htm.
Eine Alternative ist, den Würfel nicht optimal zu lösen, sondern nur pseudo-optimal. Mit Kociemba's Algorithmus kann man jeden Würfel in ca. 21-23 Züge im Bruchteil einer Sekunde lösen. Diese Lösung ist im allgemeinen nicht die kürzeste, aber eine gute Näherung. Den Algorithmus findest du ebenfalls unter der oberen Seite oder unter Sébastien's Link.