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 une fonction, et S un ensemble fini de cardinal n. On considère la suite définie par et

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 et tels que

alors 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

Dès lors, 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 tel que . Dès lors on a d'une part (car on retombe alors sur ) et d'autre part μ qui divise (car il divise et ), donc .

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 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 .

Parcours
Lent
Rapide

Pseudo-code[modifier | modifier le code]

 m = 1; x = f(); 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  }

Si on souhaite obtenir la valeur de , 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 , é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 »,‎ , pp. 636-644

Source[modifier | modifier le code]

Liens externes[modifier | modifier le code]