algorithm - ブレント周期検出アルゴリズム

Question

誰でもブレントのサイクル検出アルゴリズムを手伝ってくれませんか。「λ と μ の両方よりも大きい 2 2^i の最小累乗を検索する」理由が正確にはわかりません。サイクルの検出で 2 のべき乗がどのように役割を果たしているか。フロイドのサイクル検出アルゴリズムと何らかの関係がありますか? 根本から掴めない。助けてください ！

Answer 1

この方法では、増加するステップ (1、2、4、8...) を使用して、できるだけ早くループ内に入ります。P = 2^k が λ と μ の両方よりも大きくなると、亀 (T) はループ内にあり、ウサギ (H) は (立っている) 亀に再び会うために P 歩しか歩かなくなります。シミュレーションが役に立ちそうです。リスト0-1-2-3-4-5-6-7-3を持ってみましょう

P=1 T=0 H=0; H makes 1 step and doesn't meet T
P=2 T=1 H=1; H makes 2 steps and doesn't meet T
P=4 T=3 H=3; H makes 4 steps and doesn't meet T 
P=8 T=7 H=7; H makes 5 steps and meets T !!!!!

注意: P=4 の場合、T はループ内にありますが、hare はサイクル全体を通過しません (P >= μ ですが P < λ )。

したがって、μ<8 および λ=5 が見つかりました。次に、μ (ループのエントリ ポイント) を見つけます。

T=0 H=0; H makes 5 steps; H=5 
while T <> H 
   move both
T=1 H=6
T=2 H=7
T=3 H=3 !!!!!!!

μ=3 が見つかりました