Union-Find

Un article de Wikipédia, l'encyclopédie libre.

Étant donné un ensemble d'éléments, il est souvent utile de le partitionner en un certain nombre de classes disjointes. Une structure de données pour le problème des classes disjointes est une structure de données qui maintient une telle partition. Un algorithme union-find est un algorithme qui fournit deux opérations essentielles sur une telle structure :

  • Find : détermine la classe d'un élément. Notamment utile pour déterminer si deux éléments appartiennent à la même classe.
  • Union : réunit deux classes en une seule.

Parce qu'elle fournit ces deux opérations, une structure de données pour le problème des classes disjointes est souvent appelée structure union-find. L'autre opération importante, MakeSet, construit une classe contenant un unique élément (un singleton). À l'aide de ces trois opérations, beaucoup de problèmes de partitionnement peuvent être résolus (voir la section Applications).

Afin de définir ces opérations plus précisément, il faut choisir un moyen de représenter les classes. L'approche classique consiste à sélectionner un élément particulier de chaque classe, appelé le représentant, pour représenter la classe toute entière. Dès lors, Find(x) renvoie le représentant de la classe de x.

[modifier] Solution utilisant des listes chaînées

La solution la plus immédiate pour le problème des classes disjointes consiste à construire une liste chaînée pour chaque classe. On choisit alors l'élément en tête de liste comme représentant.

MakeSet crée une liste contenant un élément. Union concatène les deux listes, une opération en temps constant. Malheureusement, l'opération Find nécessite alors un temps Ω(n) avec cette approche.

On peut y remédier en ajoutant à chaque élément d'une liste chaînée un pointeur vers la tête de la liste ; Find est alors réalisée en temps constant. Cependant, on a détérioré l'efficacité de Union, qui doit maintenant parcourir tous les éléments d'une des deux listes pour les faire pointer vers la tête de l'autre liste, ce qui nécessite un temps Ω(n).

On peut améliorer ceci en ajoutant toujours la plus petite des deux listes en queue de la plus longue, ce qui porte le nom d' heuristique de l'union pondérée. Ceci nécessite de maintenir la longueur des listes au fur et à mesure des opérations. Avec cette solution, une séquence de m opérations MakeSet, Union et Find sur n éléments nécessite un temps O(m + nlog n). Pour obtenir de meilleurs résultats, nous devons considérer une structure de données différente.

[modifier] Solution utilisant des forêts

On considère maintenant une structure de données dans laquelle chaque classe est représentée par un arbre dans lequel chaque nœud contient une référence vers son nœud père. Une telle structure de forêt a été introduite par Bernard A. Galler et Michael J. Fisher en 1964[1], bien que son analyse détaillée ait attendu plusieurs années.

Dans une telle forêt, le représentant de chaque classe est la racine de l'arbre correspondant. Find se contente de suivre les liens vers les nœuds pères jusqu'à atteindre la racine. Union réunit deux arbres en attachant la racine de l'un à la racine de l'autre. Une manière d'écrire ces opérations est la suivante :

 function MakeSet(x)
     x.parent := null
 
 function Find(x)
     if x.parent == null
        return x
        
     return Find(x.parent)
 
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

Sous cette forme naïve, cette approche n'est pas meilleure que celle des listes chaînées, car les arbres créés peuvent être très déséquilibrés. Mais elle peut être améliorée de deux façons.

La première consiste à toujours attacher l'arbre le plus petit à la racine de l'arbre le plus grand, plutôt que l'inverse. Pour évaluer quel arbre est le plus grand, on utilise une heuristique appelée le niveau : les arbres contenant un élément sont de niveau zéro, et lorsque deux arbres de même niveau sont réunis, le résultat a un niveau plus grand d'une unité. Avec cette seule amélioration, la complexité amortie des opérations MakeSet, Union et Find devient O(logn). Voici les nouveaux codes de MakeSet et Union :

 function MakeSet(x)
     x.parent := null
     x.rank   := 0
 
 function Union(x, y)
     xRoot = Find(x)
     yRoot = Find(y)
     if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot != yRoot
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

La seconde amélioration, appelée compression de chemin, consiste à aplatir la structure d'arbre à chaque fois que l'on utilise Find. L'idée est que chaque nœud rencontré sur le chemin menant à la racine peut être directement relié à la racine; tous ses nœuds ont en effet le même représentant. Pour réaliser ceci, on fait un parcours en direction de la racine de l'arbre, afin de la déterminer, puis un autre parcours pour faire de cette racine le parent immédiat de tous les nœuds rencontrés en chemin. L'arbre résultant est aplati, ce qui améliore les performances de futures accès à ces nœuds, mais aussi à d'autres nœuds pointant vers ceux-ci, directement ou indirectement. Voici l'opération Find améliorée :

 function Find(x)
     if x.parent == null
        return x
  
     x.parent = Find(x.parent)
     return x.parent

Ces deux améliorations sont complémentaires. Conjointement, elles permettent d'atteindre une complexité amortie en temps O(α(n)), où α(n) est l'inverse de la fonction f(n) = A(n,n) et A la fonction d'Ackermann dont la croissance est extrêmement rapide. α(n) vaut moins de 5 pour toute valeur n en pratique[2]. En conséquence, la complexité amortie par opération est de fait une constante.

Il n'est pas possible d'obtenir un meilleur résultat : Fredman et Saks ont montré en 1989 que Ω(α(n)) mots en moyenne doivent être lus par opération sur toute structure de données pour le problème des classes disjointes.


[modifier] Notes et références de l'article

  1. ↑ Bernard A. Galler et Michael J. Fisher, « An improved equivalence algorithm, Communications of the ACM », mai 1964, ACM Digital Library, p. Volume 7, Issue 5, pages 301-303. Consulté le 27 octobre 2007
  2. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp.498–524.
Autres langues