ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋

Presentation on theme: "ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋"— Presentation transcript:

1 ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋
東京電機大学 理工学部 村田和也　 松浦昭洋　 2009/3/3 組合せゲーム・パズル　ミニ研究集会（東工大）

2 目次 ハノイの塔 研究内容 ハノイグラフについて ダイクストラのアルゴリズム 実験結果 まとめと今後の課題

3 ハノイの塔 1883年、E. Lucasによって考案された組合せゲーム 柱3本、円盤数nのとき、最小移動回数は2n – 1

4 k本ハノイの塔 k=4のとき、1907年のDudeney以来考察されている しかし、k > 4のとき、最小解は未だ解明されていない
次に柱4本をもつハノイの塔を説明します． 柱4本の時，Stewartは次のようなアルゴリズムを提案しました． 円盤ｎ枚をn-t枚とｔ枚に分けて考えます．まず円盤n-t枚を柱4本を使って，柱2に移動させます．つぎに残りのｔ枚を柱3本を使って，柱4に移動させます． そして最後に，柱2にあるn-t枚を柱4本を使い，柱４に移動させます． 円盤ｎ枚を移動する最小ステップ数をpeg(n,4)とすると，式②のような再帰式となります． この再帰式は，柱4本を使って移動させる円盤と柱3本を使って 移動させる円盤の枚数を工夫し，合計が一番小さくなるステップ数となるようなｔを発見しなければなりません． k=4のとき、1907年のDudeney以来考察されている しかし、k > 4のとき、最小解は未だ解明されていない ・ 最良の上界： [Frame, 1941], [Stewart, 1941] ・ 最良の下界： [Chen, 2004]

5 研究内容 k本ハノイの塔問題に対してグラフを用い たモデル化を行う グラフを利用してプログラム上で最小移 動回数の実験的な導出を行う

6 ハノイグラフ 全円盤の配置された状態を頂点とし、 遷移しうる状態間に辺を引いた（無向）グラフ 状態の符号化 7 (7, 0, 0)
1 2 4 7 (7, 0, 0) (6, 1, 0) (6, 0, 1) ○

7 (Wolfram, MathWorldより）
ハノイグラフ（柱3本） 円盤数 n = 1, 2, 3, 4,・・・のとき、 (Wolfram, MathWorldより） → チェルピンスキーの三角形に収束

8 ハノイグラフ（柱4本以上） M.-K. Lee, “The graph for the Tower of Hanoi with
four pegs”, Pythagoras, Vol. 57, pp , 2003. 課題 ・ 円盤数nに対する一般的な生成法が示されておらず， 　柱の数4本以上のハノイグラフの生成法も未知 一般のk本ハノイの塔に対して、ハノイグラフの生成法を示す

9 (0,0,0,0) k=4のときのハノイグラフの生成法 (1,0,0,0) (0,0,0,0) (0,0,0,1) (0,0,0,0)
(0,1,0,0) (0,0,0,0) (0,0,0,0) (0,0,1,0)

10 (1,0,0,0) (3,0,0,0) (2,0,0,1) (0,0,0,1) (1,0,0,0) (1,0,0,2) (0,0,0,3) (0,0,0,1) (2,1,0,0) (0,1,0,0) (0,0,1,0) (2,0,1,0) (0,1,0,2) (0,1,0,0) (0,0,1,2) (0,0,1,0) + (2,0,0,0) + (0,0,0,2) + (0,2,0,0) + (0,0,2,0) (0,0,2,1) (0,0,0,1) (1,2,0,0) (1,0,0,0) (0,0,0,1) (0,2,0,1) (1,0,2,0) (1,0,0,0) (0,3,0,0) (0,1,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)

11 (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) (0,0,7,8) ・・・ ・・・ (7,8,0,0) (0,8,0,7) (7,0,8,0) (0,0,8,7) (0,8,1,6) (0,1,8,6) (0,0,9,6) ・・・ ・・・ ・・・ (0,0,15,0) (0,15,0,0) (0,8,7,0) (0,7,8,0)

12 k本ハノイグラフ (1)円盤数 n=1 H1 = Kk (1,0,0,・・・,0) (0,0,・・・,0,1) (0,1,0,・・・,0)
(0,0,1,・・・,0) (0,0,・・・,0,1) (0,0,・・・,1,0) (1)円盤数 n=1 H1 = Kk

13 (2) n=2 H2 (2,0,・・・,1,0) (0,0,・・・,1,0) + (2,0,0,・・・,0) (0,0,・・・,1,0)
(3,0,0,・・・,0) (2,1,0,・・・,0) (2,0,1,・・・,0) (2,0,・・・,0,1) (2,0,・・・,1,0) (1,2,0,・・・,0) (0,3,0,・・・,0) (0,2,1,・・・,0) (0,2,・・・,0,1) (0,2,・・・,1,0) (1,0,2,・・・,0) (0,1,2,・・・,0) (0,0,3,・・・,0) (0,0,・・・,0,1) (0,0,・・・,1,0) (1,0,0,・・・,2) (0,1,0,・・・,2) (0,0,1,・・・,2) (0,0,・・・,0,3) (0,0,・・・,1,2) (2) n=2 (1,0,0,・・・,0) (0,1,0,・・・,0) (0,0,1,・・・,0) (0,0,・・・,0,1) (0,0,・・・,1,0) + (2,0,0,・・・,0) + (0,2,0,・・・,0) + (0,0,2,・・・,0) + (0,0,・・・,0,2) (1,0,0,・・・,0) (0,1,0,・・・,0) (0,0,1,・・・,0) (0,0,・・・,0,1) (0,0,・・・,1,0) (1,0,0,・・・,0) (0,1,0,・・・,0) (0,0,1,・・・,0) (0,0,・・・,0,1) (0,0,・・・,1,0) (1,0,0,・・・,0) (0,1,0,・・・,0) (0,0,1,・・・,0) (0,0,・・・,0,1) (0,0,・・・,1,0) H2

14 ai1,i2,・・・,in ai1,i2,・・・,in a3,1,・・・,in a3,i2,・・・,in aj1,j2,・・・,jn
(n) n円盤 ・・・ k本 n-1枚 + (0,2n-1,・・・,0,0) + (0,0,2n-1,・・・,0) + (0,0,・・・,0,2n-1) + (2n-1,0,・・・,0,0) Hn-1,1 Hn-1,2 Hn-1, i1内の頂点　 Hn-1,k ai1,i2,・・・,in ai1,i2,・・・,in a3,1,・・・,in a3,i2,・・・,in 辺が存在する条件は？ aj1,j2,・・・,jn Hn Hn-1,3

15 ハノイグラフHnに関する定理 定理： 点 ai1,i2,・・・,in と aj1,j2,・・・,jn の間に辺が存在
　　　定理： 　　　点 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

16 定理の略証 ai1,i2,・・・,in aj1,j2,・・・,jn i1 { i2, i3, ・・・，in}
j1　{ j2, j3, ・・・，jn} i2 = j2, ・・・, in = jn 定理の略証 i1 j1 ai1,i2,・・・,in i1 j1 aj1,j2,・・・,jn

17 ハノイの塔の最小手数=ハノイグラフの最短経路
(7,0,0) (6,1,0) (6,0,1) ・・・ ・・・ (1,0,6) (0,7,0) (0,0,7) ・・・ (0,1,6) ハノイの塔の最小手数=ハノイグラフの最短経路 ダイクストラのアルゴリズムを適用

18 ダイクストラのアルゴリズム グラフ上の二点間の最短距離を求める アルゴリズム S1 S3 基準点 S2
　　グラフ上の二点間の最短距離を求める アルゴリズム S1 S3 1 基準点 4 (5) 3 6 (9) 3 (4) S2 ( )内の数字 ・・・ 基準点からの距離

19 4本ハノイグラフにおける最短手数の導出結果
実験結果 0.015 13 5 - 10 1696 41 9 77 2.6 0.14 処理時間[s] 33 25 17 移動回数 8 7 6 4 円盤枚数 n (CPU:2.01GHz メモリ:1.21GB OS:Microsoft WindowsXP SP3) 4本ハノイグラフにおける最短手数の導出結果

20 4本ハノイの処理時間 1696 0.015 0.14 2.6 77

21 5本ハノイグラフにおける最短手数の導出結果
柱5本の場合 5本ハノイグラフにおける最短手数の導出結果 円盤枚数 n 4 5 6 7 8 9 10 移動回数 11 15 19 23 27 - 処理時間 [s] 0.083 2.2 143 3756 100150 (CPU:2.01GHz メモリ:1.21GB OS:Microsoft WindowsXP SP3)

22 5本ハノイの処理時間 100150 0.083 2.2 143 3756

23 まとめ ○一般的なk本ハノイについてハノイグラフの生成法を示した ○最短経路導出のプログラムを実装し，
　 柱4本と5本のハノイの塔について，n < 9 での最短経路を導出した

24 今後の課題 　 ○ハノイグラフの最短経路を理論的に導 　　　出する 　 ○最短経路導出のアルゴリズムや測定 　　　環境の改善を行い、導出にかかる時間 　　　を短縮する