Floyd ' s Algorithme de détection de cycle | Déterminer le point de départ du cycle

Vous pouvez vous référer à « Détection du début dune boucle dans une liste liée individuellement » , voici un extrait:

Distance parcourue par slowPointer avant de rencontrer $ = x + y $

Distance parcourue par fastPointer avant de rencontrer $ = (x + y + z) + y = x + 2y + z $

Puisque fastPointer voyage avec double la vitesse de slowPointer et le temps est constant pour les deux quand ils atteignent le point de rencontre. Donc, en utilisant une simple relation vitesse, temps et distance (slowPointer parcouru la moitié de la distance):

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

Par conséquent, en déplaçant slowPointer au début de la liste liée, et en faisant les deux slowPointer et fastPointer pour déplacer un nœud à la fois, ils ont tous deux la même distance à parcourir .

Ils atteindront le point où la boucle commence dans la liste chaînée.

Commentaires

• Ici, vous avez supposé quils se rencontreront après une rotation. Il peut y avoir des cas (où le cycle est petit) où ils pourraient se rencontrer après un certain non. de rotations.
• @JotWaraich limage nest pas représentative de tous les cas; la logique est cependant toujours valable
• cest la réponse la plus simple à propos de cet algorithme sur tout Internet
• Je ‘ je ne suis pas très sûr si cette preuve est correcte. La distance parcourue par le pointeur lent doit être (x + (y + z) * α + y) et la distance parcourue par le pointeur rapide doit être (x + (y + z) * β + y) où α et β sont le nombre de cycles parcourus par le pointeur lent et rapide. La preuve semble échouer avec cet ajout,
• @ hashcode55 oui je suis daccord avec vous ce nest pas clair pour moi

Jai vu la réponse acceptée comme preuve ailleurs aussi. Cependant, bien quil soit facile à grok, il est incorrect. Ce que cela prouve, cest

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

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

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

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

donc, ce que nous voulons prouver est:

$ z = x \ mod \ L $

Ou que z est congru à x (modulo L)

La preuve suivante a plus de sens pour moi:

Point de rencontre, $ M = x + y $

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

$ x + y = kL $

$ x = kL – y $

Léquation ci-dessus prouve que $ x $ est le même quun multiple de longueur de boucle, $ L $ moins $ y $. Donc, si le pointeur rapide commence au point de rencontre, $ M $ ou à $ x + y $, alors il se terminera au début de la boucle.

Commentaires

• Je ne ‘ ne sais pas pourquoi cette réponse est sous-estimée. Cela semble être la preuve la plus formelle.
• @ I8A nouveau si x = z est faux, alors logique de déplacer rapidement le pointeur vers le point de départ & déplacer les deux rapide & pointeur lent pour trouver le début de la boucle ne ‘ t fonctionner. Je ne comprends pas ce que vous entendez par x = z est faux, veuillez expliquer comment cela est?
• @divine x = z est faux car cela implique que les deux sont égaux, mais il est acceptable davoir un très long  » tail »(grand x) et un très petit cercle (petit z). En utilisant le modulo nous sommes formellement corrects, nous voulons juste prouver que x% L == z, cest-à-dire que le pointeur qui se déplace dans le cercle en attendant de rejoindre lautre peut faire autant de boucles quil le souhaite, du moment que les dernières étapes (cest-à-dire le reste après la boucle) mèneront au début du cercle lui-même.
• cest génial !!
• Pour ceux dentre vous qui nont pas encore ‘ t comprendre pourquoi x = k * L – y conduit à z = x mod L. De x = k * L – y — > x = (k – 1) * L + L – y et alors maintenant vous pouvez dire que L – y doit être z. Maintenant, vous obtenez x = (k – 1) * L + z

Disons quil y a $ l $ éléments avant le début de la boucle et éléments $ n $ dans la boucle. Et $ e_l $ est le premier élément de la boucle qui est vu lorsque nous traversons la liste chaînée. Quand nous dirons  » un élément $ x $ avance sur $ e $ « , cela signifie que nous pouvons atteindre cet élément en prenant $ x $ pas de $ e $ .

Maintenant, quand Tr (tortue) atteint $ e_l $ , après $ l $ itérations, disons, Hr (Hare) est $ x $ pas en avance sur $ e_l $ . Étant donné que Hr a effectué un total de $ 2l $ pas dici là ( $ l $ étapes avant la boucle), donc:

$ x = l \ bmod n $ .

À chaque itération future, Tr et Hr progresseront de 1 et 2 étapes respectivement, et ainsi chaque itération augmentera leur  » écart  » de 1. Donc, ils se rencontreront après $ nx $ dautres itérations, lorsque leur intervalle deviendra $ x + (nx) = n $ . Ainsi, lélément de réunion $ M $ aura $ nx $ pas davance sur $ e_l $ . Cela signifie maintenant que passer $ x $ pas après $ M $ nous ramènera à nouveau à $ e_l $ . Notre objectif est de localiser $ e_l $ .

Donc, quand nous commençons avec une référence Tr à $ M $ et une autre référence Hr en tête de la liste chaînée, et progressez les deux pas à pas, après $ l $ itérations :

• Hr sera $ l $ pas devant la tête, qui est $ e_l $ .

• Tr sera $ (l \ bmod n) $ pas avant $ M $ , cest-à-dire $ x $ pas devant $ M $ , qui est $ e_l $ .

Ainsi, quand ils ont rencontré, nous savons quil sagit de $ e_l $ .

Voir cet article pour plus de détails. Vous y trouverez une méthode légèrement modifiée pour localiser $ e_l $ .

Jai trouvé la réponse sur stackoverflow. Merci si quelquun examinait cela pour moi. Et pour ceux qui comme moi voulaient une explication, veuillez vous référer à: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list La réponse choisie à la question, explique il!

Je pense aussi que la première réponse est incomplète, et si certaines des autres explications sont également bonnes, jen ai une autre version sans MOD pour afficher la même chose, ce qui est peut-être plus facile pour certaines personnes.

La même configuration, considérez $ X \ ge 0 $ étant la distance avant la boucle, $ N \ le \ text {size of list} $ étant la taille de la boucle (la quantité $ y + z $ dans limage), et le point de rencontre soit $ Y $ dans la boucle. À ce stade, notez que nous avons également créé $ X + Y \ le N $ .

Maintenant, le pointeur lent se déplace $ X + Y + pN $ , où $ p $ est un entier arbitraire. Ensuite, le pointeur rapide a parcouru 2 $ (X + Y + pN) $ .

Maintenant, nous prétendre quils se rencontrent à $ Y $ .

Preuve :

Sils se rencontrent à $ Y $ , il doit être que le pointeur le plus rapide a parcouru exactement $ qN $ que le pointeur le plus lent, où $ q $ est un entier . Ensuite, nous avons: $$ \ text {distance difference =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Mais nous avions $ Y $ étant un point de rencontre arbitraire dans la boucle, nous pouvons donc choisir simplement $ X + Y = N $ , qui vaut $ X + Y \ le N $ .

Par conséquent, nous avons: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ qui est vrai si $ p + 1 = q $ . Maintenant, comme $ p $ et $ q $ sont des entiers arbitraires, nous pouvons simplement choisir le minimum donc que $ p = 0, q = 1 $ , ce qui correspond à: $$ \ text {distance parcourue par le pointeur lent} = X + Y + pN = X + Y $$ et $$ \ text {distance parcourue par le pointeur rapide} = (X + Y + pN) + qN = X + Y + N $$ donc le pointeur rapide, à la première rencontre avec le pointeur lent, a parcouru exactement $ N $ plus.

La tortue et le lièvre sont deux pointeurs qui sont initialisés avec la valeur du « haut » de la liste. Dans chaque cycle de la boucle, le lièvre augmente de 2 éléments incrémentiels, tandis que la tortue augmente de un. Si à un moment donné, le lièvre est égal au lièvre, une boucle a été détectée. Si le lièvre est égal à la fin, aucune boucle nest trouvée.

Cet article lexplique mieux ligne par ligne:

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