『Pythonで体験してわかるアルゴリズムとデータ構造』メモその7/ハノイの崇高なる力を経験する

『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。

Pythonで体験してわかるアルゴリズムとデータ構造

第7章 問題に適した設計法とは

この章のゴールは 与えられた問題に、分割統治法と、動的計画法のどちらが向いているかを判断できるようになる

書籍中ではハノイの塔問題、最短経路の数え上げ問題を例にとって説明している。

ハノイの塔について

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

n枚の円盤すべてを移動させるには最低 2ⁿ − 1 回の手数がかかる。

解法に再帰的アルゴリズムが有効な問題として有名であり、プログラミングにおける再帰的呼出しの例題としてもよく用いられる。ただし支配数がメルセンヌ数なので、同じく再帰の例題として多用されるフィボナッチ数同様、再帰をストレートに実装するととんでもない事態を生む例でもある。 ハノイの塔 - Wikipedia

パズルのひとつで、動画で見ると分かりやすい。
www.youtube.com

こんな感じで、必ず大-中-小（大-小）の順番で並ばなければならないゲーム。

遊戯王プレイヤーはおそらくこのワードを聞くと
(C)高橋和希 スタジオ・ダイス／集英社・テレビ東京・ＮＡＳ

これを思い出すのかなと。
俺はもうこのイメージしかない。

今回はミラフォの話でも、王宮のお触れの話でもなく、アルゴリズムの話。

何故最低2ⁿ -1なのか

以下動画を見るとイメージがつかみやすい。

www.youtube.com

円盤が3個あるとして、大きく「1と2の固まり」と「3個目」で分割する。

「1と2の固まり」は3回移動することで1個目の下に2個目が来ることが分かっているので、それに加えて3個目として1回移動させてあげればよい。

ただそれだと、1個目の下に2個目、2個目の下に3個目が来ないので、「1と2の固まり」をもう一度移動してあげる必要がある。

3回＋1回＋3回＝7回。7回移動すると1個目の下に2個目、2個目の下に3個目が来ることになる。

漸化式で考えると、

「1と2の固まり」をn、「3個目」をn+1とした場合  
[tex:a_{n+1} = 2a_{n+1}]  
（3個移動したいのであれば、2×3+1）

[tex: a_{1} = 1]とした場合に、漸化式を解くと、  
[tex: a_{n+1} + 1 = 2( a_{n+1} )] となる。

数列 [tex: a_{n+1} = 1] は、初稿がa1=2、公比が2の等比数列なので、2ⁿ - 1になる。

なんだか難しいことを書いていて正直俺もそんなによくわかってないが、重要なのは上の大きく「1と2の固まり」と「3個目」で分けてしまうということ。

実装

ハノイの塔は、再帰の典型的なパターンとのことで、再帰といえば分割統治法。

ということで分割統治法の考え方のトップダウンから考えた場合の処理を書いてみる。

def move(k,start,yobi,end):
    print("")
    print("今{}の処理だよ".format(k))

    if k >= 2:
        print("{}のa処理に入るよ".format(k-1))
        move(k-1, start, end, yobi)
    print("")
    print("今{}の処理だよ".format(k))
    print("{}を{}から{}軸へ移動".format(k,start, end))
    if k >= 2:
        print("b処理に入るよ")
        move(k-1, yobi,start, end)

move(3,1,2,3)

今3の処理だよ
2のa処理に入るよ

今2の処理だよ
1のa処理に入るよ

今1の処理だよ

今1の処理だよ
1を1から3軸へ移動

今2の処理だよ
2を1から2軸へ移動
b処理に入るよ

今1の処理だよ

今1の処理だよ
1を3から2軸へ移動

今3の処理だよ
3を1から3軸へ移動
b処理に入るよ

今2の処理だよ
1のa処理に入るよ

今1の処理だよ

今1の処理だよ
1を2から1軸へ移動

今2の処理だよ
2を2から3軸へ移動
b処理に入るよ

今1の処理だよ

今1の処理だよ
1を1から3軸へ移動