ハノイの塔アルゴリズム

Question

def hanoi(n, from, to, via)
if n == 1
puts "#{from} から #{to} へ移す"
else
hanoi(n - 1, from, via, to)
puts "#{from} から #{to} へ移す"
hanoi(n - 1, via, to, from)
end
end

hanoi(3, :A, :B, :C)

この再帰プログラムの処理過程を誰か教えてくれませんか？

結果。円盤が 3枚の場合だと

A から B へ移す
A から C へ移す
B から C へ移す
A から B へ移す
C から A へ移す
C から B へ移す
A から B へ移す

こうです
引数の順序がコロコロ変わるんで頭が混乱してます

追記
わかりやすい回答ありがとございます。
ハノイの塔はアニメーション見てるので理解してます。
私が混乱してるのは引数の代入に関してです。
3枚だと仮定して7行目のhanoi(n - 1, via, to, from)でCにある二枚がBに移る必要があるのでこれには引数として
hanoi(n - 1, C, B, A)でいいと思うのですがこのメソッドの処理過程が真下に書いてないので混乱してます
まあおそらく1行目のメソッドであるdef hanoi(n, from, to, via)に戻るだけだと思うのですがこの場合は7行目のn - 1, C, B, Aを順番に引数と代入すれだけなのかなとは思いましたが

Comments

[y_waiwai]

質問は編集できますんで、新たに質問たてないで修正追記しましょう

[Zuishin]

ここにソースと動画付きの詳しい説明があるので読んでください。
http://obelisk.hatenablog.com/entry/2018/01/17/120914

これでわからなければここで聞いて回答をもらってもわからないのではないですか？

[asm]

過去質問含めて質問を〆ない態度では、今後回答が貰えなくなると思いますよ

Answer 1

結果。円盤が 3枚の場合だと

A から B へ移す
A から C へ移す <-- 2)
B から C へ移す
A から B へ移す <-- 1) ここに注目
C から A へ移す
C から B へ移す <-- 3)
A から B へ移す

A から B にピラミッド３(n)枚を移す処理。真ん中の 1)に注目して、前半の処理と後半の処理に分けて考えます。

• A から B へ移す <-- 1) ここに注目

これは３(n)枚目の最後の円盤を A から B へ移す処理。その時に、どうなっていなければならないか。

• 前半の処理、A から経由する柱 C へ２(n-1)枚のピラミッドが移送されていなければならない。

大きな円盤の上に小さな円盤しか載せられないので２(n-1)枚のピラミッドができあがっている。
前半の移送処理の 2)をみればやはり２(n-1)枚目の最後の円盤の移送になっています。

• 後半の処理、経由する柱 C から B へ２(n-1)枚のピラミッドを移動する。

3)をみればやはり２(n-1)枚目の最後の円盤の移送になっています。

原則

• ピラミッドが１枚の時、直接移動する。(a->b)

a) 1枚を直接移動する。(a->b)

• ピラミッドが２枚以上の時、移動は間接的に行う。(a->c,a->b,c->b)

a) まずピラミッドn-1枚を中間の柱に移動する。(a->c)
b) 最後の1枚を直接移動する。(a->b)
c) 中間の柱から目的の柱にピラミッドn-1枚を移動する。(c->b)

参考

『問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考』 S. Devadas 2018 オライリージャパン
ハノイの塔の解法が載っているので立ち読みしてください。

『メタマジック・ゲーム―科学と芸術のジグソーパズル』 ダグラス・R. ホフスタッター 2005 白揚社
LISPを使うハノイの塔プログラムの紹介。円盤 3枚の解説も載っているので立ち読みしてください。

『コンピュータの数学』 ロナルド・L. グレアム、オーレン パタシュニク、ドナルド・E. クヌース 1993 共立出版
第1ページにハノイの塔の計算量の漸化式の解説があります。

追記

表示からわかること
中点にあたる移送を見れば、ピラミッドがどこに移動するのかが、わかります。

• 1. n ピラミッドは、A->B へ移動
• 1. n-1 ピラミッドは、A->C へ移動
• 1. n-1 ピラミッドは、C->B へ移動

再帰の意味
再帰するのは、問題を小さな部分問題に分割して解くためです。再帰する都度、n, n-1, n-2, ... , 1 と問題が小さくなり、1 のとき再帰せずリターンします。ネストした再帰がすべてリターンすると、部分問題がすべて解かれ、問題全体が解かれたことになります。再帰の動作がわかりづらければシーケンス図を書きましょう。表でもよい。縦に処理の流れ、横に再帰のネストごとの処理を畫いてください。

追記（再帰呼出のトレース）

hanoi(n - 1, C, B, A)でいいと思うのですがこのメソッドの処理過程が真下に書いてないので混乱してます

コメントの内容から「ハノイの塔」の問題ではなく、それ以前の「再帰呼出し」が理解できていないと判断しました。トレースコードを示します。再帰を勉強してください。

再帰呼出トレース用コード
hanoi() の呼出/リターンを表示するための行を追加。

def hanoi(n, from, to, via)
  puts "hanoi(#{n}, #{from}, #{to}, #{via}) : enter"
  if n == 1
    puts "#{from} から #{to} へ移す"
  else
    hanoi(n - 1, from, via, to)
    puts "#{from} から #{to} へ移す"
    hanoi(n - 1, via, to, from)
  end
  puts "hanoi(#{n}, #{from}, #{to}, #{via}) : return"
end

hanoi(3, :A, :B, :C)

再帰呼出トレース
irbで実行した結果を編集しました。

hanoi(3, A, B, C) : enter
  hanoi(2, A, C, B) : enter <-- 前半の移動 (A->C)
    hanoi(1, A, B, C) : enter
      A から B へ移す   <-- この円盤は、この下で B->C に移動する
    hanoi(1, A, B, C) : return
    A から C へ移す     <-- 2) ２枚目（前半(n-1)最後の円盤）の移動
    hanoi(1, B, C, A) : enter
      B から C へ移す
    hanoi(1, B, C, A) : return
  hanoi(2, A, C, B) : return
  A から B へ移す     <-- 1) ３枚目（全体(n)最後の円盤）の移動
  hanoi(2, C, B, A) : enter  <-- 後半の移動 (C->B)
    hanoi(1, C, A, B) : enter
      C から A へ移す   <-- この円盤は、この下で A->B に移動する
    hanoi(1, C, A, B) : return
    C から B へ移す     <-- 3) ２枚目（後半(n-1)最後の円盤）の移動
    hanoi(1, A, B, C) : enter
      A から B へ移す
    hanoi(1, A, B, C) : return
  hanoi(2, C, B, A) : return
hanoi(3, A, B, C) : return
=> nil

追記（再帰呼出の解説）

** 再帰呼出の動作**

再帰呼出しとはメソッド(hanoi)の中から自分自身(hanoi)を呼ぶことです。これは、自分自身を呼ぶことを除けば、普通のメソッド呼出しと同じです。メソッド呼出しの動作は以下のとおり。

• def hanoiの(…)の括弧の中に記述されているのが引数です。n, from, to, viaです。
• 引数に値を設定（代入）してメソッドに渡すと引数のコピーが作られます。

呼ばれたメソッドはコピーの値しか見えません。

• 呼ばれたメソッドは引数の値を使って処理を実行します。

hanoi()では原則に従い n=1 かそれ以外 (n≠1) かで処理が異なります。

• 処理が終わってメソッドからリターンする時に引数のコピーは消滅します。

メソッド呼び出しの都度、異なる引数の値がコピーされるため異なる動作ができるのです。

再帰呼出はループではありませんが、再帰呼出することはループの繰り返しと同じことをします。再帰呼出ししなければループ終了と同じ。hanoi()では n=1 の時再帰しません。

Comments

[xebme]

ハノイの塔のアニメーションが公開されています。見て考えましょう。

[xebme]

図はイメージです。実際の動作はプログラミングを深く学べばわかるようになります。

Answer 2

xebme さんの説明で十分だとは思うのですが、puts が２度出てくるのが少し気になりました。

def hanoi(n, from = "A", to = "B", via = "C")
  return if n.zero?
  hanoi(n - 1, from, via, to)
  puts "#{from} => #{to}"
  hanoi(n - 1, via, to, from)
end

hanoi(3)

こうすると、もう少し単純になって分かりやすくなるでしょうか。
余計な初期値まで設定してしまいました。

Answer 3

プログラムを日本語にしてもわかりませんか？

塔ををAからBに、Cをワークに使って移動するためには、
まず、塔の一番下の円盤を除いた部分を、AからCに、Bをワークに使って移動し、
Aに残った一番下の円盤をBに異動して、
その後で、CからBに、Aをワークに使って移動する。

です。