algorithm - 布伦特循环检测算法

Question

谁能帮我解决布伦特的循环检测算法。我不明白为什么“搜索两个大于 λ 和 μ 的 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