Sponsored Contents

algorithmの最新記事

Image credit:
Save

任意のサイズのルービックキューブを解くアルゴリズム

Haruka Ueda
2011年7月4日, 午後01:15 in Algorithm
73シェア
0
9
0
64

連載

注目記事


ややこしい問題が解けたとき「よし、終わった」と考える人もいれば、「これを一般化するとどうなるだろう」と考える人もいます。MITでコンピュータサイエンスを担当するErik Demaine教授はどうやら後者。教授らのチームは、3x3x3サイズが一般的なルービックキューブだけでなく、NxNxNのいかなる大きさの立方ルービックキューブ体に対しても適用できる効率的な解法アルゴリズムを開発しました。

3x3x3サイズの解法は、Googleの力を借りて全通り分析という力技でした。しかしこの方法では、キューブのサイズが大きくなると考えられる組み合わせは飛躍的に多くなり、すぐに太刀打ちできなくなります。そこでDemaine教授らは、キューブのうち一点を、なるべく他を変化させないようにしたまま、目的の場所まで動かす方法を利用し、この動きを利用して他の点も同時に目的地へ進めていくというアルゴリズムを考案しました。サイズNのルービックキューブを対象とした場合、一点一点を目的地へ動かしていく場合はN2の計算量が必要ですが、一度に複数の点を動かしていくことで、N2/logNまで計算量を削減することができます。

さて、ルービックキューブ問題はこれで終わったのでしょうか? そうではない、というのが教授の答えです。いわく今後も、実際にNサイズのルービックキューブを解くのに最小で何手が必要なのか、あるいは完全にバラバラではないルービックキューブをどのように解くのか、といった問題が残されているとのこと。なんであれ、まだまだ愛され玩具としての地位は安泰のようです。


広告掲載についてのお問い合わせはad-sales@oath.com までお知らせください。各種データなどはこちらのメディアガイドをあわせてご覧ください。

73シェア
0
9
0
64

Sponsored Contents