第2回 内容 ハノイの塔―無向グラフと有向グラフ 教科書の 1.3 節 pp.7-12 参照

Presentation on theme: "第2回 内容 ハノイの塔―無向グラフと有向グラフ 教科書の 1.3 節 pp.7-12 参照"— Presentation transcript:

1 第2回 内容 ハノイの塔―無向グラフと有向グラフ 教科書の 1.3 節 pp.7-12 参照

2 ハノイの塔（問題定義） 　64枚の純金の盤を3本のダイヤモンドの柱のうちの1本に立てられた．盤は大きいものが一番下にあり，上にいくにしたがって小さくたっていた． 　定めによって，昼夜を問わず，盤を別の柱に移し変えている．僧侶たちは1度に1枚の盤を動かすことができ，また動かした盤の下に，それよりも小さいものがあってはならない．

3 ハノイの塔 （盤が２枚の場合の移動）

4 ハノイの塔 （盤が２枚の場合の移動）

5 ハノイの塔 （盤が２枚の場合の移動）

6 ハノイの塔 （盤が２枚の場合の移動） ３回で移動終了

7 ハノイの塔 （移動を表すグラフ）

8 ハノイの塔 （盤が3枚の場合の移動）

9 ハノイの塔 （盤が3枚の場合の移動）

10 ハノイの塔 （盤が3枚の場合の移動）

11 ハノイの塔 （盤が3枚の場合の移動）

12 ハノイの塔 （盤が3枚の場合の移動）

13 ハノイの塔 （盤が3枚の場合の移動）

14 ハノイの塔 （盤が3枚の場合の移動）

15 ハノイの塔 （盤が3枚の場合の移動） 移動回数7回で完了

16 ハノイの塔 （移動を表すグラフ） 板の重さを1,2,4であるとする それぞれの柱にはまっている板の重さの合計で 板の配置を表現する

17 ハノイの塔 （移動を表すグラフ） 700 610 601 412 421 403 502 520 430 043 034 142 052 025 124 160 250 205 106 070 061 241 340 304 214 016 007 この部分は板が２枚の場合に相当

18 ハノイの塔 （移動を表すグラフ） 板が２枚の場合の 移動回数 700 610 601 412 421 １回移動 403 502 520
430 043 034 142 052 025 124 160 250 205 106 070 061 241 340 304 214 016 007 板が２枚の場合の 移動回数

19 ハノイの塔（漸化式） 漸化式 （再帰方程式 ともいう） 一般形を求めてみよう

20 新ルール 3本の柱に順に番号をつけ1,2,3としたとき，盤の移動を 「柱1から柱2」 「柱2から柱3」 「柱3から柱1」だけに制限する．
さて，何回で終了するか？

21 ハノイの塔 （移動を表すグラフ）

22 ハノイの塔 （移動を表す有向グラフ） 有向枝 有向グラフ

23 ハノイの塔 （移動を表すグラフ再び） 無向枝 無向グラフ

24 盤が３枚の場合のハノイの塔の問題で、ルール変更後の移動を表す（有向）グラフを作れ。

25 ハノイの塔 盤がn枚の場合のハノイの塔の問題で、ルール変更後の移動回数（漸化式）を求めよ。（難易度：★ ★ ★）

26 おまけ問題 盤の大きさが同じものがあるときのグラフを作成せよ．移動回数を求めるための漸化式と一般解を求めよ．
棒が４本のときのグラフを作成せよ．移動回数を求めるための漸化式と一般解を求めよ．

27 巡回セールスマン問題 現在スイスのチューリッヒに宿を構えているあなたの目的は，スペインのマドリッドで闘牛を見ること，イギリスのロンドンでビッグベンを見物すること，イタリアのローマでコロシアムを見ること，ドイツのベルリンで本場のビールを飲むことである． なるべく短い距離でほかの４つの都市を経由し，再びチューリッヒに帰ってこようと考えた． どのような順序で旅行すれば，移動距離が最小になるであろうか？

28 各都市間の距離 569 ロンドン London ベルリン Berlin チューリッヒ Zurich 476 408 736 784
マドリッド Madrid 774 434 ローマ Rome 1154 852 894

29 巡回セールスマン問題（解） チューリッヒ(Z) 順回路＝解 774 + マドリッド(M) 784 894 736 距離が最小になる順回路
408 マドリッド(M) 距離が最小になる順回路 ＝ 最適巡回路 （最適解） ロンドン(L) ローマ(R) ベルリン(B) = 3596 目的関数値

30 巡回セールスマン問題（列挙木） Z B L R M M L R B M R B M L B L R R B L B L R R B M B
3596 3297 3497 3407 3825 4034 3256 3297 3784 4034 3485 3407 3485 3674 3825 3584 3297 3674 3784 3497 3256 3596 3047 3047 最適解は チューリッヒ⇒ローマ⇒マドリッド⇒ロンドン⇒ベルリン⇒チューリッヒ チューリッヒ⇒ベルリン⇒ロンドン⇒マドリッド⇒ローマ⇒チューリッヒ

31 練習問題 以下のグラフにおいて最適順回路を求めよ ５４１ A B 562 ３４９ 300 774 C D ４２５

32 ハミルトン閉路問題 巡回セールスマン問題のツアーのように、グラフ上で同じ点をちょうど一度通る閉路をハミルトン閉路とよぶ。以下のグラフにはハミルトン閉路が存在するであろうか。

33 以下のグラフにはハミルトン閉路が存在するであろうか。存在しないならばその根拠を示せ。 （難易度：★）
ハミルトン閉路問題 以下のグラフにはハミルトン閉路が存在するであろうか。存在しないならばその根拠を示せ。 （難易度：★）