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

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

出典

2012-05-29 SlashGeek

@WillNessは何これは素数と関係があるのでしょうか？私は素数のタグを削除する必要がありますと思います。 – gsingh2011

@ gsingh2011素因数分解アルゴリズムで使用されています。おそらく素因数分解タグが追加されなければならない/素数を置き換える：... –

この方法では、増加するステップ（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

出典

2012-05-29 12:47:28 MBo

Thanx ...たくさんの助けを借りて:) – SlashGeek

「2のべき乗」がここで使われる理由を説明できますか？私たちができるだけ早くループ内に飼育することを目指しているのであれば、「力の3」または「5の力」を使用してみませんか？「5のべき乗」が使用される場合、このアルゴリズムは依然として有効でしょうか？最後に、なぜ亀が出会う前に最後のステップの数がλに等しいのですか？その数字をサイクルの長さとしなければならないという証拠は何ですか？ありがとうございました。 – carawan

@ carawan、私は証明はないが、私は3のべき乗と5のべき乗が効いていると思う。私はいくつかの簡単なテストを行った。
低速イテレータがまったく動かない場合は、イテレータが遅いほどループ外にある可能性があるため、アルゴリズムは壊れてしまいます。
イテレータの処理速度が遅く、次の距離が常に一定の制限（99など）を下回る場合、ループサイズが99を超える可能性があるため、アルゴリズムが壊れます。
次の距離が徐々に大きくなると、フォロワーは動いて、結局彼らは会うと思う。 –

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

答えて

関連する問題