Algorithme de poussage/réétiquetage

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986[1]. L'algorithme général a une complexité en temps en O(|V|^2 |E|) (ici V est l'ensemble des sommets, et E l'ensemble des arcs du graphe); un implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en O(|V|^3); une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité O(|V|^2\sqrt{|E|}). Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un link/cut tree (en) donne un temps d'exécution majoré par O(|V| |E| \log(|V|^2/|E|)). Tous ces temps sont meilleurs que la majoration en O(|V| |E|^2) qui est celle de l'algorithme d'Edmonds-Karp.

Présentation générale[modifier | modifier le code]

Sur chaque arc, la valeur du flot et la capacité. Le capacité de l'arc opposé est nulle (sauf s'il existe déjà), la valeur du flot son opposée.
Réseau résiduel. La capacité résiduelle est la différence entre la capacité et le flot.

Dans un réseau, le flot entrant dans un sommet doit être égal à celui qui en sort (à l'exception des deux sommets qui sont la source et le puits). C'est le principe de conservation de flot, aussi appelé loi de Kirchhoff. On ne peut donc pas « accumuler » des valeurs à l'intérieur du réseau. Un préflot est une notion dans laquelle cette condition de conservation est affaiblie, en autorisant les sommets à avoir une valeur de flot entrant plus importante que celle du flot sortant. La différence est appelée l'excédent du sommet. Un sommet à excédent est positif est dit actif. L'excédent de flot peut être diminué par transfert sur les arcs du graphe résiduel. Le flot est « poussé » (pushed) à travers le réseau en respectant une valeur appelée hauteur des sommets[2]. Les hauteurs sont une approximation de la distance au puits; le flot n'est poussé que vers des distances au puits plus courte. Un étiquetage est dit valide si il respecte la propriété Ch(u) \leq h(v) +1, avec h(u) la hauteur du sommet u, et où v est dans l'ensemble des voisins de u dans le graphe résiduel. Autrement dit, un sommet u doit avoir une hauteur inférieure à la hauteur augmentée de 1 de n'importe lequel de ses voisins.

L'action de « pousser » consiste à transférer un peu du flot sur un arc résiduel d'un sommet u vers un voisin v pour lequel h(u) = h(v)+1 . Une poussée est dite saturante si elle épuise toute la capacité de l'arc résiduel (u,v) qui est alors ôté du graphe résiduel. Dans le cas contraire, la poussée est dite non saturante et vide la totalité de l'excédent du sommet u. Si plus aucune poussée n'est possible, on tente d'augmenter la hauteur des sommets par une opération appelée « réétiquetage ».

Définitions[modifier | modifier le code]

Soit G = ((V,E),c,s,t) un réseau; c(u,v) et f(u,v) dénotent respectivement la capacité et le flot sur un couple (u,v).

  • contrainte de capacité: on a \ f(u,v) \le c(u,v). Le flot sur un arc est toujours inférieur à sa capacité.
  • antisymétrie: \ f(u,v) = - f(v,u). Le flot de u à v est l'opposé du flot de v à u.
  • conservation du flot: \ \sum_{w \in V} f(u,w) = 0, sauf pour u=s ou \ u=t. Le flot pour un sommet est nul, sauf pour la source qui « produit » le flot et le puits qui le « consomme ».

Un préflot satisfait les deux premières conditions, mais la troisième seulement sous une forme affaiblie durant l'exécution de l'algorithme; à la fin de la procédure, la règle de conservation du flot est à nouveau respectée.

L'excédent d'une fonction f sur V\times V est la fonction \operatorname{ex}_f ou plus simplement \operatorname{ex} définie sur V par :

\operatorname{ex}_f(u)=\sum_{w \in V} f(u, w).

Si f est un flot, l'excédent en tout sommet autre que la source et le puits est nul. Un sommet est actif si son excédent est strictement positif. Pour un préflot f, la condition de conservation du flot est remplacée par l'inégalité

\operatorname{ex}_f(u) \geq 0 pour tout sommet u \neq s.

Cela signifie qu'il y a plus de flot (au sens large) qui entre dans un sommet qu'il n'en ressort.

La capacité résiduelle d'un arc, notée r(u,v) est définie par r(u,v)=c(u,v) - f(u,v)>0 si (u,v) est un arc, et par r(u,v)= f(v,u) sinon. Un arc résiduel est un arc dont la capacité résiduelle est positive. Le graphe résiduel est le graphe des arcs résiduels.

Une hauteur est une fonction h sur les sommets qui vérifie : h(s)= n, h(t)=0 (n est le nombre de sommets) et

h(u)\le h(v)+1 pour tout arc résiduel (u,v).

Une hauteur est une estimation de la distance d'un sommet au puits. On dit aussi que cette fonction est un étiquetage admissible.

L'algorithme de poussage/réétiquetage[modifier | modifier le code]

Poussage[modifier | modifier le code]

L'opération de poussage peut s'appliquer à un arc (u, v) pourvu que h(u)=h(v)+1, et si de plus \operatorname{ex}(u)>0 (u est actif) et r(u,v)>0. Dans ces conditions, on peut décharger une quantité de flot le long de cet arc; cette quantité est le minimum entre ce qui est disponible en u, à savoir l'excédent \operatorname{ex}(u) et ce que l'arc peut absorber, à savoir r(u,v)=c(u,v) - f(u,v). Formellement on obtient :

fonction pousser(u,v)
   m = min(ex(u), r(u,v));
   ex(u) = ex(u) - m;                   diminuer l'excédent du sommet courant de m
   ex(v) = ex(v) + m;                   augmenter l'excédent du sommet destination
   f(u,v) = f(u,v) + m;                 augmenter le flot de l'arc (u,v)
   f(v,u) = f(v,u) - m;                 diminuer le flot sur l'arc opposé


Réétiquetage[modifier | modifier le code]

Réétiqueter un sommet u consiste à augmenter sa hauteur d'une quantité qui la rend d'une unité plus grande que la plus petite des hauteurs de ses voisins dans le graphe résiduel. Après réétiquetage, h(u) atteint la plus grande valeur pour laquelle la condition d'admissibilité, à savoir h(u)\le h(v)+1 est satisfaite. Pour appliquer un réétiquetage, on demande en plus que le sommet u soit actif. Formellement on obtient :

fonction réétiqueter(u)
   h(u) = 1+ min{h(v) | v voisin de u, r(u,v) > 0};

Poussage/réétiquetage[modifier | modifier le code]

L’algorithme générique de poussage/réétiquetage commence par une initialisation : la hauteur de tout sommet autre que la racine est définie comme étant nulle, et pour la racine s, on définit h(s)=|V|. Le préflot initial est comme étant nul sur tous les arcs sauf ceux sortant de la source, et f(s,v)=c(s,v) pour tout arc (s,v). L'algorithme a la structure suivante:

algorithme pousser-réétiqueter(G(V,E),s,t) 
   Initialisation();
   tantque il existe des sommets actifs 
       pousser ou réétiqueter;

Si l'on exécute les fonctions de poussage e réétiquetage aussi longtemps qu'il y a des sommets actifs, et dans n'importe quel ordre, on obtient, à la fin, un flot qui est maximum. On peut montrer que pour tout ordre d'exécution, le temps d'exécution est en O(|V|^2 |E|). Un examen plus approfondi montre que l’algorithme est ralenti par les poussages non saturants.

Algorithme de « réétiquetage vers l'avant »[modifier | modifier le code]

L'algorithme de « réétiquetage vers l’avant » est une spécialisation de l'algorithme générique de poussage/réétiquetage qui améliore le temps d'exécution en le faisant passer de O(|V|^2|E|) àO(|V|^3). Pour cela, les opérations de poussage et réétiquetage sont exécutées dans un ordre particulier. La différence principale est que le poussage/ réétiquetage est répétitivement appliqué à un même somme jusqu'à ce que son excédent ait disparu. Ceci diminue le nombre de poussages non saturants qui constituent le goulot d'étranglement de cet algorithme.

L’algorithme réétiqueter-vers-l’avant gère une liste des sommets du réseau autres que la source et le puits. L’algorithme parcourt la liste depuis son début, choisit un sommet actif u puis en le « décharge », c’est-à-dire effectue des opérations de poussage et de réétiquetage jusqu’à ce que le sommet n’ait plus d’excédent. Chaque fois qu’un sommet est réétiqueté, il est replacé en début de liste (d’où le nom « réétiquetage-vers-l’avant ») et l’algorithme commence un nouveau parcours de la liste.

Décharge[modifier | modifier le code]

La décharge d'un sommet u est décrite dans la fonction que voici :

fonction décharger(u):
    tantque ex(u) > 0:
       pour tout voisin v de u 
          pousser(u, v);
       réétiqueter(u);

Réétiqueter vers l’avant[modifier | modifier le code]

L'algorithme commence par un poussage de la source vers se voisins, puis décharge les sommets actifs, en prenant soin de mettre en tête les sommets dont la hauteur augmente.

algorithme réétiqueter-vers-l’avant(G(V,E),s,t):
   pour tout voisin v  de s
      pousser(s,v);              ceci sature les arcs (s,v) puisque le flot partant de s n'est pas limité 
   L = Liste(V-{s,t});           créer une liste des sommets
   u = L.tête;
   tantque (u != NIL):
      H = h(u);
      décharger(u);
      si h(u) > H
         placer u en tête de L
      sinon
         u = u.suivant;

On peut montrer que cet algorithme est en O(|V|^3).

Améliorations[modifier | modifier le code]

Si l'on choisit toujours un sommet actif v de hauteur maximale, on peut réduire, moyennant une gestion appropriée des sommets, le temps à \mathcal{O}(n^2 \sqrt{m}). Ici, n=|V| est le nombre de sommets et m=|E| est le nombre d'arcs. Avec des structures de données plus élaborées, réduire le temps à

O(n\, m\, \log_{2+\frac{m}{n \log m}} n),

et

\mathcal{O}(k \, m \, \log \bigl(\frac{n^2}{m}\bigr) \ \log (c_{\max})),

k=\min\{\sqrt{m}, \sqrt[3]{n^2}\} et c_{\max} et le maximum des capacités des arcs[3].

Notes et références[modifier | modifier le code]

  1. Goldberg et Tarjan 1986.
  2. Le terme « hauteur » est préconisé par Cormen et. al. Korte et Vysen utilisent « étiquette de distance ».
  3. Korte et al. 2010

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Push–relabel maximum flow algorithm » (voir la liste des auteurs)

Bibliographie[modifier | modifier le code]

  • Bernard H. Korte et Jens Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, coll. « Algorithms and Combinatorics » (no 21),‎ 2008 (ISBN 978-3-540-71844-4), « 8.4 Blocking Flows and Fujishige's Algorithm », p. 174–176. Traduction française: Bernard Korte, Jens Vygen (auteurs), Jean Fonlupt et Alexandre Skoda (traducteurs), Optimisation combinatoire: Théorie et algorithmes, Springer-France, coll. « IRIS »,‎ 2010 (ISBN 978-2-287-99036-6), « 8.5 Algorithme de Goldberg-Tarjan », p. 182–187.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge, MIT Press and McGraw-Hill,‎ 2001, 2e éd. (ISBN 978-0-262-53196-2, LCCN 2001031277), chap. 26 (« chap. 26 Flows »), p. 643–700. Traduction francaise : Introduction à l'algorithmique, 2e éd., Dunod 2002, « chapitre 26. Flot Maximum ».
  • Andrew V. Goldberg et Robert E. Tarjan, « A new approach to the maximum flow problem », Proceedings of the eighteenth annual ACM symposium on Theory of computing,‎ 1986, p. 136–146 (ISBN 0-89791-193-8, DOI 10.1145/12130.12144).