¿Cómo funciona el algoritmo de búsqueda de ciclo de Floyd? ¿De qué manera mover la tortuga al comienzo de la lista vinculada, mientras se mantiene a la liebre en el lugar de reunión, seguido de mover un paso a la vez, hace que se encuentren en el punto de inicio del ciclo?

La forma en que pienso es así (y de ninguna manera es un argumento formal). Supongamos que existe un ciclo de longitud [matemática] m [/ matemática]. Entonces eso significa que si tenemos dos números [matemática] p [/ matemática] y [matemática] q [/ matemática] (que podría representar el punto de partida de la tortuga y la liebre respectivamente), y si tenemos dos velocidades [matemática] \ mu [/ math] y [math] \ lambda [/ math], luego en algún momento, para

[mates]
\ mathrm {tortuga} (t) = p + \ mu t
[/mates]

y

[mates]
\ mathrm {liebre} (t) = q + \ lambda t
[/mates]

tendremos algunas [matemáticas] t [/ matemáticas] que satisfagan

[mates]
\ mathrm {tortuga} (t) \ equiv \ mathrm {liebre} (t) \ pmod m
[/mates]

proporcionó algunas condiciones sobre la coprimidad de las variables. Si elegimos [math] \ mu = 1 [/ math] y [math] \ lambda = 2 [/ math], con ambos [math] p = q = 0 [/ math], entonces es fácil ver la solución se reduce a un problema múltiple menos común.

Como no conocemos [math] m [/ math] a priori , simplemente iteramos [math] t \ leftarrow t + 1 [/ math] hasta encontrar una equivalencia.

Aquí hay un código para el algoritmo de búsqueda de ciclo de Floyd generalizado para trabajar con cualquier función [matemática] f: A \ to B [/ matemática] siempre que podamos probar si dos valores en [matemática] B [/ matemática] son ​​equivalentes. El problema se reformula como encontrar [math] \ psi [/ math] (la fase ) y [math] p [/ math] (el período ) para la función

[mates]
g (i) = f ^ i (x_0)
[/mates]

tal que para [matemáticas] x> x_0 + \ psi [/ matemáticas], [matemáticas] g (x + p) = g (x) [/ matemáticas].

Encuentra esto haciendo una aplicación continua de [math] f [/ math] (la tortuga) y [math] f \ circ f [/ math] (la liebre) hasta que sean iguales.

Puede ser instructivo leer los comentarios al código.

(Código de tarballs_are_good / lisp-random / source / cycle-detect.lisp.)

(defun cyclicp (function origin &key (test 'equalp)) "Compute the phase and period of the function g(i) := FUNCTION^i(SEED) where f^n is n compositions of f. Return two values, the period and phase respectively. FUNCTION should have a type signature of Eq(A) A -> A where Eq denotes that A has an equality predicate TEST." (flet ((f (x) (funcall function x)) (f^2 (x) (funcall function (funcall function x)))) (let (start-of-cycle coinciding-position phase period) ;; Find when the tortoise and the hare land on the same value, ;; COINCIDING-POSITION. (loop :for tortoise := (f origin) :then (f tortoise) :for hare := (f^2 origin) :then (f^2 hare) :until (funcall test tortoise hare) :finally (setf coinciding-position hare)) ;; Calculate the "phase" of the cycle. The phase is the distance ;; between the COINCIDING-POSITION and the ORIGIN. To ;; calculate the distance, we have two tortoises walk in ;; parallel, one at the starting position, the other where the ;; hare stopped. We wait until these tortoises land in the same ;; place. (loop :for steps := 0 :then (1+ steps) :for tortoise-1 := origin :then (f tortoise-1) :for tortoise-2 := coinciding-position :then (f tortoise-2) :until (funcall test tortoise-1 tortoise-2) :finally (setf phase steps start-of-cycle tortoise-1)) ;; Calculate the period of the cycle. We do this by setting a ;; tortoise at the start of the cycle found previously, ;; START-OF-CYCLE, and let it step until it reaches the same ;; position. (loop :for steps := 1 :then (1+ steps) :for tortoise := (f start-of-cycle) :then (f tortoise) :until (funcall test start-of-cycle tortoise) :finally (setf period steps)) (values period phase)))) 

Considere un puntero lento y rápido. el puntero rápido se mueve con el doble de velocidad que el puntero lento. así que cuando el puntero lento ha movido la distancia “d”, entonces rápido ha movido la distancia “2d”.

ahora considere que la longitud del bucle es y + z;
distancia antes del ciclo es x
ahora cuando se encuentran lento y rápido
lento ha cubierto la distancia d = x + y
rápido ha cubierto la distancia 2 * d = x + y + z + y

2 * d = x + 2y + z
2 (x + y) = x + 2y + z
2x + 2y = x + 2y + z
x = z
así que esto se muestra después de obtener el punto de encuentro si se coloca un puntero al principio. luego moviendo ambos con la misma distancia. se encontrarán al comienzo del ciclo.

EDITAR: el ejemplo anterior es cuando el puntero rápido ha completado solo un bucle antes de encontrarse lento.
Del mismo modo, también se puede probar para múltiples bucles.