ルービックキューブと群論 について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ 0321604 大石 貴弘 前回までの成果 • 前回までの成果 – 幅優先探索の2×2を解くプログラム – ルービックキューブの組み合わせ配置の内訳に ついて 読んだ本について • メタマジック･ゲーム – ダグラス･R･ホフスタッター 著 – 竹内郁雄・斉藤康己･片桐恭弘 訳 – 白揚社 • 14章 • 15章 ルービックキューブと群論 • ルービックキューブは群 – 群である条件 – 結合法則 • 計算の順序を変えても同じ結果がでる場合、それを満 たす。ルーブックキューブの並びを計算される要素、 計算を回転させる行為 – 単位元の存在 • ルービックキューブの並びをaとした時にa * e = e * a = aが成り立つために eという要素があること • ルービックキューブの場合は『何もしない』が単位元 – 逆元の存在 • 逆の操作。右回しに対する左回し ルービックキューブと群論 • ルービックキューブの最小手数について – 置換群で表現(ブロックを回転させる事の集まり) • 各方向に2方向回転することが可能 • ２×3=6のどこかを移動 – 各要素について、群作用で移動できる要素と繋いで グラフを作成（ケーリーグラフ） – そのグラフの直径（元と問題の面の間の距離）が最短 手数になる。 – 現在の所、計算量が多く不可能 ルービックキューブと群論 • また、ルービックキューブは、6個の回転で表され るので 6^30=221,073,919,720,733,357,899,776 • これはルービックキューブのすべての組合せ 43,252,003,274,489,856,000通りよりも大 • どんな配置も最短解は30手以内 ルービックキューブと群論 • ルービックキューブを解くための共役の利用 – 解けている所から解けていない所を解く • ルービックキューブの面の隣同士を入替える方法が判 っている（解き方が判明） • 離れた所だけを入替えるには、入替えたい所を隣に 移動…A • 隣同士を入れ替える • Aと逆の移動をして以前の状態に逆行 今後の課題 • 知識の不足 – 数学セミナー – 雑誌 1981年8月号 – 日本評論社 刊 の借用予定 次回までの成果誓約 • ルービックキューブについての更なる知識 習得 • ２×2を解くプログラムの制作
© Copyright 2024 ExpyDoc
