"機械学習","信号解析","ディープラーニング"の勉強

HELLO CYBERNETICS

深層学習、機械学習、強化学習、信号処理、制御工学などをテーマに扱っていきます

世界の終焉とハノイの塔

 

 

f:id:s0sem0y:20170609233338j:plain

 

 ハノイの塔

ハノイの塔が完成すると世界が終焉を迎えると言われています。

インドのガンジス河の畔のヴァラナシ(ベナレス)に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さがの体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときにが64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている(移し変えのルールが後述)。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。 

ハノイの塔のルール

下記の画像のように、3本の棒があり、大きさの異なる円盤が大きい順に、1本の棒に積み重ねられています。

 

f:id:s0sem0y:20170609233520j:plain

 

これを下記のルールを守った上で他の棒に移し替えていきます。

  1. 大きい円盤の上に小さい円盤を積む(小さい円盤の上に大きい円盤はおけない)
  2. 一度に移動できる円盤は1つだけ
  3. 3本の棒以外の場所に円盤を置くことはできない。
  4. 一番右の棒に円盤を全て移す。

簡単な例題

円盤が1個の場合は、単純にそれを1回移動するだけで終わります。

なので円盤が2個の場合を考えましょう。

・初期状態

f:id:s0sem0y:20170609234110p:plain

・1回目の移動

f:id:s0sem0y:20170609234135p:plain

・2回目の移動

f:id:s0sem0y:20170609234201p:plain

・3回目の移動

f:id:s0sem0y:20170609234226p:plain

 

簡単に終わってしまいましたが雰囲気は理解できたでしょうか。

移動回数は3回です。

次には円盤を3個にしてみましょう。

 

円盤3個の問題

この手の問題は、数を少しずつ増やしていくと規則性が見えてきます。

 

・初期状態

f:id:s0sem0y:20170609234532p:plain

・1回目

f:id:s0sem0y:20170609234617p:plain

・2回目

f:id:s0sem0y:20170609234647p:plain

・3回目

f:id:s0sem0y:20170609234750p:plain

・4回目

f:id:s0sem0y:20170609234811p:plain

・5回目

f:id:s0sem0y:20170609234910p:plain

・6回目

f:id:s0sem0y:20170609234922p:plain

ここまで来ると、実は円盤が2個の時の問題と全く同じ条件になっています。

f:id:s0sem0y:20170609234043p:plain

円盤2個の問題では3回の移動で終了しています。

円盤3個の問題で6回目においては、「2つの円盤を移動する問題」としてみることができます。

f:id:s0sem0y:20170609234922p:plain

この段階では「緑と青の2個の円盤を移動する問題」となっています。赤の円盤は一番大きいので、これが移動できた時点で、1個円盤が少ない問題の結果をそのまま流用できます。

 

従って、移動回数は6回+3回で9回となります。

待ってください、本当にこれで良いのでしょうか。もっと早い方法は無かったのでしょうか?最初の青色の円盤を移動する際には、真ん中か右か、選択肢が2つあります。さっきとは違い方を選んで今一度試してみましょう。

 

・初期状態

f:id:s0sem0y:20170609234532p:plain

・1回目

f:id:s0sem0y:20170609235948p:plain

・2回目

f:id:s0sem0y:20170610000145p:plain

・3回目

f:id:s0sem0y:20170610000216p:plain

・4回目

f:id:s0sem0y:20170610000337p:plain

案の定もっと早く終わりました。ここまでこれば円盤2つの方法で移動ができますので、従って円盤3つですと4回+3回=7回で移動ができると分かりました。これより早い方法はありません。他のパターンも試してみてください。

 

しかし、これ以上数が増えてくると、自力で探しだすのは難しそうです。

 

規則性をみる

これから円盤の個数がn個としたときの、最小の移動回数をT_nと書きます。現在のところn=1,2,3について調べましたから

 

T_1=1

 

T_2=3

 

T_3=7

 

ということが分かっています。ハノイの塔の実際の問題はn=64ですから、T_{64}が知りたい値です。果てしなく遠いです。ここはT_4の値に当たりをつけて、T_nの値を予想したいところです。

 

T_2=2T_1+1

 

T_3=2T_2+1

 

という関係性があるように見えます。すると

 

T_4=2T_3+1=15

 

となるのでしょうか。たった3つのデータだけからこの規則だと断定するのは早計です。

 

論理的に考える

私達は3個の円盤を移動するときに、以下の段階まで辿り着けば、2個の円盤を移動する問題に帰着されることを見ました。

f:id:s0sem0y:20170610000337p:plain

一方で、その直前の状態はどうでしょうか。赤を移動し終わる前の状態です。

 

f:id:s0sem0y:20170610000216p:plain

さて、初期状態からこの状態に至るまでのことを考えてみると、これも「2個の円盤を移動する問題」と見ることができます。ただし、一番右の円盤に赤色を置きたいので、(真ん中に)2個の円盤を移す問題です。そのように捉えようとも、右の棒を中継地点として捉えれば、移動回数自体に影響を及ぼすものではありません。

 

つまりまとめると、3つの円盤を移動する際には、以下の初期状態から、

f:id:s0sem0y:20170609234532p:plain

2つの円盤を(真ん中の棒に)移動する操作を行い(T_2=3回移動)、

f:id:s0sem0y:20170610000216p:plain

赤色の円盤を右側に移動し(1回移動)

f:id:s0sem0y:20170609234922p:plain

再度2つの円盤を(右側の棒に)移動する操作を行い(T_2=3回移動)、

f:id:s0sem0y:20170610001940p:plain

合わせて2T_2+1回の操作によって移動が完了します。

これは円盤の数がn個であっても同じです。真ん中の棒に、一番下以外のn-1個の円盤をT_{n-1}回の操作を用いて移動し、1回の操作で最大の円盤を右側に移動し、T_{n-1}回の操作で真ん中に積まれた円盤を右側に移動します。

 

従って、

 

T_n = 2T_{n-1}+1

 

だと結論付けることができます。もしかしたらこれより早い方法を誰かが見つけるかもしれません。しかし、T_kというのはk個の円盤を移動する最小の移動方法です。

 

今、操作を追って来た通り、一番下の円盤を一番右側に移動するためには、その他の円盤が全て真ん中になければならず、最大の円盤を除く全ての円盤が真ん中の棒にあるためには、それが大きい順に積まれていなければなりません。

 

円盤n個ならば最初にn-1個を移動しなければならないというのは絶対であり、T_{n-1}n-1個をルールに従い移動させる最小の回数であり(それが具体的に何回かは知らなくとも)これより早い方法はありません。(棒が4本ならば、必ずしもn-1個を順番通りに並べる必要がないため、T_{n-1}の手数が不要になるでしょう)

 

世界の終焉はいつくるのか

漸化式として表現

T_{64} について知りたければ、以下の漸化式を解く必要があります。そのあとn=64を代入することで世界の終焉がいつ来るのか分かります。

 

T_1=1

 

T_{n+1} = 2T_{n}+1     (nは自然数)

 

非常に単純な形の漸化式なので以下のような変形で等比数列に持っていけます。

 

漸化式の解法

T_{n+1}+α = 2(T_n+α)としてしまえば、U_n=T_n+αと置くことで等比数列にできます。これを見計らって、

 

\displaystyle T_{n+1}+1=2(T_n+1)

 

U_n = T_n+1

 

と置いてしまいます。(ここ実際にはT_{n+1}+α = 2(T_n+α)としたいので、αを右辺に集めることでT_{n+1} = 2T_n+αと変形し、T_{n+1} = 2T_{n}+1 と比較したところでα=1だと求めます)

 

U_1 = T_1+1=2

 

U_{n+1}=2U_n

 

初項2、公比2の等比数列ですから

 

U_{n}=2^n

 

と求まり、T_n=U_n-1=2^n-1と分かりました。

 

世界の終焉

従って64個の円盤の移動回数は 

 

T_{64}=2^{64}-1=18,446,744,073,709,551,615

(1844京6744兆737億955万1615回)

 

です。一枚の移動に1秒掛かったと考えると、約5,845億年です。

しばらく世界の終焉はこなさそうです。

 

参考文献 

プログラマーならよく知る「ドナルド・E.クヌース」が自画自賛した書籍「CONCRETE MATHEMATICS」の日本語版「コンピュータの数学」(何だこの訳は)には上記のような面白い問題から始まり、離散数学の大部分がカバーされています。

コンピュータの数学

コンピュータの数学

  • 作者: ロナルド・L.グレアム,オーレンパタシュニク,ドナルド・E.クヌース,Ronald L. Graham,Oren Patashnik,Donald E. Knuth,有沢誠,萩野達也,安村通晃,石畑清
  • 出版社/メーカー: 共立出版
  • 発売日: 1993/08
  • メディア: 単行本
  • 購入: 5人 クリック: 224回
  • この商品を含むブログ (38件) を見る