うさぎとかめ ループ判定法

プログラミングのアルゴリズムの話です。この方法は自分で思いついたわけでなく、どこぞの本で学んだ形。どこぞの本が何かは忘れてしまった。「うさぎとかめ」ネーミングは元々でなく、いわいが名前をつけなおしたと記憶。「鮮やかなアルゴリズムだ」との印象。

a1=func(a0);
a2=func(a1);
a3=func(a2);
a4=func(a3);
a5=func(a4);
・・・・・

と状態が分岐のない一連になってるものに使います。
あるfuncは引数が同じなら返り値は同じ値をとります。

１連といっても例えば
(1) anとa0が同じだと環状になります。
(2)途中のanとamと同じならば、全体のグラフの形は「６」みたいな形になります。

(1)(2)はループになってますのでそれを判定するアルゴリズムがあってそれが「うさぎとかめ」です。
かめは道の上を１区間づつ進みます。
うさぎは道の上を２区間づつ進みます。

 kame=usagi=スタート地点;
 for(;;){
   kame=func(kame);
   usagi=func(func(usagi)));
   if(kame==usagi){
     おっとこれだとループってる。
   }
 }

本当は証明が要るが・・・
簡単にいうと、ループじゃないと「うさぎとかめ」の差は開くばかりで「うさぎとかめ」が同じ場所にくることはない。
でも道がループになってると周回遅れのかめにうさぎが追いつくことになり、うさぎが「かめやっぱり遅いな」と同じ場所にいることになります。

説明がだいぶ、はしょってありますがわかりますでしょうか？後で絵でも足すか？

さらにプログラミングの本当の実際にあてはめてみる。状態の記憶をusagiとkameの２個分だけもっていればよい。a0はいったか、a1はいったか、a2はいったか・・・・・と全部、覚えておく必要がないので、メモリー的にすっきり。

Comments

このアルゴリズムは目から鱗が落ちました。
状態をたくさん保存することなく、ループを判定できるとは驚きです。美しいアルゴリズムですね。

Posted by aret at 2005年05月05日 00:49

aretさん、お久しぶりw
パズコンのプログラムやってる人（コタニイシノサカイニシヤマタカシマ敬称略）に知ってるかどうかきいてみると面白いかも。

Posted by いわいまさか at 2005年05月05日 07:19

>知ってるかどうかきいてみると面白いかも。
そうですね。
すっきりしたアルゴリズムをみつけたときはパズルが解けたときのような爽快感がありますね。

Posted by aret at 2005年05月07日 20:58