フロイドの循環検出法

ウィキペディア

フロイドの循環検出法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/03 03:49 UTC 版)

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

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

アルゴリズム

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

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

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

関数 $f$

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

性能

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

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

バリエーション

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

その他の循環検出法

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

脚注

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

外部リンク

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