ルービックキューブアルゴリズムが23の動きに減少

ルービックキューブを収集するために必要な移動の最大数は23に減少します。 この数学的問題はスタンフォード大学の卒業生であるトマス・ロキッキによって解決されました。 彼が開発した戦略はコンピューターステーションで開始され、計算の正確性が確認されました。



Rokickiは独自のアプローチを採用しました。 個々の動きを分析する代わりに、彼は立方体の形状を考慮に入れて、立方体を一連の状態に分割しました。 合計で、それぞれ200億個の要素を持つ20億セット(州)が取得されました。 この概念では、移動は「バインドされた状態」(コセット)のペアと見なされます。 Rokickiは、多数の条件が実際に相互に繰り返されるため、無視できることを証明しました。 しかし、最適化後でも、モデル全体を計算するには非常に大きな計算リソースが必要です。 前の記録(25移動)は、プロセッサとQ6600(1.6 GHz)および8 GBのRAMを搭載したマシンで1,500時間を必要としました。 現在、Rokickiは有名なSony Pictures Imageworks映画スタジオのより強力なクラスターで7.8コア年のコンピューティングを借りています(計算は、スパイダーマン3と漫画Catch the Waveの特殊効果が計算された同じマシンでダウンタイム中に実行されました): 20万件以上の関連条件を分析しました。



Rokickiの理論的研究は、最適なソリューションは22の動きまたは21の動きでさえあり得ることを示唆していますが、これを検証するには追加の計算リソースが必要です。 したがって、22の移動でソリューションを証明するには、約5〜7倍のマシン時間がかかります。100万から150万の接続状態を計算する必要があります。



21番手での解決策の証明はこれまでのところ素晴らしく見えますが、この問題を解決するためにキャリアを捧げてきた理論数学者の計算と一致しています。 彼らは、動きの最小数が3番目の10の最初のどこかにあることを示唆しています。



All Articles