Algoritmo de detecção do ciclo de Floyd | Determinando o ponto inicial do ciclo

32

Estou procurando ajuda para entender o algoritmo de detecção de ciclo de Floyd. Passei pela explicação na wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Eu posso ver como o algoritmo detecta o ciclo em O (n) tempo. No entanto, não consigo visualizar o fato de que, uma vez que os ponteiros da tartaruga e da lebre se encontram pela primeira vez, o início do ciclo pode ser determinado movendo o ponteiro da tartaruga de volta para o início e movendo a tartaruga e a lebre um passo de cada vez. O ponto em que eles se conheceram é o início do ciclo.

Alguém pode ajudar, fornecendo uma explicação, espero que diferente da da wikipedia, pois não consigo entender / visualizar?

Anurag Kapur
fonte
3
Encontrei a resposta no stackoverflow. Obrigado se alguém estava olhando para mim. E para quem gosta de mim queria uma explicação, consulte: stackoverflow.com/questions/3952805/… A resposta escolhida para a pergunta explica isso!
Anurag Kapur
Olá @Anurag. Apenas para sua informação, eu fiz um post no blog sobre o algoritmo "Tortoise and the Hare" aqui
Kyle
Você sabe por que a fastvariável, ou a "lebre", precisa se mover duas vezes a velocidade da tartaruga, em vez de apenas uma à frente?
devdropper87

Respostas:

47

Você pode consultar "Detectando o início de um loop na lista vinculada individual" , eis um trecho:

insira a descrição da imagem aqui

Distância percorrida slowPointerantes da reunião =x+y

Distância percorrida fastPointerantes da reunião =(x+y+z)+y = x + 2y + z

Uma vez que fastPointerviaja com o dobro da velocidade de slowPointer, e o tempo é constante para ambos quando atingem o ponto de encontro. Então, usando simples relação de velocidade, tempo e distância ( slowPointerpercorreu metade da distância):

2dist(slowPointer)=dist(fastPointer)2(x+y)=x+2y+z2x+2y=x+2y+zx=z

Portanto, movendo slowPointer- se para o início da lista vinculada, criando os dois slowPointere fastPointermovendo um nó de cada vez, ambos têm a mesma distância a percorrer .

Eles chegarão no ponto em que o loop inicia na lista vinculada.

Monge Velho
fonte
2
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 após um certo não. de rotações.
Navjot Waraich
1
@JotWaraich a imagem não é representativa de todos os casos; a lógica no entanto ainda se mantém
denis631
3
esta é a resposta mais direta sobre esse algoritmo em toda a Internet
Marshall X
7

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

x=z (que está obviamente errado, e o diagrama apenas faz com que pareça plausível devido à maneira como é 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)L

então, o que queremos provar é:

z=x mod L

Ou que z é congruente com x (módulo L)

A prova a seguir faz mais sentido para mim:

M=x+y

2(x+y)=M+kLkx+yL

x+y=kL

x=kLy

xLyMx+y

l8 novamente
fonte