Floyd algorithme de détection de cycle | La détermination du point de départ du cycle

Question

Je suis à la recherche d'aide pour comprendre l'algorithme de détection du cycle de Floyd. Je suis passé par l'explication sur wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Je peux voir comment l'algorithme détecte le cycle en O (n). Cependant, je ne peux pas visualiser le fait qu'une fois la tortue et des pointeurs de lièvre se rencontrent pour la première fois, le début du cycle peut être déterminée en revenant du pointeur de la tortue pour commencer et se déplacer alors à la fois la tortue et l'étape d'un lièvre à la fois. Le point où leur première rencontre est le début du cycle.

Quelqu'un peut-il aider en fournissant une explication, je l'espère différent de celui sur wikipedia, comme je suis incapable de comprendre / visualiser?

Answer 1

J'ai trouvé la réponse sur StackOverflow. Merci si quelqu'un cherchait à cela pour moi. Et pour ceux qui comme moi voulait une explication, s'il vous plaît se référer à:

Answer 2

Vous pouvez vous référer à « start détection d'une boucle dans la liste chaînée » , voici un extrait:

Distance parcourue par slowPointer avant la réunion $ = x + y $

Distance parcourue par fastPointer avant la réunion $ = (x + y + z) + y $ = X + 2y + z

Depuis fastPointer voyage avec deux la vitesse de slowPointer et temps est constant pour les deux lorsque la portée du point de rencontre. Ainsi, en utilisant la vitesse simple, le temps et la relation à distance (slowPointer parcouru la moitié de la distance):

\ begin {align *} 2 * \ operatorname {dist} (\ texte {} slowPointer) & = \ {operatorname dist} (\ texte {} fastPointer) \\ 2 (x + y) et x = + 2y + z \\ 2x + 2y & = x + 2y + z \\ x et z = \ End {align *}

Ainsi en déplaçant slowPointer au début de la liste liée, et en faisant la fois slowPointer et fastPointer pour déplacer un noeud à la fois, ils ont tous deux une même distance de couverture .

Ils atteindront au point où la boucle démarre dans la liste chaînée.

Je l'ai vu la réponse acceptée comme preuve ailleurs aussi. Cependant, alors que son facile à GROK, il est incorrect. Qu'est-ce que cela prouve est

$ x = z $ (ce qui est évidemment faux, et le diagramme fait juste semble plausible en raison de la façon dont il est esquissée).

Qu'est-ce que vous voulez vraiment prouver est (en utilisant les mêmes variables que décrit dans le diagramme dans la réponse acceptée ci-dessus):

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

$ (y + z) $ est la longueur de boucle, $ L $

, ce que nous voulons démontrer est:

$ z = x \ mod \ L $

Ou que z est congru à x (modulo L)

Après la preuve est plus logique pour moi:

Point de rencontre, M $ = x + y $

$ 2 (x + y) = M + kL $, où $ k $ est une constante. Au fond, la distance parcourue par le pointeur est rapide $ x + y $ plus un multiple de la longueur de boucle, $ L $

$ x + y = kL $

$ x = kL - y $

L'équation ci-dessus montre que $ x $ est identique à un multiple de la longueur de boucle, $ L $ moins $ y $. Donc, si le pointeur rapide commence au point de rencontre, $ M $ ou à $ x + y $, alors il finira au début de la boucle.

Answer 3

Vous pouvez vous référer à « start détection d'une boucle dans la liste chaînée » , voici un extrait:

Distance parcourue par slowPointer avant la réunion $ = x + y $

Distance parcourue par fastPointer avant la réunion $ = (x + y + z) + y $ = X + 2y + z

Depuis fastPointer voyage avec deux la vitesse de slowPointer et temps est constant pour les deux lorsque la portée du point de rencontre. Ainsi, en utilisant la vitesse simple, le temps et la relation à distance (slowPointer parcouru la moitié de la distance):

\ begin {align *} 2 * \ operatorname {dist} (\ texte {} slowPointer) & = \ {operatorname dist} (\ texte {} fastPointer) \\ 2 (x + y) et x = + 2y + z \\ 2x + 2y & = x + 2y + z \\ x et z = \ End {align *}

Ainsi en déplaçant slowPointer au début de la liste liée, et en faisant la fois slowPointer et fastPointer pour déplacer un noeud à la fois, ils ont tous deux une même distance de couverture .

Ils atteindront au point où la boucle démarre dans la liste chaînée.

Answer 4

Je l'ai vu la réponse acceptée comme preuve ailleurs aussi. Cependant, alors que son facile à GROK, il est incorrect. Qu'est-ce que cela prouve est

$ x = z $ (ce qui est évidemment faux, et le diagramme fait juste semble plausible en raison de la façon dont il est esquissée).

Qu'est-ce que vous voulez vraiment prouver est (en utilisant les mêmes variables que décrit dans le diagramme dans la réponse acceptée ci-dessus):

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

$ (y + z) $ est la longueur de boucle, $ L $

, ce que nous voulons démontrer est:

$ z = x \ mod \ L $

Ou que z est congru à x (modulo L)

Après la preuve est plus logique pour moi:

Point de rencontre, M $ = x + y $

$ 2 (x + y) = M + kL $, où $ k $ est une constante. Au fond, la distance parcourue par le pointeur est rapide $ x + y $ plus un multiple de la longueur de boucle, $ L $

$ x + y = kL $

$ x = kL - y $

L'équation ci-dessus montre que $ x $ est identique à un multiple de la longueur de boucle, $ L $ moins $ y $. Donc, si le pointeur rapide commence au point de rencontre, $ M $ ou à $ x + y $, alors il finira au début de la boucle.