Expliquez comment trouver le nœud de début de cycle dans une liste liée à un cycle ?

Question

Je comprends que la rencontre de la tortue et du lièvre conclut à l'existence de la boucle, mais comment le fait de déplacer la tortue au début de la liste liée tout en gardant le lièvre au point de rencontre, puis de déplacer les deux pas à pas les fait se rencontrer au point de départ du cycle ?

Answer 1

Je vais essayer de clarifier l'algorithme de détection des cycles qui est fourni à l'adresse suivante http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare dans mes propres mots.

Comment cela fonctionne

Ayons une tortue et un lièvre (nom des pointeurs) pointant vers le début de la liste avec un cycle, comme dans le schéma ci-dessus.

Faisons l'hypothèse que si nous déplaçons la tortue d'un pas à la fois, et le lièvre de deux pas à la fois, ils finiront par se rencontrer en un point. Montrons tout d'abord que cette hypothèse est vraie.

La figure illustre une liste avec un cycle. Le cycle a une longueur de n et nous sommes initialement m s'éloigne du cycle. Disons également que le point de rencontre est k pas du début du cycle et la tortue et le lièvre se rencontrent quand la tortue a pris i total des pas. (Lièvre aurait pris 2i total des étapes d'ici là).

Les 2 conditions suivantes doivent être remplies :

1) i = m + p * n + k

2) 2i = m + q * n + k

Le premier dit que la tortue se déplace i et dans ces i les premières étapes du cycle. Ensuite, il passe par le cycle p fois pour un nombre positif p . Enfin, il passe à k d'autres nœuds jusqu'à ce qu'il rencontre le lièvre.

Il en va de même pour le lièvre. Il se déplace 2i et dans ces 2i les premières étapes du cycle. Ensuite, il passe par le cycle q fois pour un nombre positif q . Enfin, il passe à k plus de nœuds jusqu'à ce qu'il rencontre la tortue.

Le lièvre voyage deux fois plus vite que la tortue, et le temps est constant pour les deux lorsqu'ils atteignent le point de rencontre.

En utilisant la relation simple entre vitesse, temps et distance,

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

Parmi m, n, k, p, q, les deux premiers sont des propriétés de la liste donnée. Si nous pouvons montrer qu'il existe au moins un ensemble de valeurs pour k, q, p qui rend cette équation vraie, nous montrons que l'hypothèse est correcte.

L'un de ces ensembles de solutions est le suivant :

p = 0

q = m

k = m n - m

Nous pouvons vérifier que ces valeurs fonctionnent comme suit :

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn.

Pour cet ensemble, i est

i = m + p n + k

=> m + 0 * n + mn - m = mn.

Bien sûr, vous devriez voir que ce n'est pas nécessairement le plus petit i possible. En d'autres termes, la tortue et le lièvre pourraient s'être déjà rencontrés plusieurs fois auparavant. Cependant, puisque nous montrons qu'ils se rencontrent en un point au moins une fois, nous pouvons dire que l'hypothèse est correcte. Ils devraient donc se rencontrer si nous déplaçons l'un d'eux d'un pas et l'autre de deux pas à la fois.

Nous pouvons maintenant passer à la deuxième partie de l'algorithme, qui consiste à trouver le début du cycle.

Début du cycle

Lorsque la tortue et le lièvre se rencontrent, remettons la tortue au début de la liste et gardons le lièvre là où ils se sont rencontrés (c'est-à-dire à k pas du début du cycle).

L'hypothèse est que si nous les laissons se déplacer à la même vitesse (1 pas pour les deux), la première fois qu'ils se rencontreront sera le début du cycle.

Prouvons cette hypothèse.

Supposons d'abord qu'un oracle nous dise ce qu'est m.

Ensuite, si on les laisse se déplacer de m + k pas, la tortue devra arriver au point où elles se sont rencontrées à l'origine (à k pas du début du cycle - voir dans la figure).

Auparavant, nous avons montré que m + k = (q - 2p) n .

Comme m + k pas est un multiple de la longueur n du cycle, le lièvre, entre-temps, parcourrait le cycle (q-2p) fois et reviendrait au même point (à k pas du début du cycle).

Maintenant, au lieu de les laisser faire m + k pas, si nous les laissons faire seulement m pas, la tortue arrivera au début du cycle. Il manquerait au lièvre k pas pour effectuer (q-2p) rotations. Comme il a commencé k pas avant le début du cycle, le lièvre devrait arriver au début du cycle.

Par conséquent, cela explique qu'ils devraient se rencontrer au début du cycle après un certain nombre d'étapes pour la toute première fois (toute première fois car la tortue vient d'arriver au cycle après m étapes et elle n'a jamais pu voir le lièvre qui était déjà dans le cycle).

Nous savons maintenant que le nombre de pas dont nous avons besoin pour les déplacer jusqu'à ce qu'ils se rencontrent est la distance entre le début de la liste et le début du cycle, m. Bien sûr, l'algorithme n'a pas besoin de savoir ce que m représente. Il va simplement déplacer la tortue et le lièvre un pas après l'autre jusqu'à ce qu'ils se rencontrent. Le point de rencontre doit être le début du cycle et le nombre d'étapes doit être la distance (m) au début du cycle. En supposant que nous connaissions la longueur de la liste, nous pouvons également calculer la longueur du cycle en soustrayant m de la longueur de la liste.

Answer 2

C'est Algorithme de Floyd pour la détection des cycles . Vous posez une question sur la deuxième phase de l'algorithme - une fois que vous avez trouvé un nœud qui fait partie d'un cycle, comment trouver le nœud qui fait partie du cycle ? commencer du cycle ?

Dans la première partie de l'algorithme de Floyd, le lièvre fait deux pas pour chaque pas de la tortue. Si la tortue et le lièvre se rencontrent, il y a un cycle, et le point de rencontre fait partie du cycle, mais n'est pas nécessairement le premier nœud du cycle.

Lorsque la tortue et le lièvre se rencontrent, nous avons trouvé le plus petit i (le nombre de pas effectués par la tortue) tel que X _i \= X _2i . Soit mu représentant le nombre d'étapes pour passer de X ₀ au début du cycle, et laissez lambda représenter la longueur du cycle. Alors i = mu + a lambda, et 2i = mu + b lambda, où a et b sont des entiers indiquant combien de fois la tortue et le lièvre ont fait le tour du cycle. En soustrayant la première équation de la seconde donne i = (b-a)*lambda, i est donc un multiple entier de lambda. de lambda. Par conséquent, X _{i + mu} \= X _mu . X _i représente le point de rencontre de la tortue et du lièvre. Si vous déplacez la tortue vers le nœud de départ X ₀ et que la tortue et le lièvre continuent à la même vitesse, après mu pas supplémentaires, la tortue aura atteint X _mu et le lièvre aura atteint X _{i + mu} \= X _mu Le deuxième point de rencontre indique donc le début du cycle.

Answer 3

Au moment de la première collision, la tortue s'est déplacée m+k étapes comme indiqué ci-dessus. Le lièvre se déplace deux fois plus vite que la tortue, ce qui signifie que le lièvre s'est déplacé 2(m+k) étapes. À partir de ces simples faits, nous pouvons dériver le graphique suivant.

À ce stade, nous ramenons la tortue au point de départ et déclarons que le lièvre et la tortue doivent se déplacer un pas après l'autre. Par définition, après m étapes, la tortue sera au début du cycle. Où sera le lièvre ?

Le lièvre sera également au début du cycle. C'est ce que montre clairement le deuxième graphique : Lorsque la tortue a été déplacée vers le début, le lièvre a été k entre dans son dernier cycle. Après m étapes, le lièvre aura accompli un autre cycle et sera entré en collision avec la tortue.

Answer 4

Approche :

Il y a deux pointeurs :

• Un pointeur lent qui se déplace d'un nœud à la fois.
• Un pointeur rapide qui déplace deux nœuds à la fois.

Si les deux pointeurs se rencontrent, cela prouve qu'il y a une boucle. Une fois qu'ils se sont rencontrés, l'un des nœuds pointe vers la tête et les deux avancent un nœud à la fois. Ils se rencontreront au début de la boucle.

Justification : Lorsque deux personnes marchent sur une piste circulaire, l'une d'elles à deux fois la vitesse de l'autre, où se rencontrent-elles ? Exactement là où elles ont commencé.

Maintenant, supposons que le coureur rapide a une avance de k étapes d'un n tour de piste. où vont-ils se rencontrer ? Exactement à n-k étapes. Lorsque le coureur lent a parcouru (n-k) pas, le coureur rapide aurait couvert k+2(n-k) étapes. ( ie, k+2n-2k étapes ie 2n-k étapes ), c'est-à-dire (n-k) étapes (le chemin est circulaire et nous ne sommes pas concernés par le nombre de tours après lesquels ils se rencontrent ; nous sommes juste intéressés par la position où ils se rencontrent).

Comment le coureur rapide a-t-il eu l'avantage sur les autres ? k pas en premier lieu ? Parce qu'il a fallu au coureur lent autant de pas pour atteindre le début de la boucle. Donc le début de la boucle est à k pas du noeud de tête.

Note : Le nœud où les deux pointeurs se sont rencontrés est k pas du début de la boucle (à l'intérieur de la boucle) et le nœud de tête est également k pas du début de la boucle. Ainsi, lorsque le pointeur avance à un rythme égal d'un pas de chacun de ces nœuds, ils se rencontrent au début de la boucle.

Je crois que c'est simple. Veuillez me faire savoir si une partie est ambiguë.

Answer 5

Supposons que le lièvre et la tortue se rencontrent en un point situé à k pas du début du cycle, que le nombre de pas avant le début du cycle est mu et que la longueur du cycle est L.

Donc maintenant au point de rencontre ->

Distance parcourue par la tortue = mu + a*L + k - Équation 1

(nombre de pas pour atteindre le début du cycle + nombre de pas pour couvrir 'a' itérations du cycle + k pas depuis le début du cycle) (où a est une constante positive)

Distance parcourue par le lièvre = mu + b*L + k - Équation 2

(Pas pris pour atteindre le début du cycle + pas pris pour couvrir 'b' itérations du cycle + k pas depuis le début du cycle) (où b est une constante positive et b>=a)

La distance supplémentaire parcourue par le lièvre est donc = Équation 2 - Équation 1 = (b-a)*L

Notez que cette distance est également égale à la distance de la tortue depuis le point de départ puisque le lièvre se déplace 2 fois plus vite que la tortue. On peut l'assimiler à "mu+k" qui est aussi la distance du point de rencontre depuis le début si l'on ne tient pas compte des traversées multiples du cycle.

Ainsi, mu + k = (b-a)*L

Ainsi, mu pas à partir de ce point ramèneraient au début du cycle (puisque k pas à partir du début du cycle ont déjà été effectués pour atteindre le point de rencontre). Cela peut se produire dans le même cycle ou dans n'importe lequel des cycles suivants. Ainsi, si nous déplaçons la tortue au début de la liste chaînée, il lui faudra mu pas pour atteindre le point de départ du cycle et le lièvre fera mu pas pour atteindre également le début du cycle et ils se rencontreront donc tous les deux au point de départ du cycle.

P.S. Honnêtement, j'avais la même question que l'affiche originale dans mon esprit et j'ai lu la première réponse, ils ont clarifié quelques choses mais je ne pouvais pas arriver au résultat final clairement et donc j'ai essayé de le faire à ma propre façon et j'ai trouvé plus facile à comprendre.