アルゴリズム - 循環検出 - フロイドの\(\rho\)アルゴリズム

問題概要

適当な有限集合 \(X\) について, \(x_0 \in X\) と \(f \colon X \to X\) によって数列 \[\{ x_0, x_i \mid x_{i+1} = f(x_i), i=1,2,\ldots \}\] を構成する.

ここで \(X\) を有限集合としたので, \(i \leq |X|\) の範囲で同じ値が重複することが必ずある（鳩の巣原理）. 一度 \(x_i = x_j (i \ne j)\) であるとき, それ以降 \(x_{i+m} = x_{j+m}\) であるので数列はループする.

このことは次のように言い直せる. ループに入るまでの長さを \(\lambda\), ループの周期長を \(\mu\) として \[\forall n, k \in \mathbb N, x_{\lambda + n} = x_{\lambda + n + k\mu} ~~\cdots\cdots(\ast)\]

\(x_0, f\) が与えられるときに, この \(\lambda, \mu\) を探すのがフロイドの\(\rho\)アルゴリズムである.

アルゴリズム詳細

適当な \(i\) を始点に各ステップで \(i\) を \(1\) または \(2\) ずつ進めるようなイテレータを2つ並行して動かしていくようなことを考える.

フェーズ 1

初めに \(i=0\) を始点に各ステップで \(1\) 及び \(2\) 進めるイテレータを2つ用意する. これをちょうど \(m_1\) ステップ進めたときに初めて同じ数を指しているとする. すなわち \[x_{m_1} = x_{2m_1}\] になったとする. このことからある \(n,k\) で

  • \(m_1 = \lambda + n\)
  • \(2m_1 = \lambda + n + k \mu\)

を満たす. このことからは \[m_1 = k \mu\] を得る.

フェーズ 2

次に, \(i=0\) から \(1\) ずつ進めるイテレータと, \(i=m_1\) から \(1\) ずつ進めるイテレータの2つを用意する. （後者は先程のものを使いまわせばよい.） そしてやはり \(m_2\) ステップ進めたときに初めて同じ数を指していると \[x_{m_2} = x_{m_1 + m_2}\] が成り立つ. ここで \(m_1 = k\mu\) であった: \[x_{m_2} = x_{m_2 + k\mu}\] 従って, \(m_2 \geq \lambda\) であればこの等式は常に成り立つ. \(m_2\) が「初めて同じ数を指す」ときのステップ数であるとしたことから \[m_2 = \lambda\] を得る.

フェーズ 3

最後に, \(i=\lambda\) から \(1\) ずつ進めるイテレータと \(i=\lambda\) から \(2\) ずつ進めるイテレータの2つを並行して進める. そして今度は \(m_3\) ステップ後に初めて同じ数を指したとする. \[x_{\lambda + m_3} = x_{\lambda + 2 m_3}\] さて \(m_3 = \mu\) とすればこれが成立するのは明らかである. \(m_3 < \mu\) では成り立たないこともすぐに確認できる. そこからやはり \[m_3 = \mu\] を得る.

計算量

時間は \(O(\lambda + \mu)\), 空間は \(O(1)\).

実装例