任意のサイズのルービックキューブを解くアルゴリズム
ややこしい問題が解けたとき「よし、終わった」と考える人もいれば、「これを一般化するとどうなるだろう」と考える人もいます。
MITでコンピュータサイエンスを担当するErik Demaine教授はどうやら後者。教授らのチームは、3x3x3サイズが一般的な
ルービックキューブだけでなく、NxNxNのいかなる大きさの立方ルービックキューブ体に対しても適用できる効率的な解法
アルゴリズムを開発しました。
3x3x3サイズの解法は、Googleの力を借りて全通り分析という力技でした。しかしこの方法では、キューブのサイズが大きく
なると考えられる組み合わせは飛躍的に多くなり、すぐに太刀打ちできなくなります。そこでDemaine教授らは、キューブの
うち一点を、なるべく他を変化させないようにしたまま、目的の場所まで動かす方法を利用し、この動きを利用して他の点も
同時に目的地へ進めていくというアルゴリズムを考案しました。サイズNのルービックキューブを対象とした場合、一点一点を
目的地へ動かしていく場合はN2の計算量が必要ですが、一度に複数の点を動かしていくことで、N2/logNまで計算量を削減
することができます。
さて、ルービックキューブ問題はこれで終わったのでしょうか？ そうではない、というのが教授の答えです。いわく今後も、
実際にNサイズのルービックキューブを解くのに最小で何手が必要なのか、あるいは完全にバラバラではないルービックキューブ
をどのように解くのか、といった問題が残されているとのこと。なんであれ、まだまだ愛され玩具としての地位は安泰のようです。
http://japanese.engadget.com/2011/07/04/rubik/
http://www.newscientist.com/article/dn20636-rubiks-cubes-of-any-size-can-now-be-solved.html
http://www.blogcdn.com/www.engadget.com/media/2011/07/rubiks-cube.jpg
|
|
|
2 ：名無しさん＠涙目です。(関西地方)：2011/07/04(月) 20:46:09.17 ID:Dt7wCIMo0
花札面白いよね
3 ：名無しさん＠涙目です。(チベット自治区)：2011/07/04(月) 20:46:25.92 ID:pT8N2jE/0
／::::::::::::::::::::::::::＼
＿i:::::::-‐―――-::::i＿
／／.:::i::::i::::i::::i::::i::::i::::i:::.ヽヽ.
/:::/..::/ ヽ::ヽ
/::/::::/ ＼ ／ l::::i::i
|::::i:::l ＜●> <●＞ l::::i:::|
|::::i:::l △ l::l::::|
￣しヽ 'ｰ=三-' /ソ￣
＼ . /
＼ /
＼＿＿＿/
＿i:::::::-‐―――-::::i＿
／／.:::i::::i::::i::::i::::i::::i::::i:::.ヽヽ.
/:::/..::/ ヽ::ヽ
/::/::::/ ＼ ／ l::::i::i
|::::i:::l ＜●> <●＞ l::::i:::|
|::::i:::l △ l::l::::|
￣しヽ 'ｰ=三-' /ソ￣
＼ . /
＼ /
＼＿＿＿/
4 ：名無しさん＠涙目です。(神奈川県)：2011/07/04(月) 20:46:29.25 ID:qiKK/4sx0
理系はこんなくだらないことばっかやってるから予算を削られる。
やっぱ文系すごいわ。
やっぱ文系すごいわ。
5 ：名無しさん＠涙目です。(熊本県)：2011/07/04(月) 20:46:44.09 ID:G+NSp8si0
忍者の皆さんとアルゴリズム行進
6 ：名無しさん＠涙目です。(岡山県)：2011/07/04(月) 20:47:32.18 ID:iZeMQYDI0
仮想でだろ
7 ：名無しさん＠涙目です。(東京都)：2011/07/04(月) 20:48:26.89 ID:a64rpkP80
8 ：名無しさん＠涙目です。(catv?)：2011/07/04(月) 20:51:01.35 ID:X410HCjP0
俺も１×１なら解けるんだが
9 ：名無しさん＠涙目です。(茨城県)：2011/07/04(月) 20:53:13.56 ID:a3ENjvnH0
>>3
ああアゴってことか
ああアゴってことか
10 ：名無しさん＠涙目です。(catv?)：2011/07/04(月) 20:54:51.18 ID:YqxT2vRX0
力でバラせばいいよね
11 ：名無しさん＠涙目です。(チベット自治区)：2011/07/04(月) 20:55:35.11 ID:37SdT98Q0
Googleで全パターン分析とか文系でも出来るな
12 ：名無しさん＠涙目です。(関東)：2011/07/04(月) 21:09:23.19 ID:GU+yz05oO
ダイナミックプログラミングってのとかで解けないの？
13 ：名無しさん＠涙目です。(神奈川県)：2011/07/04(月) 21:11:36.36 ID:CsyOP+Qu0
キューブを動作させると当然他のピースも変わっちゃうから色々難しい
14 ：名無しさん＠涙目です。(長屋)：2011/07/04(月) 21:17:05.26 ID:9qcV1kLw0
ラプラスの魔スレ
15 ：名無しさん＠涙目です。(新潟・東北)：2011/07/04(月) 21:58:43.26 ID:EUXr9dnjO
オリラジの髭がなんか方程式やってたな
16 ：名無しさん＠涙目です。(三重県)：2011/07/04(月) 22:19:42.15 ID:euXqcMuo0
2x2x2も自分で解こうとすると結構難しいよ
17 ： 忍法帖【Lv=14,xxxPT】 (鳥取県)：2011/07/04(月) 22:31:44.87 ID:l/bEh+k10
http://tribox.cart.fc2.com/ca94/278/p-r94-s/
2色のやつが簡単かと思ったら、ちゃんと解法知らないとハマることに気がついた。
色が一緒だから別のとこに行っててもわかりにくいんだよな。
2色のやつが簡単かと思ったら、ちゃんと解法知らないとハマることに気がついた。
色が一緒だから別のとこに行っててもわかりにくいんだよな。
18 ：名無しさん＠涙目です。(三重県)：
>>17
1色で形が変わるやつとか色々あるよね
1色で形が変わるやつとか色々あるよね