ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋 2009/3/3 組合せゲーム・パズル ミニ研究集会(東工大) 1 目次 ハノイの塔 研究内容 ハノイグラフについて ダイクストラのアルゴリズム 実験結果 まとめと今後の課題 2 ハノイの塔 1883年、E. Lucasによって考案された組合せゲーム 柱3本、円盤数nのとき、最小移動回数は2n –1 3 k本ハノイの塔 k=4のとき、1907年のDudeney以来考察されている しかし、k > 4のとき、最小解は未だ解明されていない ・ 最良の上界: [Frame, 1941], [Stewart, 1941] ・ 最良の下界: [Chen, 2004] 4 研究内容 1. k本ハノイの塔問題に対してグラフを用い たモデル化を行う 2. グラフを利用してプログラム上で最小移 動回数の実験的な導出を行う 5 ハノイグラフ 全円盤の配置された状態を頂点とし、 遷移しうる状態間に辺を引いた(無向)グラフ 状態の符号化 1 2 4 7 ○ (7, 0, 0) ○ (6, 1, 0) ○ (6, 0, 1) 6 ハノイグラフ(柱3本) 円盤数 n = 1, 2, 3, 4,・・・のとき、 (Wolfram, MathWorldより) → チェルピンスキーの三角形に収束 7 ハノイグラフ(柱4本以上) M.-K. Lee, “The graph for the Tower of Hanoi with four pegs”, Pythagoras, Vol. 57, pp. 27-31, 2003. 課題 ・ 円盤数nに対する一般的な生成法が示されておらず, 柱の数4本以上のハノイグラフの生成法も未知 一般のk本ハノイの塔に対して、ハノイグラフ の生成法を示す 8 k=4のときのハノイグラフの生成法 (0,0,0,0) (1,0,0,0) (0,0,0,0) (0,0,0,1) (0,0,0,0) (0,0,0,0) (0,1,0,0) (0,0,0,0) (0,0,1,0) 9 (1,0,0,0) (3,0,0,0) (0,0,0,1) (2,0,0,1) (1,0,0,0) (1,0,0,2) (0,0,0,1) (0,0,0,3) (0,1,0,0) (2,1,0,0) (0,0,1,0) (2,0,1,0) (0,1,0,0) (0,1,0,2) (0,0,1,0) (0,0,1,2) + (2,0,0,0) + (0,0,0,2) + (0,2,0,0) + (0,0,2,0) (1,0,0,0) (1,2,0,0) (0,0,0,1) (0,2,0,1) (1,0,0,0) (1,0,2,0) (0,0,0,1) (0,0,2,1) (0,1,0,0) (0,3,0,0) (0,0,1,0) (0,2,1,0) (0,1,0,0) (0,1,2,0) (0,0,1,0) (0,0,3,0) 10 (15,0,0,0) (8,0,0,7) (7,0,0,8) (0,0,0,15) (0,0,1,14) (8,1,0,6) (8,0,1,6) ・・・ ・・・ (8,7,0,8) (8,6,1,0) (8,0,7,0) (0,7,0,8) (0,6,1,8) ・・・ (7,8,0,0) (0,8,0,7) (0,8,1,6) (7,0,8,0) (0,0,8,7) (0,1,8,6)(0,0,9,6) (0,15,0,0) (0,8,7,0) ・・・ (0,0,7,8) ・・・ ・・・ (0,7,8,0) (0,0,15,0) 11 k本ハノイグラフ (1)円盤数 n=1 (0,1,0,・・・,0) (1,0,0,・・・,0) (0,0,・・・,0,1) (0,0,・・・,1,0) (0,0,1,・・・,0) H1 = K k 12 (3,0,0,・・・,0) (1,0,0,・・・,0) (2) n=2 (2,0,・・・,0,1) (0,0,・・・,0,1) (2,1,0,・・・,0) (0,1,0,・・・,0) (2,0,・・・,1,0) (0,0,・・・,1,0) + (2,0,0,・・・,0) (2,0,1,・・・,0) (0,0,1,・・・,0) (1,0,0,・・・,0) (1,0,0,・・・,2) (0,1,0,・・・,0) (0,1,0,・・・,2) (0,3,0,・・・,0) (0,1,0,・・・,0) (1,2,0,・・・,0) (1,0,0,・・・,0) (0,2,・・・,0,1) (0,0,・・・,0,1) (0,2,1,・・・,0) (0,0,1,・・・,0) (0,0,1,・・・,0) (0,0,1,・・・,2) (0,0,・・・,0,1) (0,0,・・・,0,3) (0,0,・・・,1,0) (0,0,・・・,1,2) + (0,0,・・・,0,2 ) (0,2,・・・,1,0) (0,0,・・・,1,0) + (0,2,0,・・・,0) (1,0,2,・・・,0) (1,0,0,・・・,0) (0,1,2,・・・,0) (0,1,0,・・・,0) (0,0,3,・・・,0) (0,0,1,・・・,0) (0,0,・・・,0,1) (0,0,・・・,1,0) + (0,0,2,・・・,0) H2 13 (n) n円盤 n2 i , 2 ,0・・・ i0 ,0 k本 n-1枚 ・・・ +(2n-1,0,・・・,0,0) +( Hn-1,1 ) 0,2n-1,・・・,0,0 Hn-1,2 + (0,0,2n-1,・・・,0) Hn-1,3 + (0,0,・・・,0,2n-1) Hn-1, i1内の頂点 ai31,i1i22,・・・ ・・・,iinn aj1,j2,・・・,jn Hn-1,k 辺が存在する条件は? Hn 14 ハノイグラフHnに関する定理 定理: 点 ai1,i2,・・・,in と aj1,j2,・・・,jn の間に辺が存在 (1) i1=j1 のとき,それらがHn-1 で辺をもつ (2) i1≠j1のとき, i1 { i2, i3, ・・・,in} かつ j1 { j2, j3, ・・・,jn} かつ i2 = j2, ・・・, in = jn 15 i1 { i2, i3, ・・・,in} j1 { j2, j3, ・・・,jn} i2 = j2, ・・・, in = jn 定理の略証 i1 j1 i1 j1 ai1,i2,・・・,in aj1,j2,・・・,jn 16 (7,0,0) (6,1,0) (6,0,1) (1,0,6) (0,7,0) ・・・ (0,1,6) (0,0,7) ダイクストラのアルゴリズムを適用 ハノイの塔の最小手数=ハノイグラフの最短経路 17 ダイクストラのアルゴリズム グラフ上の二点間の最短距離を求める アルゴリズム 1 基準点 S1 3 (4) 3 4 (5) S3 6 (9) S2 ( )内の数字 ・・・ 基準点からの距離 18 実験結果 4本ハノイグラフにおける最短手数の導出結果 円盤枚数 n 4 5 6 7 8 9 10 移動回数 9 13 17 25 33 41 - 処理時間[s] 0 0.015 0.14 2.6 77 1696 - (CPU:2.01GHz メモリ:1.21GB OS:Microsoft WindowsXP SP3) 19 4本ハノイの処理時間 1800 1696 1600 処 理 時 間.[s] 1400 1200 1000 800 600 400 200 0 0 0 0 0 0.015 77 0.14 2.6 0 0 2 4 6 8 10 円盤枚数[枚] 20 柱5本の場合 5本ハノイグラフにおける最短手数の導出結果 円盤枚数 n 4 移動回数 7 5 11 6 15 7 19 8 23 9 27 10 - 処理時間 [s] 0 0.083 2.2 143 3756 100150 - (CPU:2.01GHz メモリ:1.21GB OS:Microsoft WindowsXP SP3) 21 5本ハノイの処理時間 120000 100150 処理時間 [s] 100000 80000 60000 40000 20000 0 0 0 0 0 2 0 3756 0 0.083 2.2 143 4 6 8 10 円盤枚数 [枚] 22 まとめ ○一般的なk本ハノイについてハノイグラフ の生成法を示した ○最短経路導出のプログラムを実装し, 柱4本と5本のハノイの塔について,n < 9 での最短経路を導出した 23 今後の課題 ○ハノイグラフの最短経路を理論的に導 出する ○最短経路導出のアルゴリズムや測定 環境の改善を行い、導出にかかる時間 を短縮する 24
© Copyright 2024 ExpyDoc