Floyd ' s Algoritmo de detecção de ciclo | Determinando o ponto de partida do ciclo

Você pode consultar “Detecção do início de um loop em uma lista vinculada individualmente” , aqui está um trecho:

Distância percorrida por slowPointer antes da reunião $ = x + y $

Distância percorrida por fastPointer antes da reunião $ = (x + y + z) + y = x + 2y + z $

Já que fastPointer viaja com double a velocidade de slowPointer e o tempo é constante para ambos quando chegarem ao ponto de encontro. Portanto, usando uma relação simples de velocidade, tempo e distância (slowPointer percorreu metade da distância):

\ 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 *}

Portanto, movendo slowPointer para o início da lista vinculada e tornando ambos slowPointer e fastPointer para mover um nó de cada vez, ambos têm a mesma distância para cobrir .

Eles chegarão no ponto onde o loop começa na lista vinculada.

Comentários

• Aqui, você assumiu que eles se encontrarão após uma rotação. Pode haver casos (onde o ciclo é pequeno) em que eles podem se encontrar depois de um certo não. de rotações.
• @JotWaraich a imagem não é representativa de todos os casos; a lógica, entretanto, ainda se mantém
• esta é a resposta mais direta sobre esse algoritmo em toda a Internet
• Eu ‘ não tenho muita certeza se esta prova estiver correta. A distância percorrida pelo ponteiro lento deve ser (x + (y + z) * α + y) e a distância percorrida pelo ponteiro rápido deve ser (x + (y + z) * β + y) onde α e β são os números de ciclos percorridos pelo ponteiro lento e rápido. A prova parece falhar com esta adição,
• @ hashcode55 sim, concordo com você, isso não está claro para mim

Também vi a resposta aceita como prova em outro lugar. No entanto, embora seja fácil de grocar, é incorreto. O que isso prova é

$ x = z $ (o que está obviamente errado, e o diagrama apenas faz com que pareça plausível devido à forma como está esboçado).

O que você realmente deseja provar é (usando as mesmas variáveis descritas no diagrama na resposta aceita acima):

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

$ (y + z) $ é o comprimento do loop, $ L $

então, o que queremos provar é:

$ z = x \ mod \ L $

Ou que z é congruente ax (módulo L)

A prova a seguir faz mais sentido para mim:

Ponto de encontro, $ M = x + y $

$ 2 (x + y) = M + kL $, onde $ k $ é alguma constante.Basicamente, a distância percorrida pelo ponteiro rápido é $ x + y $ mais algum múltiplo do comprimento do loop, $ L $

$ x + y = kL $

$ x = kL – y $

A equação acima prova que $ x $ é o mesmo que algum múltiplo de comprimento de loop, $ L $ menos $ y $. Portanto, se o ponteiro rápido começar no ponto de encontro, $ M $ ou em $ x + y $, ele terminará no início do loop.

Comentários

• Eu não ‘ não sei por que essa resposta é subestimada. Esta parece ser a prova mais formal.
• @ I8Novamente, se x = z estiver errado, então a lógica em mover o ponteiro rápido de volta ao ponto inicial & mova ambos rápido & ponteiro lento para localizar o início do loop não ‘ funcionaria. eu não entendo o que você quer dizer com x = z está errado, por favor explique como isso é?
• @divine x = z está errado porque implica que ambos são iguais, mas é aceitável ter um longo “ cauda ”(x grande) e um círculo muito pequeno (z pequeno). Ao usar o módulo estamos formalmente corretos, queremos apenas provar que x% L == z, ou seja, o ponteiro que viaja no círculo esperando para se juntar ao outro pode fazer quantos loops quiser, desde que as últimas etapas (ou seja, o restante após o loop) levarão ao início do próprio círculo.
• isso é ótimo !!
• Para aqueles de vocês que ainda não ‘ entenda por que x = k * L – y leva a z = x mod L. De x = k * L – y — > x = (k – 1) * L + L – y e agora você pode dizer que L – y tem que ser z. Agora, você obtém x = (k – 1) * L + z

Digamos que existem $ l $ elementos antes do início do loop e $ n $ elementos no loop. E $ e_l $ é o primeiro elemento do loop que é visto quando percorremos a lista vinculada. Quando dizemos ” um elemento $ x $ passos à frente de $ e $ “, isso significa que podemos alcançar esse elemento seguindo $ x $ passos de $ e $ .

Agora, quando Tr (tartaruga) atinge $ e_l $ , depois de $ l $ iterações, digamos, Hr (Hare) está $ x $ passos à frente de $ e_l $ . Como o RH deu um total de $ 2l $ etapas até então ( $ l $ etapas antes do loop), então:

$ x = l \ bmod n $ .

Em cada iteração futura, Tr e Hr irão progredir por 1 e 2 etapas, respectivamente, e assim cada iteração aumentará sua ” gap ” em 1. Assim, eles se encontrarão após $ nx $ iterações adicionais, quando sua lacuna se tornará $ x + (nx) = n $ . Portanto, o elemento da reunião $ M $ será $ nx $ passos à frente de $ e_l $ . Agora, isso significa que pisar $ x $ passos depois de $ M $ nos levará novamente para $ e_l $ . Nosso objetivo é localizar $ e_l $ .

Então, quando começamos com uma referência Tr em $ M $ e outra referência Hr no topo da lista vinculada, e progredir ambos uma etapa por vez, após $ l $ iterações :

• Hr estará $ l $ passos à frente da cabeça, que é $ e_l $ .

• Tr será $ (l \ bmod n) $ passos à frente de $ M $ , ou seja, $ x $ passos à frente de $ M $ , que é $ e_l $ .

Portanto, quando eles têm conhecemos, sabemos que é $ e_l $ .

Veja este artigo para detalhes. Lá você encontrará um método ligeiramente modificado para localizar $ e_l $ .

Também acho que a resposta principal está incompleta e, embora algumas das outras explicações também sejam boas, tenho outra versão sem MOD para mostrar a mesma coisa, o que talvez seja mais fácil para algumas pessoas.

A mesma configuração, considere $ X \ ge 0 $ sendo a distância antes do loop, $ N \ le \ text {size of list} $ sendo o tamanho do loop (a quantidade $ y + z $ na imagem), e o ponto de encontro será $ Y $ no Loop. Neste ponto, observe que também fizemos $ X + Y \ le N $ .

Agora, o ponteiro lento viaja $ X + Y + pN $ , onde $ p $ é um número inteiro arbitrário. Em seguida, o ponteiro rápido viajou $ 2 (X + Y + pN) $ .

Agora, nós afirmam que se encontram em $ Y $ .

Prova :

Se eles se encontrarem em $ Y $ , deve ser que o ponteiro mais rápido viajou exatamente $ qN $ mais do que o ponteiro mais lento, onde $ q $ é um número inteiro . Então temos: $$ \ text {diferença de distância =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Mas tínhamos $ Y $ sendo um ponto de encontro arbitrário no circuito, então podemos escolher simplesmente $ X + Y = N $ , que vale como $ X + Y \ le N $ .

Portanto, temos: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ que é verdadeiro se $ p + 1 = q $ . Agora, como $ p $ e $ q $ são inteiros arbitrários, podemos escolher o mínimo para que $ p = 0, q = 1 $ , que corresponde a: $$ \ text {distância percorrida por ponteiro lento} = X + Y + pN = X + Y $$ e $$ \ text {distância percorrida pelo ponteiro rápido} = (X + Y + pN) + qN = X + Y + N $$ então o ponteiro rápido, na primeira vez que encontra o ponteiro lento, viajou exatamente $ N $ mais.

A tartaruga e a lebre são dois ponteiros que são inicializados com o valor do “topo” da lista. Em cada ciclo do loop, a lebre aumenta em 2 itens incrementais, enquanto a tartaruga aumenta em um. Se em algum ponto a lebre for igual à lebre, um loop foi detectado. Se a lebre for igual ao fim, um loop não foi encontrado.

Esta postagem explica melhor linha por linha:

https://www.thiscodeworks.com/floyd-s-cycle-detection-algorithm-aka-the-tortoise-and-the-hare-algorithms-logic-interesting/5e10a9b796432f6f7b798b29