1
第2回 内容
• ハノイの塔―無向グラフと有向グラフ
教科書の 1.3 節 pp.7-12 参照
• 巡回セールスマン問題
教科書の 1.5 節 pp.18-26 参照
ハノイの塔(問題定義)
2
64枚の純金の盤を3本のダイヤモンドの柱のうちの1本に立てら
れた.盤は大きいものが一番下にあり,上にいくにしたがって
小さくたっていた.
定めによって,昼夜を問わず,盤を別の柱に移し変えている.
僧侶たちは1度に1枚の盤を動かすことができ,また動かした盤
の下に,それよりも小さいものがあってはならない.
3
ハノイの塔
(盤が2枚の場合の移動)
4
ハノイの塔
(盤が2枚の場合の移動)
5
ハノイの塔
(盤が2枚の場合の移動)
6
ハノイの塔
(盤が2枚の場合の移動)
3回で移動終了
ハノイの塔
(移動を表すグラフ)
7
8
ハノイの塔
(盤が3枚の場合の移動)
ハノイの塔
(盤が3枚の場合の移
動)
9
10
ハノイの塔
(盤が3枚の場合の移動)
ハノイの塔
(盤が3枚の場合の移
動)
11
12
ハノイの塔
(盤が3枚の場合の移動)
13
ハノイの塔
(盤が3枚の場合の移動)
14
ハノイの塔
(盤が3枚の場合の移動)
ハノイの塔
(盤が3枚の場合の移動)
移動回数7回で完了
15
16
ハノイの塔
(移動を表すグラフ)
板の重さを1,2,4であるとする
それぞれの柱にはまっている板の重さの合計で
板の配置を表現する
17
ハノイの塔
(移動を表すグラフ)
700
610 601
412
421
403 502 520 430
043
142 052
160
250
070 061 241 340
034
025 124
205
106
304 214 016 007
この部分は板が2枚の
場合に相当
18
ハノイの塔
(移動を表すグラフ)
板が2枚の場合の
移動回数
1回移動
700
610 601
412
421
403 502 520 430
043
142 052
160
250
070 061 241 340
板が2枚の場合の
移動回数
034
025 124
205
106
304 214 016 007
19
ハノイの塔(漸化式)
A1  1
A2  2 A1  1
A3  2 A2  1
An  2 An1  1
一般形を求めてみよう
An  ???
漸化式
(再帰方程式
ともいう)
20
新ルール
3本の柱に順に番号をつけ1,2,3としたとき,
盤の移動を
「柱1から柱2」
「柱2から柱3」
「柱3から柱1」だけに制限する.
さて,何回で終了するか?
ハノイの塔
(移動を表すグラフ)
21
ハノイの塔
(移動を表す有向グラ
フ)
有向枝
有向グラフ
22
ハノイの塔
(移動を表すグラフ再
び)
無向枝
無向グラフ
23
ハノイの塔
• 盤が3枚の場合のハノイの塔の問
題で、ルール変更後の移動を表す
(有向)グラフを作れ。
ハノイの塔
• 盤がn枚の場合のハノイの塔の問題で、
ルール変更後の移動回数(漸化式)を
求めよ。(難易度:★ ★ ★)
• 盤がn枚の場合のハノイの塔の問題で、
ルール変更後の移動回数(一般形)を
求めよ。 (難易度:★ ★ ★ ★ ★ )
26
おまけ問題
• 盤の大きさが同じものがあるときのグラフ
を作成せよ.移動回数を求めるための漸
化式と一般解を求めよ.
• 棒が4本のときのグラフを作成せよ.移動
回数を求めるための漸化式と一般解を求
めよ.
27
巡回セールスマン問題
現在スイスのチューリッヒに宿を構えているあなたの目的は,スペイ
ンのマドリッドで闘牛を見ること,イギリスのロンドンでビッグベンを
見物すること,イタリアのローマでコロシアムを見ること,ドイツのベ
ルリンで本場のビールを飲むことである.
なるべく短い距離でほかの4つの都市を経由し,再びチューリッヒに
帰ってこようと考えた.
どのような順序で旅行すれば,移動距離が最小になるであろうか?
28
各都市間の距離
569
ロンドン
London
476
ベルリン
Berlin
チューリッヒ
Zurich
408
736
784
マドリッド
Madrid
774
434
1154
852
894
ローマ
Rome
29
巡回セールスマン問題(解)
チューリッヒ(Z)
マドリッド(M)
ロンドン(L)
ローマ(R)
ベルリン(B)
774
+
784
+
894
+
736
+
408
=
3596
順回路=解
距離が最小になる順回路
=
最適巡回路
(最適解)
目的関数値
30
巡回セールスマン問題(列挙木)
Z
L
M
L
R
B
M
R
B
R
B
M
L
B
M
L
R
RB L B L R R B M B M R L B M B M L L R M R M L
BR B L R L B R B M R B
B L B M L M R L R M L M
3596
3297 3497 3407 3825 4034 3256 3297 3784 4034 3485 3407
最適解は
3047
3485 3674 3825 3584 3297 3674 3784
3497 3256 3596
3047
チューリッヒ⇒ローマ⇒マドリッド⇒ロンドン⇒ベルリン⇒チューリッヒ
チューリッヒ⇒ベルリン⇒ロンドン⇒マドリッド⇒ローマ⇒チューリッヒ
31
練習問題
• 以下のグラフにおいて最適順回路
を求めよ
541
A
B
562
774
C
425
349
300
D
ハミルトン閉路問題
巡回セールスマン問題のツアーのように、グラフ上で同じ
点をちょうど一度通る閉路をハミルトン閉路とよぶ。以下の
グラフにはハミルトン閉路が存在するであろうか。
ハミルトン閉路問題
以下のグラフにはハミルトン閉路が存在するであろうか。存在
しないならばその根拠を示せ。 (難易度:★)
ダウンロード

PowerPoint (新バージョン:練習問題を含む)