アカウント名:
パスワード:
到達した状態を管理するのにもメモリが大量に必要になります。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
ナニゲにアレゲなのは、ナニゲなアレゲ -- アレゲ研究家
シミュレーションでは証明にならない (スコア:0)
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
Re:シミュレーションでは証明にならない (スコア:2, すばらしい洞察)
Re:シミュレーションでは証明にならない (スコア:1, 興味深い)
到達した状態を管理するのにもメモリが大量に必要になります。
逆に不揃いから揃える方向ならば、6面が揃ったというチェックは簡単に実装できます。
また初期状態の全パターンは再帰を使えば簡単に生成できるのでメモリコストは少しですみます。
その各状態から26手まで総当りですが、26手を総当りで試して、26手以内に6面揃えばその初期パターンは26手以内であると確認されるので打ち切れます。
これも再帰を使えば26手までは十分試せるでしょう。
これである初期状態から26手総当りを行っても6面が揃わなければ26手以内では揃わない初期状態があると証明できます。
#どっちにしても計算量は膨大ですね
Re:シミュレーションでは証明にならない (スコア:1)
ルービックキューブの状態を一意で密なハッシュ値であるidに変換できれば
（つまり全ての状態に0から始まる一意なIDが付けられれば）、解を根とする木構造を深さ26までの
深さ優先探索で総当りしながら、たどり着いたノードの状態のハッシュをメモリにキャッシュして、
適当にたまったところでHDDのidビット目に1を上書していけば、最後に全ての状態に対してビットが
立っているか確認するだけでいいので。
ってなわけで問題は結局、
って部分に集約されるのではないかと。
全ての状態に対して到達しているかしていないかを1bitで表したとしても、約5エクサバイト
（43,252,003,274,489,856,000bit）の補助記憶領域が必要な訳で、メモリほど高速である
必要がないのでHDDでOKって事を考えても現実的かは微妙な容量ですね。
ただ、不揃いから揃える場合の初期状態数（43,252,003,274,489,856,000）と、それぞれそこから
下手すると深さが26の木を辿らなきゃいけないって事を考えれば（解からなら1回辿るだけでOK）、
解から辿った方が現実的なやり方だと思います。