Mad-P音ゲー日記 2008年03月下旬

←前 2008年03月中旬 ↑index 2008年04月上旬次→

★ 2008/03/23 ニコ動→mp3一括再エンコscript

■ 投下してしまった。
　 http://www7.axfc.net/uploader/93/so/File_4845.zip.html
こんなことしてるから風邪が治らないんだorz

★ 2008/03/29 ルービックキューブは25手以内で解ける

■ Tomas Rokickiが3x3x3ルービックキューブを解くのに必要な手数の上限が 25手以下であることを示した。論文はこちら。テクノバーンの紹介記事や Drupalフォーラムの記事も参照。今回の証明概略はこんな感じ:

ルービックキューブ群Gとその部分群H=<U,D,R2,L2,F2,B2>を考え、Hとcoset空間G＼Hの性質を調べるのはこれまでと同じアプローチ。Hの要素は20G個あり、直交するようにcosetが2.2G個ある。20G×2.2G=約43Eでキューブの取り得る全状態数になる。
従来の解法(Reidの方法)は、Hが最大18手で到達可能、coset空間が最大12手で到達可能なので、18+12手以内でキューブの全状態が到達可能とするもの。
Rokickiの方法は、すべてのcosetにつき、coset内の全要素がある手数(例えば25手)以下で解けると証明することによって、全キューブ状態が25手以下で解けると示すもの。cosetは2.2G個あるが、対称性を考えると139M個だけ考えればよい。
cosetを頂点とするケーリーグラフを作成。あるcosetが20手以内で解けるなら、グラフ上で隣にあるcosetは21手以内で解けることを利用すれば、全数を解かなくてもよい。
あるcosetの必要手数上限を得るために、1要素を1ビットに対応させた20Gビットのビットマップを使って、breadth-firstサーチを実行(集合の各要素を解くのでなく全体を一気に解くのでset solverと称している)。上限付近は具体的なキューブをKociembaの解法で解いてみることによって、時間のかかるBFサーチを省力化。

Rokickiは139Mのcosetのうち約4000をグラフの構造から戦略的に選び、それぞれ19ないし20手以内で解けることを確認した。これによって全coset(の全要素)が最大25手で到達可能なことを示した。coset内の探索は「少なくとも○○手以内では解ける」というところでやめてしまうことで時間短縮しているそうだ。
　以前に話題になったKunkleの方法は、碁盤の目状の街で東西に何ブロック、南北に何ブロック、合計○○ブロックで到達可能とした上で、対角一番遠い地点までのななめの近道がないかさがす方法に例えることができる。Rokickiの方法は、首都圏の私鉄・地下鉄のようなネットワークにおいて、主要な乗り換え駅に待ち時間○○分以内の支店を配置することによって、どの駅からでも△△分以内にどこかの店舗でサービスを受けられる、という感じの戦略。
　この方法は、cosetの最大手数が短縮されることによってケーリーグラフ上のクリティカルパスが変わっていくため、それに応じて別のcosetを選んで解くことを繰り返せば、全体の上限をさらに短縮することが可能(支店を追加して最大の待ち時間を短縮できる)。現在24手という上限をめざして計算を続行中だそうだ。
　Rokickiは個人所有のCore2 QuadなPCで計算しているそうだが、set solverをMapReduce化してGoogleの計算機を使ったらどんどん上限が下がっていったりしてw

←前 2008年03月中旬 ↑index 2008年04月上旬次→