1 第2回 内容 • ハノイの塔―無向グラフと有向グラフ 教科書の 1.3 節 pp.7-12 参照 • 巡回セールスマン問題 教科書の 1.5 節 pp.18-26 参照 ハノイの塔（問題定義） 2 64枚の純金の盤を3本のダイヤモンドの柱のうちの1本に立てら れた．盤は大きいものが一番下にあり，上にいくにしたがって 小さくたっていた． 定めによって，昼夜を問わず，盤を別の柱に移し変えている． 僧侶たちは1度に1枚の盤を動かすことができ，また動かした盤 の下に，それよりも小さいものがあってはならない． 3 ハノイの塔 （盤が２枚の場合の移動） 4 ハノイの塔 （盤が２枚の場合の移動） 5 ハノイの塔 （盤が２枚の場合の移動） 6 ハノイの塔 （盤が２枚の場合の移動） ３回で移動終了 ハノイの塔 （移動を表すグラフ） 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 この部分は板が２枚の 場合に相当 18 ハノイの塔 （移動を表すグラフ） 板が２枚の場合の 移動回数 １回移動 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 19 ハノイの塔（漸化式） A1 1 A2 2 A1 1 A3 2 A2 1 An 2 An1 1 一般形を求めてみよう An ??? 漸化式 （再帰方程式 ともいう） 20 新ルール 3本の柱に順に番号をつけ1,2,3としたとき， 盤の移動を 「柱1から柱2」 「柱2から柱3」 「柱3から柱1」だけに制限する． さて，何回で終了するか？ ハノイの塔 （移動を表すグラフ） 21 ハノイの塔 （移動を表す有向グラ フ） 有向枝 有向グラフ 22 ハノイの塔 （移動を表すグラフ再 び） 無向枝 無向グラフ 23 ハノイの塔 • 盤が３枚の場合のハノイの塔の問 題で、ルール変更後の移動を表す （有向）グラフを作れ。 ハノイの塔 • 盤がn枚の場合のハノイの塔の問題で、 ルール変更後の移動回数（漸化式）を 求めよ。（難易度：★ ★ ★） • 盤がn枚の場合のハノイの塔の問題で、 ルール変更後の移動回数（一般形）を 求めよ。 （難易度：★ ★ ★ ★ ★ ） 26 おまけ問題 • 盤の大きさが同じものがあるときのグラフ を作成せよ．移動回数を求めるための漸 化式と一般解を求めよ． • 棒が４本のときのグラフを作成せよ．移動 回数を求めるための漸化式と一般解を求 めよ． 27 巡回セールスマン問題 現在スイスのチューリッヒに宿を構えているあなたの目的は，スペイ ンのマドリッドで闘牛を見ること，イギリスのロンドンでビッグベンを 見物すること，イタリアのローマでコロシアムを見ること，ドイツのベ ルリンで本場のビールを飲むことである． なるべく短い距離でほかの４つの都市を経由し，再びチューリッヒに 帰ってこようと考えた． どのような順序で旅行すれば，移動距離が最小になるであろうか？ 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 練習問題 • 以下のグラフにおいて最適順回路 を求めよ ５４１ A B 562 774 C ４２５ ３４９ 300 D ハミルトン閉路問題 巡回セールスマン問題のツアーのように、グラフ上で同じ 点をちょうど一度通る閉路をハミルトン閉路とよぶ。以下の グラフにはハミルトン閉路が存在するであろうか。 ハミルトン閉路問題 以下のグラフにはハミルトン閉路が存在するであろうか。存在 しないならばその根拠を示せ。 （難易度：★）
© Copyright 2024 ExpyDoc
