ブレントのサイクル検出アルゴリズム

Question

誰でもブレントのサイクル検出アルゴリズムを教えてください。私はちょうど "2と2の最小のパワーを探して、なぜλとμの両方よりも大きいのか"ということを正確に理解していませんか？どのように2の力がサイクルの検出に果たしているか。それは何とかフロイドのサイクル検出アルゴリズムに関連していますか？私は基本からそれを得ることができません。助けてください ！

Answer 1

この方法では、増加するステップ（1,2,4,8 ...）を使用してループ内にできるだけ早く到達します。 P = 2^kがλとμの両方よりも大きくなると、亀（T）がループに入り、hare（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がループの内側にあるが、ウサギはサイクル全体を経由しないで（P≧μであるがP <λ）

したがって、λ0= 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