フロイドの循環検出法

フロイドの循環検出法（英: Floyd's cycle-finding algorithm）とは、任意の数列に出現する循環を検出するアルゴリズムである。任意の数列とは、例えば擬似乱数列などであるが、単方向連結リストとみなせる構造のようなもののループ検出にも適用できる。ロバート・フロイドが1967年に発明した^[1]。「速く動く」と「遅く動く」という2種類のインデックス（ポインタ）を使うことから、ウサギとカメのアルゴリズムといった愛称もある。

グラフの最短経路問題を解くワーシャル–フロイド法とは（同じ発案者に由来するので同じ名前がある、という点以外は）無関係である。

アルゴリズム

単方向連結リストのループ検出なども典型的なのであるが、形式的（フォーマル）な説明には数列のほうが向いているのでここでは擬似乱数列生成器の例で説明する。ポラード・ロー素因数分解法などで擬似乱数列生成器の分析が重要なため、といったこともある。

通常、擬似乱数列生成器は決定的な動作をするのであるから、生成器の内部状態がもし以前と同一になれば、そこから先はその以前と同一の列が再生成される。一般に内部状態の数は有限であるから^[2]、いつかは鳩の巣原理によって、以前に出現したどこかからと同一の列が再現されるはずである。この時「どこかから」というのが曲者で、調査を始めた列の、必ず先頭からであるとは限らないのが難しい所である。例えば理想的な擬似乱数列生成器であれば全ての内部状態を経てから必ず最初に戻るが（そして、そのようになる条件が明らかな生成器の族もあるが）、数列を生成する任意の関数にそのような期待はできない。

ここでは具体的な擬似乱数列生成器として、線形合同法のような、通常、内部状態をそのまま出力とする擬似乱数列生成器を考える（もし、内部状態のごく一部のみが出力されるような擬似乱数列生成器を対象とする場合は、当然のことだが、出力される列ではなく、内部状態の列について考えなければならない）。

関数 $f$ を擬似乱数列生成器とする、次のような擬似乱数列 $a_{i}$ を考える。

a_{i+1}=f(a_{i})

ナイーブな方法の一例は、数列をいちいち記録していって、並びが同じ部分を総当り的に探すことである。このとき必要な記憶領域は $O(\mu +\lambda )$ であり、 $\mu$ は循環部分の長さ、 $\lambda$ は循環していない部分の長さである。

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

a_{i}=a_{j}

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

a_{\lambda +m}=a_{\lambda +m+k\mu }.

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

a_{m}=a_{2m}

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

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

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

アルゴリズムの可視化

このアルゴリズムを可視化する最善の方法は、単方向連結リストのループ検出の場合の図（グラフ（ネットワーク）構造）を作ることである。それはちょうどギリシア文字の $\rho$ に似ている。列は、 $\rho$ の字の伸びた尻尾の先から始まり、上に登っていき、時計周りに回る。具体的には右図の場合、アルゴリズム中の6回目の繰り返しで $a_{6}$ の位置で一致が検出される。そのまま続けると、さらに6回繰り返したときに、同じ要素で再び一致する。巡回の長さも 6 であるため、その後も常に同じ結果となる。

性能

このアルゴリズムの第一段階は、最小で $\max(\lambda ,\mu )$ 、最大で $\lambda +\mu$ の比較演算をする必要がある。循環のスタート地点を探すには $\lambda$ 回の比較が必要である。循環の長さを知るには $\mu$ 回の比較が必要であるが、 $m$ が $\mu$ の整数倍であることを利用することで節約が可能である。

このアルゴリズムは $O(1)$ の領域を使用する。

バリエーション

フロイドの循環検出法のバリエーションとして最も知られているのは、擬似乱数列を使った素因数分解アルゴリズムであるポラード・ロー素因数分解法であろう。また、フロイドの循環検出法に基づいて離散対数を計算するアルゴリズムもある。

その他の循環検出法

フロイドのアルゴリズム以外の循環検出法のひとつに、ゴスパーによるものがある（空間計算量が $O(1)$ ではない）。詳細は英語版 en:Cycle detection#Gosper's algorithm などを参照のこと。

脚注

^ Floyd, R.W. (10 1967). “Non-deterministic Algorithms”. J. ACM: pp. 636-644.
^ 理論的には、たとえば円周率を計算し続けるプログラムは、無限の内部状態を持つ擬似乱数列生成器とみなせるが、ここではそういったものは考えない（円周率の小数展開が本当に乱数的かはさておき（まだ決定的な理論は無い））。

外部リンク

Literate implementations of Floyd's cycle-finding algorithm in various languages on LiteratePrograms

[1] Floyd, R.W. (10 1967). “Non-deterministic Algorithms”. J. ACM: pp. 636-644.

[2] 理論的には、たとえば円周率を計算し続けるプログラムは、無限の内部状態を持つ擬似乱数列生成器とみなせるが、ここではそういったものは考えない（円周率の小数展開が本当に乱数的かはさておき（まだ決定的な理論は無い））。

[1]

[2]