アルゴリズム - 循環検出 - フロイドの\(\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)\).

実装例

/// Returns (lambda, mu), Steps before Loop, Length of Loop
pub fn rho<X: Eq + Copy + std::fmt::Debug, F: Fn(X) -> X>(initial_state: X, step: F) -> (u64, u64) {
    let mut x1 = initial_state;
    let mut x2 = initial_state;
    loop {
        x1 = step(x1);
        x2 = step(x2);
        x2 = step(x2);
        if x1 == x2 {
            break;
        }
    }
    let mut lambda = 0;
    let mut x2 = initial_state;
    while x1 != x2 {
        lambda += 1;
        x1 = step(x1);
        x2 = step(x2);
    }
    let mut mu = 0;
    while mu == 0 || x1 != x2 {
        mu += 1;
        x1 = step(x1);
        x2 = step(x2);
        x2 = step(x2);
    }
    (lambda, mu)
}

#[cfg(test)]
mod test_rho {

    use crate::algorithm::rho::*;

    #[test]
    fn test1() {
        // 2 -> 4 -> 6 -> 6 -> ...
        let (lambda, mu) = rho(2, |x| (x * x) % 10);
        assert_eq!((lambda, mu), (2, 1));
    }

    #[test]
    fn test_const() {
        // 1 -> 1 -> ...
        let (lambda, mu) = rho(1, |x| x);
        assert_eq!((lambda, mu), (0, 1));
    }

    #[test]
    fn test2() {
        // 1 -> 0 -> 0 -> ...
        let (lambda, mu) = rho(1, |x| x % 1);
        assert_eq!((lambda, mu), (1, 1));
    }

    #[test]
    fn test3() {
        // 0 -> 1 -> 2 -> 0 -> 1 -> 2 -> 0 -> ...
        let (lambda, mu) = rho(0, |x| (x + 1) % 3);
        assert_eq!((lambda, mu), (0, 3));
    }

    #[test]
    fn test4() {
        // 3 -> 1 -> 2 -> 0 -> 1 -> 2 -> 0 -> ...
        let (lambda, mu) = rho(3, |x| (x + 1) % 3);
        assert_eq!((lambda, mu), (1, 3));
    }

    #[test]
    fn test5() {
        // 0 -> 1 -> 0 -> 1
        let (lambda, mu) = rho(2, |x| 1 - x);
        assert_eq!((lambda, mu), (0, 2));
    }
}