Algoritmo de detección de ciclo de Brent

Question

¿Alguien puede ayudarme con el algoritmo de detección de ciclo de Brent? No estoy entendiendo exactamente por qué "buscar el poder más pequeño de dos 2^i que sea más grande que ambos λ y μ"? Cómo los poderes de 2 juegan un rol en la detección del ciclo. ¿Está de alguna manera relacionado con el algoritmo de detección de ciclos de Floyd? No puedo obtenerlo desde lo básico. Por favor ayuda !

Answer 1

Este método utiliza incrementos en los pasos (1, 2, 4, 8 ...) para ingresar al ciclo lo antes posible. Cuando P = 2^k llega a ser más grande que tanto λ y μ, entonces la tortuga (T) está en el circuito, y liebre (H) no hace más que P pasos para encontrarse (de pie) con la tortuga nuevamente. Parece que alguna simulación sería útil. Vamos tenemos lista 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 !!!!! 

Aviso: Con P = 4 T es el interior del bucle, pero la liebre no pasa por todo el ciclo (P> = μ pero P < λ)

Hemos encontrado μ < 8 y λ = 5. A continuación, queremos encontrar μ (punto de entrada de bucle)

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 !!!!!!! 

Nos acaba de encontrar μ = 3