表1.回転と捻り量の変化の関係(全81通りの一部)

Slides:



Advertisements
Similar presentations
1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
Advertisements

模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
コンピュータと情報 第10回 Excel を使ってみる. Excel の起動 ① 「スタート」ボタンをク リック ② すべてのプログラムにマ ウスカーソルをあわせる ③ 「 Microsoft Office 」 → 「 Microsoft Excel 2003 」 にマウスをあわせて,ク リック ④.
0章 数学基礎.
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
ゲーム理論・ゲーム理論Ⅰ(第2回) 第2章 戦略形ゲームの基礎
第12回 順序回路の解析方法 瀬戸 順序回路から,以下を導き、解析を行えるようにする タイムチャート 状態遷移関数・出力関数 状態遷移表
セキュアネットワーク符号化構成法に関する研究
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
豊中高校土曜講座「数学セミナー2003」 プラトン多面体の数学 なぜ正多面体は5種類しかないのか 大阪府立豊中高等学校 深川 久.
ラベル付き区間グラフを列挙するBDDとその応用
パスカルの三角形  ~3次元への拡張~ 立命館高校 2年 池内 正剛.
デジタルポートフォリオ作成支援ツール PictFolio 使用マニュアル
On the Enumeration of Colored Trees
4.3 連立1次方程式   Ax = b   (23) と書くことができる。
群論とルービックキューブ 白柳研究室  水野貴裕.
ネットワークシステムⅠ ネットワークシステム 第2回
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
Extremal Combinatorics 14.1 ~ 14.2
An Algorithm for Enumerating Maximal Matchings of a Graph
一般化マクマホン立方体パズルの 問題例生成
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
Bias2 - Variance - Noise 分解
香川大学工学部 富永浩之 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之
15パズルの解法について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ  大石 貴弘.
IM、プレゼンス、連絡先 IM 要求を受け入れる Lync 2013 クイック リファレンス プレゼンスを設定または変更する ユーザーの検索
 Combinations(2)        古川 勇輔.
香川大学工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学工学部 富永浩之
数独パズルの難易度判定 ~解法ロジックを用いた数値化の提案~
イメージポスターを作ろう! 高校2年 情報選択②.
Mathcad と Excel の比較 PTC ジャパン(株) 部署名 年月日.
10.通信路符号化手法2 (誤り検出と誤り訂正符号)
電気回路学Ⅱ エネルギーインテリジェンスコース 5セメ 山田 博仁.
クリッカブル三次元地図の制作 情報工学科 服部 真和 (指導教員: 金子 教授) 研究背景 目的
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
二分探索木によるサーチ.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
情報処理A 第?回 Excelを使ってみる.
高速剰余算アルゴリズムとそのハードウェア実装についての研究
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
OpenGLライブラリを用いた3次元フラクタルの描画
第5章 特徴の評価とベイズ誤り確率 5.5 ベイズ誤り確率の推定法 [1] 誤識別率の偏りと分散 [2] ベイズ誤り確率の上限および下限
情報検索(6) メディア検索の仕組み 教員 岩村 雅一
No.3 No3.電子筐体製品 コメント 使用機能 一覧 従来課題 課題解決策 3D IGESを利用した IGES 「IGES読込み設定」
デジタル画像とC言語.
電気回路学Ⅱ コミュニケーションネットワークコース 5セメ 山田 博仁.
第1日目第3時限の学習目標 2変量データを手にした時の分布の特徴の記述方法(前回からの続き)について学ぶ。 基本的な2変量統計量ー1
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
数独の解生成と 解に対する番号付け 理学部 情報科学科 渡辺研究室 戸神星也.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
不確実データベースからの 負の相関ルールの抽出
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
問題作成、解説担当:中島 副担当:坪坂、松本
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
川崎浩司:沿岸域工学,コロナ社 第4章(pp.58-68)
情報基礎Ⅱ (第1回) 月曜4限 担当:北川 晃.
東邦大学理学部情報科学科 白柳研究室 五味渕真也
度数分布表における平均・分散 (第1章 記述統計の復習 補足)
EastNipporiFactory(東日暮里工房)
電気回路学Ⅱ 通信工学コース 5セメ 山田 博仁.
電気回路学Ⅱ 通信工学コース 5セメ 山田 博仁.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
香川大学工学部 富永浩之 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之
香川大学創造工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学創造工学部 富永浩之
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
エクセル(3)の目次 参照演算子と演算子 参照セルの表示法 セルの参照方法 エラーについて シグマ(Σ)関数 条件付書式 問題(1)
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
ペンシルパズル「一本線」のヒント数の扱いに関する解析
Presentation transcript:

表1.回転と捻り量の変化の関係(全81通りの一部) ルービックキューブの探索プログラム 北海道大学理学部数学科4年 大島 知樹 指導教員 秋山 正和(電子科学研究所) 4.効率的な探索手法の必要性 1.研究動機 4.数値計算結果  ルービックキューブは,ハンガリーの建築学者であるエルノー・ルービックが1974年に考案したパズルである(図1).3×3×3個の立方体からなるように見えるこの立方体は,各列を独立して回転させることができる.このパズルは、その回転を用いて6色に塗り分けられた面をバラバラにし,それを回転により再び揃えて遊ぶものである.パズルとしての操作は各列の回転のみであり,一見簡単そうに見えるが,各回転は様々な面に影響するため,見た目に反して難易度の高いパズルである.  今後,ルービックキューブは一般のサイズのものを考える.ルービックキューブの回転によって得られるパターン数は1,2,3面体の位置と2,3面体の向き,及び前述の3面体の捻り量の条件に加えて,2面体の捻り量の条件がある.さらに奇数サイズのものは,中心部分の2面体(図11)と3面体の相互の位置関係の条件がある.これらを考慮すると,ルービックキューブの回転によって得られるパターン数は(4.1)のようになる. (1) (3) (4) (2) (1) 2×2×2のパターン数 (2) 3×3×3のパターン数 (3) 2面体の配置のパターン数 (4) 1面体の配置のパターン数 図1.ルービックキューブ  ルービックキューブはパズルとしてのみならず,数学的対象としても興味深いものとして知られている.ルービックキューブの小面の状態を元とする集合を考え,回転操作をその集合上の演算とみなすと,その集合と演算の組は群をなすことが知られている(*).例えば,ルービックキューブにある複数の回転操作を施したあとに,その逆の操作を行うとルービックキューブは元に戻る.これはちょうど,群における元とその逆元の存在に対応している(式1). (4.1) 図11.中心部分の2面体 サイズ パターン数 1秒に1京パターンを 発見できるスパコンの計算時間 2×2×2 3.67×106 1秒未満 3×3×3 4.32×1019 約1時間12分 4×4×4 7.40×1045 約234垓年 5×5×5 2.82×1074 約894極年  (4.1)より,2×2×2から5×5×5サイズのパターン数を求めると,表2のようになる.仮に,全探索で1秒間に1京(1.00×1016)パターンの速さで解法を見つけられるスパコンがあったとしても,ルービックキューブのサイズが大きくなると,現実的な時間で解法を見つけることは不可能になる.このため,ルービックキューブの解法探索では,効率的な探索手法が必要不可欠となる. 式1.群の定義  ルービックキューブは,その明快さから子供から大人まで広く愛されているパズルであるが,そのようなものに数学の群構造が含まれていることに私は純粋な興味を持った.また,ルービックキューブの群構造のみならず,難易度の高いこのパズルを数学的手法を用いて解決することにも興味を持った. 表2.回転によるパターン数と計算時間 *:群論の味わい 置換群で解き明かすルービックキューブと15パズル(David Joyner 著,川辺治之 訳,共立出版,2010年) 5.探索プログラム 2.ルービックキューブと群構造  ルービックキューブの解法を探索するプログラムを制作した(図12,図13).解法の探索手法は表3の通りである.このプログラムに,入力された面情報が回転によって完成状態にできるものであるか,2,3面体の捻り量や位置を元に判定する機能を実装した.  今後,ルービックキューブは世界標準配色のものを考える(図2).橙の1面体を含む面を右面(Right)と定義する.同様に,赤,黄,白,青,緑の1面体を含む面を,左面(Left),前面(Front),後面(Back),上面(Up),下面(Down)と定義する.  右面を正面に見て,右面を右に90°回転する操作をRと定義する.また,180°回転する操作,270°回転する操作をそれぞれ,R2,R'と書く.他面の回転も同様に定義する.なお,中心列の回転は定義しない.これは,中心列の回転は,その中心列以外の2列の回転により実現できるためである.  各小面に図2のように番号を付ける.すると,Rによる小面の移動は,置換群の表記を用いて(2.1)のように記述できる.  また,OpenCVという画像処理ライブラリを用いて,ウェブカメラを使って面情報の入力ができる機能を実装した(図14). 図2.世界標準配色の展開図と 各面の番号付け 図12.探索プログラムによる解法表示 図13.入力画面 図14.カメラ機能 (2.1) 他の回転についても,同様にして置換群の表記を用いて記述できる.それらをそれぞれ,  , , , ,  とする.  R2はRを2回施して得られる回転なので,置換群の表記を用いると  となる.同様にR'はRを3回施して得られる回転なので,  となる.このことより,ルービックキューブの回転操作による置換群  は単純に(2.2)のようになる.以後  をルービック群と呼ぶ. 図 説明 Ⅰ.回転の全探索により,左図のような"6個"か"8個"のブロックを見つける. Ⅱ.Ⅰで見つけたブロックを起点に,回転の全探索により,左図のような"12個"のブロックを見つける.規定手数以内に見つからなかった場合,Ⅰに戻る. Ⅲ.Ⅱで見つけたブロックを起点に,一部回転を制限した回転の全探索により,左図のような"2層揃い"のブロックを見つける.規定手数以内に見つからなかった場合,Ⅱに戻る. Ⅳ.OLL(Orientation of the Last Layer)と呼ばれる回転処理を行い,"2層揃い+1面揃い"の形を作る(左図).その後,PLL(Permutation of the Last Layer)と呼ばれる回転処理を行い,完成形(右図)を作る. (2.2)  ルービック群は,明らかに54次置換群の部分群である.このように置換群との関連付けをすることにより,ルービックキューブを置換群の部分群として扱うことができる. 3.回転により得られないパターン  ルービックキューブを構成する小立方体のうち,3面が表に面しているものを3面体と定義する(図3).同様に2面体,1面体を定義する(図4,図5).ルービックキューブは8個の3面体,12個の2面体,6個の1面体からなる. 図3.3面体(全8個) 図4.2面体(全12個) 図5.1面体(全6個) 表3.3×3×3の解法の探索手法  ルービックキューブを分解し組み直すと,図6のようなパターンが得られる.しかし,このパターンは,完成状態からの回転操作では作ることができない.以後,このことを示す.  上面と下面を基準面とし,基準面の色を基準色とする.基準色の小面が基準面に面している場合,その3面体の捻り量は0であると定義する(図7).同様に,基準色の小面が基準面に対し,図8,図9のような位置関係にあるとき,その3面体の捻り量はそれぞれ1,2であると定義する.  8個ある3面体の捻り量の和を捻り量の総和と呼ぶことにする.例えば,完成状態のルービックキューブは,全ての基準色の小面が基準面を向いているので,捻り量の総和は0である.  次に,回転によって3面体の捻り量がどのように変化するかを考える.まず,Rについて考える.Rに関わる4つの3面体に図10のように番号を付ける.1,2,3,4の3面体の全ての捻り量の組み合わせと,その状態にRを施した後の捻り量の関係をまとめると表1のようになる.表1より,全ての捻り量の状態に対し,Rは捻り量の総和を3で割った余りを変化させないことが分かる.同じようにまとめると,L,F,Bについても同様のことが分かる.また,U,Dは全ての3面体の捻り量を変化させない.  また,3×3×3の探索手法を応用して,一般のサイズに対するプログラムも制作した(図15,16).2×2×2サイズのものは,完成形までの全探索により,解法を求める.一般のサイズのものは,まず,1面体を揃えた後(図17),揃えた1面体を維持しながら2面体を揃え(図18),最終的に3×3×3サイズの探索手法を用いて,解法を求める. 図6.回転により得られないパターン 図7.捻り量0 図8.捻り量1 図15.20×20×20サイズ 図16.2×2×2サイズ 図17.1面体揃え 図18.2面体揃え 6.まとめ 図9.捻り量2 図10.3面体の 番号付け  研究開始時は,ルービックキューブに触れることすら初めての状況であったが,最終的に一般的なサイズのルービックキューブに対しての解法プログラムを作ることができて,非常に満足している.ただ,当初の目的であった,数学的手法による解法によるものではないことに関しては満足していない.また,3×3×3サイズにおいて,俗に"神の数字"と呼ばれる回転数の下限の上限(20手)からは,ほど遠い手数の解法しか見つけられないことに関しても不満がある.  ルービックキューブは既によく研究されているが,一般的なサイズのものに関しては,まだ不十分なことが多々ある.この先,数学の発展はもちろん,コンピュータ性能もますます向上していくものと思われる.数学,コンピュータ双方からのアプローチによって一般のサイズのものに関しても,より研究が進むことを願っている.  以上のことと,完成状態のルービックキューブの捻り量の総和が0であることより,回転によって得られるパターンは,全て捻り量の総和を3で割った余りが0であることが分かる.図6のパターンは捻り量の総和が1であることより,回転によって得ることのできないパターンであるということが分かる. 3面体 1,2,3,4の捻り量 (1) (1)の和を 3で割った余り Rを施した後の1,2,3,4の捻り量(2) (2)の和を 0,0,0,0 2,1,2,1 0,0,0,1 1 0,1,2,1 : 1,2,0,1, 0,2,1,1 2,2,2,1, 0,0,1,0 2,2,2,2 2 1,0,1,0 表1.回転と捻り量の変化の関係(全81通りの一部)