フロイドの循環検出法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

フロイドの循環検出法（英: Floyd's cycle-finding algorithm）とは、任意の数列に出現する循環を検出するアルゴリズムである。任意の数列とは、例えばデータ構造でもよいし、O(1)領域でその場で生成される数列（特にグラフや擬似乱数列）でもよい。ロバート・フロイドが1967年に発明した^[1]。ウサギとカメのアルゴリズムと呼ばれることもある。

グラフの最短経路問題を解くワーシャル-フロイド法とは異なるので注意されたい。

[編集] アルゴリズム

以下では、擬似乱数列を対象としている。フロイドの循環検出法は擬似乱数発生器の分析に重要であるし、ポラード・ロー素因数分解法でもそれが重要となるためである。擬似乱数は最初は無作為だが、ある時点から循環して同じ数列を繰り返すようになる。

まず、擬似乱数函数 f を次のように表す。

$f\colon S\mapsto S$

ここで、S は元の個数（cardinality）が n の有限集合である。数列 a_i は次のように定義される。

a i + 1 = f (a i)

明らかに、このような数列は、擬似乱数函数がとりうる値が n 種類しかないので、最高でも n 回繰り返すまでに循環を発生させる。循環の長さを知る素朴な方法は、数列をいちいち記録していって、並びが同じ部分を総当り的に探すことである。このとき必要な記憶領域は O(μ + λ) であり、μ は循環部分の長さ、λ は循環していない部分の長さである。

ここで注目すべきは、2つの要素に以下の関係が成り立つとき

a i = a j

その間の要素数 |i − j| は循環の長さの整数倍となる。なぜなら、循環数列の定義から、次が成り立つからである。

a λ + m = a λ + m + k μ .

この2つの要素のインデックスの差は kμ であり、循環部分の長さの整数倍となっている。フロイドの循環検出法は、2つのインデックス変数を並行して増やしていき（ただし、一方はもう一方の2倍の速度で増やす）、このように一致する場合を探すのである。すなわち一方のインデックスを1ずつ増やし、もう一方を2ずつ増やしていく。すると、ある時点で次のようになる。

a m = a 2 m

ここで、2m − m = m を割り切れる任意の数が循環の長さとなる（循環に入る前の部分 λ は、λ > m - μ でかつ λ <= m の任意の値と考えられる）。

一致が見つかったら、λ を決定する。これは、一方は $a m$ から、もう一方は数列の最初から値を求めて比較していくことで分かる（共に1つずつ進めて行く）。 $a m$ は循環の先頭地点から m - λ ステップ進んだ地点であり、そこから λ ステップ進むと循環の先頭地点からは m ステップの地点である。m は μ の整数倍であるから、それはつまり、循環の先頭地点に他ならない。従って、&labmda; ステップ後に両者は循環の先頭地点に到達し、そこまでの繰り返し回数が λ となる。

λ が分かれば、巡回の開始地点から第一段階と同じアルゴリズムを繰り返すことで μ を見つけることができる。この場合、λ が 0 なので、新たな m は μ の整数倍ではなく、μ そのものであることが保証される。

[編集] アルゴリズムの可視化

このアルゴリズムを可視化する最善の方法は、数列の図を作ることである。それはちょうどギリシア文字の ρ に似ている。数列は伸びた尻尾の先から始まり、上に登っていき、時計周りに回る。アルゴリズムによれば、右図の場合、6回目の繰り返しで a₆ の位置で一致が検出される。そのまま続けると、さらに6回繰り返したときに、同じ要素で再び一致する。巡回の長さも 6 であるため、その後も常に同じ結果となる。