ルービックキューブを解くロボットを作ろう！2 アルゴリズム編

この記事はなに？
この記事は連載しているルービックキューブを解くロボットを作ろう！という記事集の一部です。全貌はこちら
1. 概要編
2. アルゴリズム編(本記事)
3. ソフトウェア編(未公開)
4. ハードウェア編(未公開)
また、この記事と同じ内容で動画を作成しました。
この記事集に関する動画集はこちらです。
今回の記事の内容
今回は2x2x2ルービックキューブを解くための、(ロボットにとっての)最短手順を出力するプログラムのアルゴリズムについて解説します。アルゴリズムは「幅優先探索」と「IDA*」を紹介します。と、その前に全探索の考え方について軽く触れましょう。
今回考える「全探索」とは？
全探索は文字通り、全部のパターンを探索する手法です。2x2x2のルービックキューブであれば、ある状態から{U, U’, U2, F, F’, F2, R, R’, R2}を回す場合すべてをチェックして、揃ってなければ前にチェックしたすべてのパターンに対してまた{U, U’, U2, F, F’, F2, R, R’, R2}のすべてを回してチェックして…というような探索手法です(厳密には2手順目以降探索するのは各6手順ずつですが、その話はこのあとします)。ここで出てきたUとかFとかRは回転記号といいます。詳しくは概要編をご覧ください。
さて、ここでちょっと図を描いてみましょう。
このように、キューブの状態を丸(ノード)、その状態からなにか手を回すことを棒(辺)で表すと、ある状態から探索可能な手を全部回すことを繰り返していくこととこの木のような図が対応します。図ではサボりましたが、2x2x2の場合は各状態に対して、
最初の手は{U, U’, U2, F, F’, F2, R, R’, R2}の9手
2手目以降は、前の手が{X, X’, X2}のどれかだった場合は{U, U’, U2, F, F’, F2, R, R’, R2}{X, X’, X2}の6手(は差集合の記号)
これだけの手が回せるので、最初のノード(根)からは9本の辺が、最初以外のノードからはそれぞれ6本ずつ辺が生えていることになります。
なお、2手目以降に探索すべき手数が減るのは、例えばX X’と回したら何も回していないのと同じ、X Xと回せばX2、X X2と回せばX’と同じ、というよ
情報元サイト：「Qiita」
[ オリジナルサイトで見る ]