Go to Qiita Advent Calendar 2024 Top
LoginSignup
16
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

データ構造とアルゴリズムAdvent Calendar 2020

Day 1
@SaitoTsutomu(Tsutomu Saito)

k本のハノイの塔の動かし方（Python版）

Last updated at Posted at 2020-11-30

本記事は、「データ構造とアルゴリズム Advent Calendar 2020」 1日目の記事です。
2日目の記事は @okateim 氏による「「4人のロシア人の方法」を用いた編集距離計算の高速化」です。

お題

「ハノイの塔」で塔の本数をk本に拡張せよ

参考：ハノイの塔 - Wikipedia

塔の数が3本のとき

ディスクの枚数をnとします。
塔が3本のときの最小手数は、$2^n - 1$であることがよく知られています。
また、そのときの動かし方は1通りに決まります。
この動かし方のコードは再起関数で次のように書けます。

def hanoi(n, pos):
    if n == 1:
        yield pos[0], pos[-1]
        return
    yield from hanoi(n - 1, pos[:1] + pos[2:] + pos[1:2])
    yield from hanoi(1, pos[:1] + pos[2:-1] + pos[-1:])
    yield from hanoi(n - 1, pos[1:-1] + [pos[0], pos[-1]])

コードの解説

hanoi(n, pos)は、「どの塔からどの塔に移動するか」を返すジェネレーター（forで使える関数）です。引数は以下の通りです。

  • n：ディスクの枚数。
  • pos：利用可能な塔のインデックスのリスト。このリストの先頭の塔のn枚のディスクを最後の塔に移動します。

4枚のディスクを塔0から塔2へ動かす方法は、下記のように書きます。

for i, j in hanoi(4, [0, 1, 2]):
    print(f'{i} -> {j}')

出力は以下のようになります（改行を変えてます）。

0 -> 1  0 -> 2  1 -> 2  0 -> 1  2 -> 0
2 -> 1  0 -> 1  0 -> 2  1 -> 2  1 -> 0
2 -> 0  1 -> 2  0 -> 1  0 -> 2  1 -> 2

ディスクが1枚のときは、「移動元、移動先」を返して終了します。

ディスクが2枚以上のときは、以下を実行します。

    yield from hanoi(n - 1, pos[:1] + pos[2:] + pos[1:2])
    yield from hanoi(1, pos[:1] + pos[2:-1] + pos[-1:])
    yield from hanoi(n - 1, pos[1:-1] + [pos[0], pos[-1]])

上記は、わかりにくいですが下記の処理です。

  • ステップ1）pos[0]からpos[1]にn - 1枚移動
  • ステップ2）pos[0]からpos[-1]に1枚移動
  • ステップ3）pos[1]からpos[-1]にn - 1枚移動

簡単に説明します。
pos[0]にある最下段のディスクは、その上にあるn - 1枚のディスクをどかさないと移動できません。
そこで、ステップ1でn - 1枚どけます。ステップ2で最下段のディスクを動かし、ステップ3で残ったディスクを動かします。

塔の数がk本のときの方針

しばらく考えましたが、どうすればよいかわかりませんでした。
仕方がないので、考えやすいように下記を仮定することにしました。

命題

n枚をk本で動かしたいとき、以下の3ステップで最短手数で動かせる

  • m枚を別の塔にどかす
  • 下に残ったn - m枚を移動先に動かす
  • 残りm枚を移動先に動かす

この命題は証明できていませんが、結果はうまくいっているようです。
mは、後で求めます。

最短手数

n枚をk本で動かすときの最短手数の数式はわかりませんでした。
しかし、動的最適化で以下のように計算できます。

from functools import lru_cache

@lru_cache(maxsize=1024)
def nmove(n, k):
    k = min(n + 1, k)
    if k == 2:
        return 1 if n == 1 else float("inf")
    elif k == 3:
        return 2 ** n - 1
    elif k == n + 1:
        return 2 * n - 1
    return min(nmove(i, k) * 2 + nmove(n - i, k - 1) for i in range(1, n))

解説

  • 塔の本数がn + 1を超えていても使わない塔がでてきます。そこで、塔の数は無駄がないようにk = min(n + 1, k)とします。これで無駄な計算が減ります。
  • k == 2のとき
    • ディスクが1枚なら1回で移動できます。
    • ディスクが2枚以上なら移動できません。移動回数として∞（float("inf")）を返します。
  • k == 3のときは、2 ** n - 1です。この処理はなくても動きますが、高速になります。
  • k == n + 1のときは、2 * n - 1です。これは各ディスクを空いている塔に退避すれば良いからです。
  • それ以外のときは、先ほどの命題を使ってしらみつぶしに調べます。

塔の数がk本のとき

命題を使えば以下のようになります。

def hanoi(n, pos):
    if n == 1:
        yield pos[0], pos[-1]
        return
    k = len(pos)
    m = min((nmove(i, k) * 2 + nmove(n - i, k - 1), i) for i in range(1, n))[1]
    yield from hanoi(m, pos[:1] + pos[2:] + pos[1:2])
    yield from hanoi(n - m, pos[:1] + pos[2:-1] + pos[-1:])
    yield from hanoi(m, pos[1:-1] + [pos[0], pos[-1]])

塔が3本のときにステップ1でn - 1本移動していたのが、m本の移動に変わっただけで、ほぼ同じコードになっています。
最短手数になるmも、nmoveを使えばしらみつぶしで求められます。

全コード

4枚のディスクを4本の塔で動かすコードは以下のようになります。

from functools import lru_cache

@lru_cache(maxsize=1024)
def nmove(n, k):
    k = min(n + 1, k)
    if k == 2:
        return 1 if n == 1 else float("inf")
    elif k == 3:
        return 2 ** n - 1
    elif k == n + 1:
        return 2 * n - 1
    return min(nmove(i, k) * 2 + nmove(n - i, k - 1) for i in range(1, n))

def hanoi(n, pos):
    if n == 1:
        yield pos[0], pos[-1]
        return
    k = len(pos)
    m = min((nmove(i, k) * 2 + nmove(n - i, k - 1), i) for i in range(1, n))[1]
    yield from hanoi(m, pos[:1] + pos[2:] + pos[1:2])
    yield from hanoi(n - m, pos[:1] + pos[2:-1] + pos[-1:])
    yield from hanoi(m, pos[1:-1] + [pos[0], pos[-1]])

for i, j in hanoi(4, [0, 1, 2, 3]):
    print(f'{i} -> {j}')

出力は以下のようになります（改行を変えてます）。

0 -> 1  0 -> 3  0 -> 2  3 -> 2  0 -> 3
2 -> 0  2 -> 3  0 -> 3  1 -> 3

可視化

塔の番号だけだとあっているかわかりにくいですね。
可視化しました。

$ pip install k-peg-hanoi
$ hanoi 4 4

   =
  ===
 =====
=======
0------------------------------

  ===
 =====
=======    =
1------------------------------

 =====
=======    =              ===
2------------------------------

=======    =     =====    ===
3------------------------------

                  ===
=======    =     =====
4------------------------------

                  ===
           =     =====  =======
5------------------------------

  ===      =     =====  =======
6------------------------------

                         =====
  ===      =            =======
7------------------------------

                          ===
                         =====
           =            =======
8------------------------------

                           =
                          ===
                         =====
                        =======
9------------------------------

最短手数の表

k\n 6 7 8 9 10
3 63 127 255 511 1023
4 17 25 33 41 49
5 15 19 23 27 31
6 13 17 21 25 29
7 11 15 19 23 27
8 11 13 17 21 25

以下で作成しました。

print("k\\n|6|7|8|9|10")
print(":--|:--|:--|:--|:--|:--|")
for k in range(3, 9):
    print(k, end='|')
    for n in range(6, 11):
        print(nmove(n, k), end='|')
    print()
16
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
16
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?