Floyd ' s Algoritmo de detección de ciclos | Determinando el punto de inicio del ciclo

Puede consultar «Detectar el inicio de un bucle en una lista enlazada individualmente» , aquí hay un extracto:

Distancia recorrida por slowPointer antes de reunirse con $ = x + y $

Distancia recorrida por fastPointer antes de reunirse con $ = (x + y + z) + y = x + 2y + z $

Dado que fastPointer viaja con duplica la velocidad de slowPointer, y el tiempo es constante para ambos cuando lleguen al punto de encuentro. Entonces, usando una relación simple de velocidad, tiempo y distancia (slowPointer viajó la mitad de la distancia):

\ begin {align *} 2 * \ operatorname {dist} (\ text {slowPointer}) & = \ operatorname {dist} (\ text {fastPointer}) \\ 2 (x + y) & = x + 2y + z \\ 2x + 2y & = x + 2y + z \\ x & = z \ end {align *}

Por lo tanto, al mover slowPointer al inicio de la lista vinculada, y hacer que ambos slowPointer y fastPointer para mover un nodo a la vez, ambos deben cubrir la misma distancia .

Llegarán al punto donde comienza el ciclo en la lista enlazada.

Comentarios

También he visto la respuesta aceptada como prueba en otros lugares. Sin embargo, aunque es fácil de asimilar, es incorrecto. Lo que demuestra es

$ x = z $ (lo cual obviamente es incorrecto, y el diagrama simplemente lo hace parecer plausible debido a la forma en que está esbozado).

Lo que realmente quieres probar es (usando las mismas variables que se describen en el diagrama en la respuesta aceptada anterior):

$ z = x \ mod \ (y + z) $

$ (y + z) $ es la longitud del bucle, $ L $

entonces, lo que queremos demostrar es:

$ z = x \ mod \ L $

O que z es congruente ax (módulo L)

La siguiente demostración tiene más sentido para mí:

Punto de encuentro, $ M = x + y $

$ 2 (x + y) = M + kL $, donde $ k $ es una constante.Básicamente, la distancia recorrida por el puntero rápido es $ x + y $ más algún múltiplo de la longitud del bucle, $ L $

$ x + y = kL $

$ x = kL – y $

La ecuación anterior demuestra que $ x $ es lo mismo que algún múltiplo de la longitud del ciclo, $ L $ menos $ y $. Entonces, si el puntero rápido comienza en el punto de encuentro, $ M $ o en $ x + y $, terminará al comienzo del ciclo.

Comentarios

Digamos que hay $ l $ elementos antes de que comience el ciclo y $ n $ elementos en el ciclo. Y $ e_l $ es el primer elemento del bucle que se ve cuando recorremos la lista vinculada. Cuando diremos » un elemento $ x $ se adelanta a $ e $ «, eso significa que podemos llegar a ese elemento tomando $ x $ pasos de $ e $ .

Ahora, cuando Tr (tortuga) alcanza $ e_l $ , después de $ l $ iteraciones, digamos, Hr (Hare) está $ x $ pasos por delante de $ e_l $ . Dado que Hr ha tomado un total de $ 2l $ pasos para entonces ( $ l $ pasos antes del ciclo), entonces:

$ x = l \ bmod n $ .

En cada iteración futura, Tr y Hr progresarán por 1 y 2 pasos respectivamente, por lo que cada iteración aumentará su » gap » en 1. Por lo tanto, se encontrarán después de $ nx $ iteraciones posteriores, cuando su espacio se convierta en $ x + (nx) = n $ . Por lo tanto, el elemento de reunión $ M $ será $ nx $ pasos por delante de $ e_l $ . Eso significa que, si sigues $ x $ pasos después de $ M $ , volveremos a llevarnos a $ e_l $ . Nuestro objetivo es ubicar $ e_l $ .

Entonces, cuando comenzamos con una referencia Tr en $ M $ y otra Hr de referencia al principio de la lista vinculada, y progresar ambos paso a paso, después de $ l $ iteraciones :

• Hr será $ l $ pasos por delante de la cabeza, que es $ e_l $ .

• Tr será $ (l \ bmod n) $ pasos por delante de $ M $ , es decir, $ x $ pasos por delante de $ M $ , que es $ e_l $ .

Por lo tanto, cuando tienen conocido, sabemos que es $ e_l $ .

Consulte este artículo para detalles. Allí encontrará un método ligeramente modificado para localizar $ e_l $ .

Encontré la respuesta en stackoverflow. Gracias si alguien estaba investigando esto por mí. Y para aquellos que como yo querían una explicación, consulte: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list La respuesta elegida a la pregunta, explica ¡eso!

También creo que la respuesta principal está incompleta, y aunque algunas de las otras explicaciones también son buenas, tengo otra versión sin MOD para mostrar lo mismo, lo que quizás sea más fácil para algunas personas.

La misma configuración, considere $ X \ ge 0 $ siendo la distancia antes del bucle, $ N \ le \ text {size of list} $ es el tamaño del bucle (la cantidad $ y + z $ en la imagen), y el punto de encuentro será $ Y $ en el bucle. En este punto, observe que también hemos creado $ X + Y \ le N $ .

Ahora, el puntero lento viaja $ X + Y + pN $ , donde $ p $ es un entero arbitrario. Luego, el puntero rápido viajó $ 2 (X + Y + pN) $ .

Ahora, afirman que se encuentran en $ Y $ .

Prueba :

Si se encuentran en $ Y $ , debe ser que el puntero más rápido viajó exactamente $ qN $ más que el puntero más lento, donde $ q $ es un número entero . Entonces tenemos: $$ \ text {diferencia de distancia =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Pero teníamos $ Y $ como un punto de encuentro arbitrario en el ciclo, por lo que podemos elegir simplemente $ X + Y = N $ , que se mantiene como $ X + Y \ le N $ .

Por lo tanto, tenemos: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ que es cierto si $ p + 1 = q $ . Ahora, dado que tanto $ p $ y $ q $ son números enteros arbitrarios, podemos elegir el mínimo para ese $ p = 0, q = 1 $ , que corresponde a: $$ \ text {distancia recorrida por el puntero lento} = X + Y + pN = X + Y $$ y $$ \ text {distancia recorrida por el puntero rápido} = (X + Y + pN) + qN = X + Y + N $$ por lo que el puntero rápido, al encontrarse por primera vez con el puntero lento, viajó exactamente $ N $ más.