Algorithme du lièvre et de la tortue

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Le Lièvre et la Tortue.

L'algorithme de Floyd de détection de cycle, encore connu sous le nom d'algorithme du lièvre et de la tortue, est un algorithme pour détecter les cycles dans des séquences arbitraires, qu'il s'agisse de structures de données ou de séquences générées à la volée (et notamment les séquences pseudo-aléatoires), en espace O(1).

Cet algorithme fut énoncé par Robert Floyd en 1967[1], et ne doit pas être confondu avec l'algorithme de Floyd-Warshall (tous les plus courts chemins dans un graphe).

Algorithme[modifier | modifier le code]

Soit f\colon S\mapsto S une fonction, et S un ensemble fini de cardinal n. On considère la suite (a_i) définie par a_0\in S et a_{i+1}=f(a_i)

Il est clair que cette suite aboutit nécessairement à un cycle, le nombre de ses valeurs possibles étant limité à n. Une manière naïve de déterminer la longueur de ce cycle consiste à stocker chaque élément de la séquence et, à chaque étape, de vérifier si le nouvel élément fait partie des éléments déjà rencontrés. L'espace utilisé est en O(μ + λ), où μ est la longueur du cycle et λ le nombre d'éléments à l'extérieur du cycle.

Si l'on parvient à trouver deux éléments de la séquence a_i et a_{j} tels que a_i=a_{j}

alors |i-j| est un multiple de la longueur du cycle.

L'algorithme de Floyd de détection de cycle détermine une telle égalité en parcourant la séquence simultanément à deux vitesses différentes, respectivement 1 et 2. L'algorithme aboutit nécessairement sur deux valeurs égales, i.e. détermine m tel que a_m=a_{2m}

Dès lors, 2m-m=m est un multiple de la longueur du cycle, μ.

Pour déterminer la valeur exacte de μ, il suffit de refaire tourner l'algorithme à partir de m+1, jusqu'à trouver un autre nombre m_{1} tel que a_{m_1}=a_{2{m_1}}. Dès lors on a d'une part m_1\le m+\mu (car on retombe alors sur a_m) et d'autre part μ qui divise m_1-m (car il divise m et m_1), donc \mu=m_1-m.

Visualisation[modifier | modifier le code]

Exemple de cycle de μ=6 nœuds obtenu après être passé sur λ=2 nœuds

La meilleure façon de visualiser l'algorithme consiste à représenter la séquence. Le dessin obtenu ressemble à la lettre grecque ρ. La séquence démarre en bas, monte et emprunte le cycle dans le sens des aiguilles d'une montre. Suivant l'algorithme de Floyd, les deux parcours se rencontrent en a_6 après 6 itérations. Un deuxième tour de l'algorithme amène les deux parcours à se rencontrer après 6 nouvelles itérations, d'où la valeur \mu=6.

Parcours t_0 t_1 t_2 t_3 t_4 t_5 t_6 t_7 t_8 t_9 t_{10} t_{11} t_{12}
Lent a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_2 a_3 a_4 a_5 a_6
Rapide a_0 a_2 a_4 a_6 a_2 a_4 a_6 a_2 a_4 a_6 a_2 a_4 a_6

Pseudo-code[modifier | modifier le code]

 m = 1; x = f(a_0); y = f(x);
 tant que x != y faire
    m = m + 1
    x = f(x)
    y = f(f(y))
 { la valeur de m est telle que a_m=a_{2m} }

Si on souhaite obtenir la valeur de \mu, il suffit d'ajouter à la suite le code suivant :

 mu = 0
 répéter
    mu = mu+1
    x = f(x)
    y = f(f(y))
 tant que x != y

Complexité[modifier | modifier le code]

L'algorithme effectue au minimum λ comparaisons, étant donné que le parcours lent de la séquence doit au moins atteindre le cycle pour rencontrer le parcours rapide. Le nombre maximum de comparaisons est \lambda+\mu, étant donné que le parcours lent ne peut effectuer plus d'un tour du cycle avant d'être rattrapé par le parcours rapide. L'algorithme utilise un espace O(1).

Variantes[modifier | modifier le code]

La variante la plus connue de l'algorithme de Floyd de détection de cycle est l'algorithme rho de Pollard, un algorithme de décomposition en produit de facteurs premiers qui utilise les séquences pseudo-aléatoires pour factoriser les entiers. Il existe également un algorithme de calcul du logarithme discret basé sur l'algorithme de Floyd de détection de cycle.

Références[modifier | modifier le code]

  1. (en) R.W. Floyd, « Non-deterministic Algorithms »,‎ octobre 1967, pp. 636-644

Source[modifier | modifier le code]

Liens externes[modifier | modifier le code]