La detección de ciclos en Wikipedia tiene una excelente analogía para esto, basada en la fábula de la carrera entre la tortuga y la liebre. Tenga en cuenta que a menudo hay dos etapas para un algoritmo de búsqueda de ciclo; primero, detecta un ciclo (al encontrar dos índices [matemática] i, j [/ matemática] tal que [matemática] x_i = x_j [/ matemática]), y luego, tal vez, desee encontrar valores mínimos [matemática] \ mu, \ lambda [/ math] tal que [math] x_ {i + k \ lambda} = x_i [/ math] para todos los números naturales [math] k [/ math] y [math] i \ geq \ mu [ /matemáticas]. Centrémonos en la parte de detección; Una vez que haya encontrado un ciclo, es mucho más fácil encontrar los valores mínimos.
La estrategia es primero poner en marcha la ‘liebre’, que revisará los datos rápidamente, y detrás de él, la ‘tortuga’, que examinará los datos más lentamente. Si la tortuga y la liebre alguna vez están de acuerdo, has detectado un ciclo.
El algoritmo de Floyd es el más simple. Comience la tortuga y la liebre en la posición cero, luego, en cada iteración, deje que la tortuga avance un paso y la liebre avance dos pasos. En cada iteración, usted compara [matemáticas] x_i [/ matemáticas] y [matemáticas] x_ {2i} [/ matemáticas]. Si existe un ciclo, entonces eventualmente obtendrá un valor [math] i \ geq \ mu [/ math] y la diferencia entre las posiciones de liebre y tortuga (que también es [math] i [/ math]) será divisible por [math] \ lambda [/ math]. En cada paso, debe iterar la función tres veces; una vez para la tortuga, dos veces para la liebre.
El algoritmo de Brent procede de manera un poco diferente; esta vez, dejamos que la tortuga se siente a una potencia de 2, y la liebre se escapa a la siguiente potencia de 2. En cada iteración interna, la tortuga está en [matemáticas] 2 ^ n [/ matemáticas] mientras que la liebre está en [ matemáticas] 2 ^ n + i [/ matemáticas]. Una vez que la liebre llega a [matemáticas] 2 ^ {n + 1} [/ matemáticas], restablecemos la tortuga a ese punto. Nuevamente, si existe un ciclo, eventualmente lo detectaremos. Los beneficios son esta vez, solo necesita aplicar la función una vez en cada paso; además, una vez que [math] 2 ^ n \ geq \ mu [/ math], la liebre encontrará [math] \ lambda [/ math] directamente, en lugar de posiblemente un múltiplo. Incluso si tiene que buscar más a través de los datos, el algoritmo de Brent requerirá menos evaluaciones funcionales que las de Floyd.
- ¿Cuál es una fórmula para calcular la suma de todas las permutaciones de un número dado con repeticiones?
- Sea [math] d (n) [/ math] el número de factores positivos, incluidos [math] 1 [/ math] y [math] n, [/ math] de un entero positivo [math] n [/ math] . ¿Cómo encontramos la suma de todas [matemáticas] n [/ matemáticas] de modo que [matemáticas] d (n) = \ frac {n} {3} [/ matemáticas]? Cualquier prueba elegante de por qué estos son los únicos valores de [math] n [/ math] son bienvenidos pero no obligatorios.
- Cómo explicar qué sucede cuando sustituye directamente los valores de la tira crítica en la función sin continuación analítica en una función zeta de Riemann
- ¿Cuál es el resto cuando 123, 123, … (hasta 300 dígitos) se divide por 999?
- Dado el logaritmo natural [math] \ ln x [/ math] (y tal vez iniciar sesión con cualquier base) y un vector [math] A \ in \ mathcal {R} ^ n [/ math], ¿cómo sería [math] \ ln ¿Un trabajo [/ matemático]?
