読者です 読者をやめる 読者になる 読者になる

はしくれエンジニアもどきのメモ

情報・Web系技術の勉強メモ・備忘録です。

ハノイの塔問題メモ

 
In [1]:
import scipy as sp

import matplotlib.pylab as plt
 

ハノイの塔

 

規則

 
  • 1回に1枚の円盤だけ動かす.
  • 移動の途中で円盤の大小を逆に積んではいけない. 常に大きい方の円盤が下になるようにする.
  • 棒A,B,C以外のところに円盤を置いてはいけない.
 

ハノイの塔($n=3$段)の目標

 1                                  1
22                 ->              22
333                                333
場所A 場所B 場所C     場所A 場所B 場所C
 

ハノイの塔を解く手順

 

2段ハノイの塔の場合

 

初期状態

 1                
22                               
場所A 場所B 場所C

1回目:1段目 A->B

22      1                        
場所A 場所B 場所C

2回目:2段目 A->C

        1     22                   
場所A 場所B 場所C

3回目:1段目 B->C

              1
              22                   
場所A 場所B 場所C
 

3段ハノイの塔の場合

 

初期状態

 1                
22   
333
場所A 場所B 場所C

まず,[1-2]段を場所Bに逃がす

1回目:1段目 A->C

22
333           1
場所A 場所B 場所C

2回目:2段目 A->B

333    22     1
場所A 場所B 場所C

3回目:1段目 C -> B

        1
333    22     
場所A 場所B 場所C

避難完了したので,3段目を場所Cへ

4回目:1段目 A -> C

        1
       22    333
場所A 場所B 場所C

2段目を場所$C$へ移動させるため, [1]段を避難させる

5回目:1段目 B -> A


  1    22    333
場所A 場所B 場所C

避難できたので,2段目を場所Cへ

6回目:2段目 B -> C

             22
  1          333
場所A 場所B 場所C

7回目:1段目 A -> C

              1
             22
             333
場所A 場所B 場所C
 

4段ハノイの塔の場合

 

初期状態

 1                
 22   
333
4444
場所A 場所B 場所C

まず,[1-3]段を場所Bに逃がす. そのため,3段目を場所Bに置くことを考える.

1回目:1段目 A->B

 22
333           
4444    1
場所A 場所B 場所C

2回目:2段目 A->C

333           
4444    1     22
場所A 場所B 場所C

3回目:1段目 B -> C

333            1    
4444          22
場所A 場所B 場所C

3段目を場所Bへ

4回目:3段目 A -> B

              1    
4444    333   22
場所A 場所B 場所C

避難させていた[1-2]段を場所$C$から場所Bへ

5回目:1段目 C -> A

  1               
4444    333   22
場所A 場所B 場所C

6回目:2段目 C -> B

 1      22         
4444   333  
場所A 場所B 場所C

7回目:1段目 A -> B

        1
        22
4444   333
場所A 場所B 場所C

避難完了したので,4段目を場所Cへ

8回目:4段目 A -> C

        1
        22
       333  4444
場所A 場所B 場所C

場所Bの3段目を場所Cへ移動させることを考える. そのため,[1-2]段を場所Aへ避難させる.

9回目:1段目 B -> C


        22    1
       333  4444
場所A 場所B 場所C

10回目:2段目 B -> A

              1
  22   333  4444
場所A 場所B 場所C

11回目:1段目 C -> A

  1
  22   333  4444
場所A 場所B 場所C

[1-2]段の避難ができたので, 3段目を場所Cへ

12回目:1段目 B -> C

  1          333
  22         4444
場所A 場所B 場所C

2段目を場所Cへ動かすことを考える.

13回目:1段目 A -> B

             333
  22    1    4444
場所A 場所B 場所C

[1]段の避難ができたので,2団目を場所Cへ移動

14回目:2段目 A -> C

              22
             333
        1    4444
場所A 場所B 場所C

移動完了

15回目:1段目 B -> C

              1
              22
             333
             4444
場所A 場所B 場所C
 

n段ハノイの塔を解く手順

 

考え方

 

n段ハノイの塔を徳手順を考える.

Hanoi(k, s, p, g): k段の円盤を場所 $s$ から 場所 $g$ へ 途中,場所pを介しながら円盤を移動する手順とする.

  • Hanoi(1, s, p, g) のとき: 1段の円盤を場所 $s$ から,場所 $g$ へ移動する手順となる.場所pを介する必要がないので,1回の操作で解決できる.

  • 一般のHanoi(k, s, p, g) のとき:

    1. $k-1$段の円盤を場所 s から場所 p へ一旦移動(逃がし),

            1
      333    22  
      場所s 場所p 場所g
    2. $k$段目を s -> g へ(1回)移動し,

             1
            22    333
      場所s 場所p 場所g
    3. 一旦逃がした$k-1$段を場所pから場所gへ移動させる.

                   1 
                   22
                  333
      場所s 場所p 場所g
 
  • $k = 1$ の場合は,1回と決まっている.
  • $k$段の解は,$k-1$段の解がわかれば構成できる.

こういう場合,再帰呼び出しが得意な場合になる.

 
フローチャート
 

コード

In [2]:
def hanoi(n:int, start:str, partition:str, goal:str):
    '''
    n段をstart->goalへ移動.
    partitionは途中の移動に使用
    '''
    if n >= 1:
        # 上に乗っているn-1段を一旦移動
        hanoi(n-1, start, goal, partition)
        print("{} 段目を {} -> {} ".format(n, start, goal))
        # 一旦移動したn-1段をgoalへ
        hanoi(n-1, partition, start, goal)
In [3]:
hanoi(3, "A", "B", "C")
 
1 段目を A -> C 
2 段目を A -> B 
1 段目を C -> B 
3 段目を A -> C 
1 段目を B -> A 
2 段目を B -> C 
1 段目を A -> C 
 

関数呼び出しを追う

 

n=2の場合

 
Hanoi(2, f, w, d)
{
    Hanoi(1, f, d, w)
    {
       print(1: f -> w)
    }
    print(2: f -> d)
    Hanoi(1, w, f, d)
    {
        print(1: w -> d)
    }
}
 

n=3の場合

 
Hanoi(3, f, w, d)
{
    Hanoi(2, f, d, w)
    {
        Hanoi(1, f, w, d)
        {
           print(1: f -> d)
        }
        print(2: f -> w)
        Hanoi(1, d, f, w)
        {
            print(1: d -> w)
        }
    }

    print(3: f -> d)

    Hanoi(2, w, f, d)
    {
        Hanoi(1, w, d, f)
        {
            print(1: w -> f)
        }
        print(2: w -> d)
        Hanoi(1, f, w, d)
        {
            print(1: f -> d)
        }
    }
}
 

ハノイの塔の証明

 
01 def hanoi(n:int, start:str, partition:str, goal:str): 
02 if n >= 1:
03      hanoi(n-1, start, goal, partition) # 上に乗っているn-1段を一旦移動
04      print("{} 段目を {} -> {} ".format(n, start, goal))
05      hanoi(n-1, partition, start, goal)

ここでHanoi(n,start, partition, goal) という操作の意味を正確にしておく。

  • この操作は $1-n$ まで順に積まれた $n$ 個の円盤を start から goal へ移動する操作。
  • 操作開始時,start には $1 - n$ まで順に積まれた $n$ 個の円盤がある。
  • 操作終了後,goal には$1 - n$まで順に円盤が積まれたものになる。
  • その際,partition を補助的に使っても良い。
  • さらに,この操作はゲームの規則(1),(2),(3) を満たす。
  • またn+1 以上の円盤があっても,この操作はそれに関係なく行われる。
 

証明は数学的帰納法を使う。

  1. $n=0$ の場合: 2行の条件を満たさないから,Hanoi(n, s, p, g) は何もしない。

  2. $n=1$ の場合: $n=1$ の場合,$3-5$行が実行されるが, 3,5行は Hanoi(0,s, g, p)Hanoi(0, p, s, g) で何も実行しません。つまり,この場合は,4行だけ実行されます。従って,1番の円盤を start から goal へ移動と言う操作で,この場合正しい操作になっています。

  3. $n-1$の場合: Hanoi が正しい操作を行っていると仮定します。 このとき $n$の場合正しい操作になることを示す。

    1. まず,開始時 start には $1 - n$ まで順に積まれた$n$個の円盤がある。   2. 03行目で,Hanoi(n-1, s, g, p):このとき,start には $1 - n$ までの円盤があるから,この操作は可能。 ここで Hanoi は n-1 の時は正しい操作をすると言う仮定から,3行の結果,$1 - n-1$ までの円盤が規則(1),(2),(3) を満たしながら p へ移動する。  この過程で $1 - n-1$ 以外の円盤の上に乗ることもありますが,あったとしても, それは $n$ 以上の大きいものの上です。 従って規則(2)を満たす。
    2. 次に,04行目で $n$番目の円盤を s から g へ移動する。今 $1 - n-1$までの円盤は p にあるから,goal に円盤があるとしてもそれは$n + 1$番以上の円盤です。従って,$n$の円盤を g に移動しても規則(2)を満たす。
  4. 最後に,5行目で Hanoi(n-1, p, start, goal): これは先ほど移動した,$1 - n-1$ の円盤を pから goal に移動するもの。 これもHanoi は $n-1$ の時は正しい操作をすると言う仮定から,正しく動作し,規則(2)を満たす。

以上から,nの場合も正しい操作になる。

 

移動回数

In [4]:
def hanoi(n:int, start:str, partition:str, goal:str):
    move_n = 0
    def hanoi_rec(n:int, start:str, partition:str, goal:str):
        '''
        n段をA->Bへ移動.
        Cは途中の移動に使用
        '''
        if n >= 1:
            # nonlocal でローカル変数でないことを宣言
            # https://docs.python.jp/3/faq/programming.html
            nonlocal move_n 
            
            # 上に乗っているn-1段を一旦移動
            hanoi_rec(n-1, start, goal, partition)
            print("{} 段目を {} -> {}".format(n, start, goal))
            # 一旦移動したn-1段をgoalへ
            hanoi_rec(n-1, partition, start, goal)
            move_n = move_n + 1 
            
    hanoi_rec(n, start, partition, goal)
    print("move_n: ", move_n)
In [5]:
hanoi(3, "A", "B", "C")
 
1 段目を A -> C
2 段目を A -> B
1 段目を C -> B
3 段目を A -> C
1 段目を B -> A
2 段目を B -> C
1 段目を A -> C
move_n:  7
In [6]:
hanoi(5, "A", "B", "C")
 
1 段目を A -> C
2 段目を A -> B
1 段目を C -> B
3 段目を A -> C
1 段目を B -> A
2 段目を B -> C
1 段目を A -> C
4 段目を A -> B
1 段目を C -> B
2 段目を C -> A
1 段目を B -> A
3 段目を C -> B
1 段目を A -> C
2 段目を A -> B
1 段目を C -> B
5 段目を A -> C
1 段目を B -> A
2 段目を B -> C
1 段目を A -> C
3 段目を B -> A
1 段目を C -> B
2 段目を C -> A
1 段目を B -> A
4 段目を B -> C
1 段目を A -> C
2 段目を A -> B
1 段目を C -> B
3 段目を A -> C
1 段目を B -> A
2 段目を B -> C
1 段目を A -> C
move_n:  31
 

移動回数の計算

 

参考: http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Hanoi.html

ハノイの塔の解法プログラム Hanoi での移動の回数を計算。 移動の回数を $H(n)$ と表す。

Hanoi(n, s, p, g)は 3,4,5行で移動を出力するが,

  • 3行は $H(n-1)$ 回の移動,
  • 4行は 1回の移動,つまり,$H(1)$
  • 5行は $H(n-1)$回の移動を出力します。

従って, $H(1)=1, n >1$ のとき,

$$ H(n)=H(n-1)+1+H(n-1) $$

となる。

この漸化式は, $H(1)=1, n>1, H(0)=0$ のとき,

$$ H(n) = 2 \cdot H(n-1) + 1 \\ H(n) + 1 = 2 \cdot H(n-1) + 2 \\ H(n)+1 = 2 \cdot (H(n-1)+1) $$$$ \{H(1)+1 = 2, 2(H(1)+1), 2^2 (H(1)+1), \cdots \} $$

から初項$H(1)+1 = 2$, 公比$r=2$ の等比数列より,

$$ H(n)+1 = (H(1)+1) \cdot 2^{n-1} \\ = 2^n\\ $$

よって,

$$ H(n)=2^n - 1 $$

となる.

メルセンヌ素数 https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0 と一致する.

In [7]:
def H(n):
    n_int64 = sp.array(n, dtype=sp.int64)
    return sp.power(2, n_int64) - 1
 

この数値はかなり大きい。

例えば,

  • $H(10)=1023$
  • $H(40)=1099511627775$

となる。

In [8]:
H(10), H(40) 
Out[8]:
(1023, 1099511627775)
In [9]:
%matplotlib inline

n_ar = sp.arange(1, 40+1, 1)
plt.plot(n_ar, H(n_ar))
plt.yscale("log")
plt.xlabel("n")
plt.ylabel("move_num")
plt.grid()
plt.show()
 
移動回数ののグラフ
In [10]:
H(n_ar)
Out[10]:
array([            1,             3,             7,            15,
                  31,            63,           127,           255,
                 511,          1023,          2047,          4095,
                8191,         16383,         32767,         65535,
              131071,        262143,        524287,       1048575,
             2097151,       4194303,       8388607,      16777215,
            33554431,      67108863,     134217727,     268435455,
           536870911,    1073741823,    2147483647,    4294967295,
          8589934591,   17179869183,   34359738367,   68719476735,
        137438953471,  274877906943,  549755813887, 1099511627775], dtype=int64)
 

再帰(繰り返し)でできるか

 
Hanoi(3, f, w, d)
{
    Hanoi(2, f, d, w)
    {
        Hanoi(1, f, w, d)
        {
           print(1: f -> d)
        }
        print(2: f -> w)
        Hanoi(1, d, f, w)
        {
            print(1: d -> w)
        }
    }

    print(3: f -> d)

    Hanoi(2, w, f, d)
    {
        Hanoi(1, w, d, f)
        {
            print(1: w -> f)
        }
        print(2: w -> d)
        Hanoi(1, f, w, d)
        {
            print(1: f -> d)
        }
    }
}

を参考にスタックとwhileループを利用して実装する.

In [11]:
def hanoi_ite(n, f, w, d):
    stack = []
    # now
    (N, From, Work, Dist) = (n, f, w, d)
    stack.append((N, From, Work, Dist))
    
    while stack:
        while N-1 >= 1:
            # N-1段を F -> W
            stack.append((N-1, From, Dist, Work))
            (N, From, Work, Dist) = stack[-1]
        
        # N段を F -> D
        p = stack.pop()
        print(p)
        (N, From, Work, Dist) = p
        
        if N-1 >= 1: 
            # N-1段を W -> D
            stack.append((N-1, Work, From, Dist))
            (N, From, Work, Dist) = stack[-1]
In [12]:
hanoi_ite(5, "A", "B", "C")
 
(1, 'A', 'B', 'C')
(2, 'A', 'C', 'B')
(1, 'C', 'A', 'B')
(3, 'A', 'B', 'C')
(1, 'B', 'C', 'A')
(2, 'B', 'A', 'C')
(1, 'A', 'B', 'C')
(4, 'A', 'C', 'B')
(1, 'C', 'A', 'B')
(2, 'C', 'B', 'A')
(1, 'B', 'C', 'A')
(3, 'C', 'A', 'B')
(1, 'A', 'B', 'C')
(2, 'A', 'C', 'B')
(1, 'C', 'A', 'B')
(5, 'A', 'B', 'C')
(1, 'B', 'C', 'A')
(2, 'B', 'A', 'C')
(1, 'A', 'B', 'C')
(3, 'B', 'C', 'A')
(1, 'C', 'A', 'B')
(2, 'C', 'B', 'A')
(1, 'B', 'C', 'A')
(4, 'B', 'A', 'C')
(1, 'A', 'B', 'C')
(2, 'A', 'C', 'B')
(1, 'C', 'A', 'B')
(3, 'A', 'B', 'C')
(1, 'B', 'C', 'A')
(2, 'B', 'A', 'C')
(1, 'A', 'B', 'C')
 

時間を計測 再帰 vs 非再帰

In [24]:
def hanoi_ite(n, f, w, d):
    stack = []
    # now
    (N, From, Work, Dist) = (n, f, w, d)
    stack.append((N, From, Work, Dist))
    
    while stack:
        while N-1 >= 1:
            # N-1段を F -> W
            stack.append((N-1, From, Dist, Work))
            (N, From, Work, Dist) = stack[-1]
        
        # N段を F -> D
        p = stack.pop()
#         print(p)
        (N, From, Work, Dist) = p
        
        if N-1 >= 1: 
            # N-1段を W -> D
            stack.append((N-1, Work, From, Dist))
            (N, From, Work, Dist) = stack[-1]

def hanoi(n:int, start:str, partition:str, goal:str):
    '''
    n段をstart->goalへ移動.
    partitionは途中の移動に使用
    '''
    if n >= 1:
        # 上に乗っているn-1段を一旦移動
        hanoi(n-1, start, goal, partition)
#         print("{} 段目を {} -> {} ".format(n, start, goal))
        # 一旦移動したn-1段をgoalへ
        hanoi(n-1, partition, start, goal)
        
import time
n = 20
time_rec = []
time_ite = []

def get_time(func, args_tuple, loop=5):
    times = []
    for i in sp.arange(loop):
        s = time.time()
        func(*args_tuple)
        e = time.time()
        times.append(e - s)
    return sp.mean(times)

for i in sp.arange(1, n+1, 1):
    time_rec.append(get_time(hanoi, (i, "A", "B", "C")))  
    time_ite.append(get_time(hanoi_ite, (i, "A", "B", "C")))

plt.plot(sp.arange(1, n+1, 1), time_rec, label="recursive")
plt.plot(sp.arange(1, n+1, 1), time_ite, label="non-recursive")
plt.xlabel("disk num")
plt.ylabel("time [s]")
plt.suptitle("measuring time: recursive vs non-recursive", y=0)
plt.legend(loc=2)
plt.grid()
plt.tight_layout()
plt.show()
 
再帰vs非再帰のの計測時間

通常, 再帰関数では関数呼び出しのオーバーヘッドがあり, 非再帰のほうが実行時間が短くなる傾向にある. しかし,結果では非再帰のほうが実行時間が長くなった.

おそらく,非再帰で使用している(スタックのように使用している)リストの操作がボトルネック担っていると考えられる.

参考

広告を非表示にする