ハノイの塔

問題: ハノイの塔

３本の柱 A,B,C があり、最初に A の柱に大、中、小の円板が入っている。 小さな円板の上に大きな円板を乗せることはできない。 また１度に１枚の円板しか動かせないとする。 このとき、A の柱の円板をすべて C の柱に移すにはどうすればよいか。 (19世紀フランスの数学者Ｅ．リュカ（Edouard Lucas）が考案) 
【初期状態】
　　　　　Ａ　　　　　　　Ｂ　　　　　　　Ｃ
　　　　　┏┓　　　　　　┏┓　　　　　　┏┓
　　　　　┃┃　　　　　　┃┃　　　　　　┃┃
　　　　┏┻┻┓　　　　　┃┃　　　　　　┃┃
　　　┏┻━━┻┓　　　　┃┃　　　　　　┃┃
　　┏┻━━━━┻┓　　　┃┃　　　　　　┃┃
━━┻━━━━━━┻━━━┻┻━━━━━━┻┻━━━━

【目標】
　　　　　Ａ　　　　　　　Ｂ　　　　　　　Ｃ　　　　　
　　　　　┏┓　　　　　　┏┓　　　　　　┏┓　　　　　
　　　　　┃┃　　　　　　┃┃　　　　　　┃┃　　　　　　
　　　　　┃┃　　　　　　┃┃　　　　　┏┻┻┓　　　　
　　　　　┃┃　　　　　　┃┃　　　　┏┻━━┻┓　　　　
　　　　　┃┃　　　　　　┃┃　　　┏┻━━━━┻┓　　
━━━━━┻┻━━━━━━┻┻━━━┻━━━━━━┻━━




今日のトピック
  1. n枚のハノイの塔を解決するためには何回円盤を動かせばよいか？
  2. n枚のハノイの塔を解決するプログラムをどう書けばよいか？




とにかくやってみる

探索木



問題の表現

プログラムでどうやって解けばよいか？
　問題の表現→アルゴリズム


  • 基本知識

    • 集合：要素に順番はなく、要素は一意的である
      {a,b,c}, {テニス,野球,読書},

      ただし情報で扱う集合は応用に依存する
      {テニス,野球,スポーツ}, {1,2,int,even}
      何か変？⇒『データ工学』で説明

    • リスト：要素の順番に意味があり、要素の重複を許す
      [a,b,c]=[a,[b,[c,[]]]]
      数学: [a,b]={a,{a,b}}　　　　[a,b]=[c,d]⇔a=c∧b=d
      Lisp: (a,b,c)

    • 多重集合(マルチセット, バグ)：集合で要素の重複を許す
      {10,10,10,50,50,100,100}


  • 状態：Ｓ＝[Ａの状態,Ｂの状態,Ｃの状態]

  • 手続き：初期状態[[小,中,大],[],[]]⇒⇒目標状態[[],[],[小,中,大]]

  • リストの操作

    • car(L): リストの先頭要素を取り出す
      car([a,b,c])=a

    • cdr(L): リスト L の先頭要素を削除する
      cdr([a,b,c])=[b,c]

    • append(e,L): e をリスト L の先頭に付加する
      append(a,[b,c])=[a,b,c]

    • set_tail(L,e): e をリスト L の最後に付加する
      set_tail([b,c],a)=[b,c,a]

    • mem(L,i): car(cdr(…cdr(L)…))　％ cdr は i-1 個
      リスト L の i 番目の要素を取り出す
      mem([a,b,c],2)=car(cdr([a,b,c]))=car([b,c])=b

    • move(L1,L2): リスト L1 の先頭要素を L2 の先頭に移動する 
      
　　L2:=append(car(L1),L2);
　　L1:=cdr(L1)
    • 円板の比較が必要
      • size(小)＜size(中)
      • size(小)＜size(大)
      • size(中)＜size(大)


    • 条件付move(L1,L2): リスト L1 の円板を L2 の先頭に移動する 
      
　　if size(car(L1))＜size(car(L2)) ∨ car(L2)=[]
　　　then move(L1,L2);

　％ i≠j;L1:=mem(S,i);L2:=mem(S,j), 
　　　　　　ただしS=[左,中,右]


    初期状態をルート、可能な移動を枝にし、次々に木を生成し、目標状態ができたら成功。


操作はわかった。それではどのようなアルゴリズムを書けばよいか？

一般問題解決器 (GPS; general problem solver)

1960 に Newell、Shaw、Simon によって提案された一般問題解決器

  • 基本概念

    • 初期状態
    • 目標 (ゴール)、副目標 (サブゴール)
    • 作用素
    • 差異

  • ハノイの塔

    • 状況：初期状態、目標をリストで表現
      　　[小の位置、中の位置、大の位置]：初期状態　[A,A,A]

      　　上の例 [[小,中,大],[],[]] より効率的であることに注意

    • 作用素:
      • move(大,Loc), move(中,Loc), move(小,Loc)

    • 差異:
      • D1: 大円板の入っている柱とゴールの柱の差異
      • D2: 中円板の入っている柱とゴールの柱の差異
      • D3: 小円板の入っている柱とゴールの柱の差異

    • 差異順序（差異を縮める困難さ）：D1＞D2＞D3
    • 関係表
    • 主目標：[Ａ,Ａ,Ａ]⇒[Ｃ,Ｃ,Ｃ]

  • 手順

    1(主)：[A,A,A] を [C,C,C] にする　　　　　　　　　　[A,A,A]
    　2(1の副)：差異 D1 を小さくする
    　　3(2の副)：大円板をCに移す⇒移せない
    　　　4(3の副)：差異 D2 を小さくする
    　　　　5(4の副)：中円板をCに移す⇒移せない
    　　　　　6(5の副)：差異 D3 を小さくする
    　　　　　　7(6の副)：小円板をCに移す　　　　　　　[C,A,A]
    　　　　　8(5の副)：中円板をCに移す⇒Ｂに移る　[C,B,A]
    　　　9(3の副)：大円板をCに移す⇒移せない
    　　　　10(9の副)：小円板をBに移す　　　　　　　　[B,B,A]
    　　　11(3の副)：大円板をCに移す　　　　　　　　　[B,B,C]
    　12(1の副)：[B,B,C] を [C,C,C] にする
    　　13(12の副)：差異 D2 を小さくする
    　　　14(13の副)：中円板をCに移す⇒移せない
    　　　　15(14の副)：差異 D3 を小さくする
    　　　　　16(15の副)：小円板をAに移す　　　　　　[A,B,C]
    　　　　17(14の副)：中円板をCに移す　　　　　　　[A,C,C]
    　　18(12の副)：[A,C,C] を [C,C,C] にする
    　　　19(18の副)：差異 D3 を小さくする
    　　　　20(19の副)：小円板をCに移す　　　　　　　[C,C,C]

    GPS の問題
    • GPS の探索＝深さ優先
    • 中間状態が記録されない：部分解が出ない
    • 条件が部分的であれば探索は不完全
    • 問題記述能力が限られている


ハノイの塔(再帰)

  • 問題の表現　目標：[Ａ,Ａ,…,Ａ]⇒[Ｃ,Ｃ,…,Ｃ]

  • 方針

    • ＡからＣに移すのと、ＡからＢに移すのは等価
    • n-1枚の円板を移すことができればn枚を移すことができる 
      
【初期状態】
　　　　　Ａ　　　　　　　Ｂ　　　　　　　Ｃ
　　　　　┏┓　　　　　　┏┓　　　　　　┏┓
　　　　　┃┃　　　　　　┃┃　　　　　　┃┃
　　　　┏┻┻┓　　　　　┃┃　　　　　　┃┃
　　　┏┻━━┻┓　　　　┃┃　　　　　　┃┃
　　┏┻━━━━┻┓　　　┃┃　　　　　　┃┃
━━┻━━━━━━┻━━━┻┻━━━━━━┻┻━━━━

【n-1枚】
　　　　　Ａ　　　　　　　Ｂ　　　　　　　Ｃ　　　　　
　　　　　┏┓　　　　　　┏┓　　　　　　┏┓　　　　　
　　　　　┃┃　　　　　　┃┃　　　　　　┃┃　　　　　　
　　　　　┃┃　　　　　　┃┃　　　　　　┃┃
　　　　　┃┃　　　　　┏┻┻┓　　　　　┃┃　　　　
　　┏━━┻┻━━┓　┏┻━━┻┓　　　　┃┃
━━┻━━━━━━┻━┻━━━━┻━━━━┻┻━━━━


    • 解決：n枚のハノイの塔を解くアルゴリズムをP(n,From,To)とする 
      
P(n,1,3);
if n=0 then success;
P(n-1,1,2);
P(1,1,3);
P(n-1,2,3);
success:

    • 問題：Ａのｎ枚の円盤をＣに移すためには、最初の円盤はＢかＣかどちらに移すべきだろうか？

    • 計算量？

      n個の円盤を動かす回数をTnとする。 すると再帰のアルゴリズムのより以下のように定義できる。 
      
T0 = 0
TN = TN-1 + 1 + TN-1 ただし N>0  
   = 2TN-1 + 1      ただし N>0  

Sn=Tn+1と書き直すと

S0 = 1
Sn = (2Tn-1 + 1) + 1 = 2(Tn-1 + 1) = 2Sn-1 = 2n

したがって
Tn = 2n - 1

@n=1のときＡからＣに移動する回数は21-1=1

An=kのときの最少回数を2k-1とする。n=k+1のとき
a) k枚をＡからＢに移す最少回数は2k-1
b) 一番大きな円盤をＡからＣに移す回数は1回
c) Ｂのk枚をＣに移す最少回数は2k-1回
したがってk+1枚の円盤をＡからＣに移す最少回数は
	(2k - 1) + 1 + (2k - 1) = 2k+1 - 1


    • 計算量の応用

      • ハノイの塔（虹のバージョン；７段）の現在の最速記録は71秒である。
        （あるNGO企画室21才の女性で、両手を使っていた。）
        問題：彼女は１秒間に何回円盤を動かしただろうか？）

      • 円盤を1回移動するごとに1秒かかるとすると、円盤7枚なら2分7秒で移し換えられるが、円盤32枚だと不眠不休で動かし続けても約136年かかり、円盤64枚だと宇宙の寿命より長い時間がかかると言われている。 本当だろうか？

        1秒に1回移動した場合の所用時間を計算すると‥‥

        1段 1回 （1s）
        2段 3回 （3s）
        3段 7回 （7s）
        4段 15回 （15s）
        5段 31回 （31s）
        6段 63回 （1m03s）
        7段 127回 （2m07s）
        8段 255回 （4m15s）
        9段 511回 （8m31s）
        10段 1,023回 （17m03s）
        11段 2,047回 （34m07s）
        12段 4,095回 （1h08m15s）
        13段 8,191回 （2h16m31s）
        14段 16,383回 （4h33m03s）
        15段 32,767回 （9h06m07s）
        16段 65,535回 （18h12m15s）
        17段 13,1071回 （1日12h24m31s）
        18段 262,143回 （3日00h49m03s）
        19段 524,287回 （6日01h38m07s）
        20段 1,048,575回 （12日03h16m15s）
        21段 2,097,151回 （24日06h32m31s）
        22段 4,194,303回 （48日13h04m03s）
        23段 8,388,607回 （97日02h10m07s）
        24段 16,777,215回 （194日04h20m15s）
        25段 33,554,431回 （1年23日08h40m31s）
        26段 67,108,863回 （約2年46日17h）
        27段 134,217,727回 （約4年3ヶ月）
        28段 268,435,455回 （約8.5年）
        29段 536,870,911回 （約17年）
        30段 1,073,741,823回 （約34年）
        31段 2,147,483,647回 （約68年）
        32段 4,294,967,295回 （約136年）

        264−1≒1.84×1019≒5,800億年


    • 変形ハノイ

      • 逆ハノイ（脳神経逆流バージョン）
      • 振り分けハノイ
        Ｂの円盤の、下から偶数番目をＡ，奇数番目をＣに移動。
      • 統合ハノイ

      • 凹凸ハノイ
        奇数番目が正立、偶数番目が逆立ち
      • 砂時計ハノイ
        奇数番目が正立、偶数番目が逆立ち
      • 三山ハノイ
        大きな円盤から３で割って１余るものをＡ，２余るものをＢ，割り切れるものをＣ
      • 千鳥ハノイ
        チドリに並べる
      • SWAPハノイ
      • 三色ハノイ


      応用問題