PowerPoint プレゼンテーション

ハノイグラフの生成と最短経路の導出
東京電機大学理工学部
村田和也
松浦昭洋
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円盤
n2 i
,
 2 ,0・・・
i0
,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

Download Report