AccueilđŸ‡«đŸ‡·Chercher

Algorithme de Ford-Fulkerson

En informatique, l'algorithme de Ford-Fulkerson est un algorithme pour le problÚme de flot maximum, un problÚme d'optimisation classique dans le domaine de la recherche opérationnelle. Il est dû à Lester Randolph Ford junior et D. R. Fulkerson[1] et c'est une variante de l'algorithme de Busacker et Gowen.

Exemple d'exécution de l'algorithme de Ford-Fulkerson. L'animation affiche le graphe résiduel correspondant à chaque itération.

ProblĂšme du flot maximum

DĂ©finition du problĂšme

Ce problĂšme d'optimisation peut ĂȘtre reprĂ©sentĂ© par un graphe comportant une entrĂ©e (Ă  gauche) et une sortie (Ă  droite). Le flot reprĂ©sente la circulation de l'entrĂ©e vers la sortie d'oĂč l'utilisation de cet algorithme dans les problĂšmes de rĂ©seaux. Les applications sont multiples : problĂšmes informatiques, routiers, ferroviaires, etc. Il s'applique Ă©galement Ă  tous les autres problĂšmes de transferts comme les importations/exportations, les flux migratoires, dĂ©mographiques mais aussi sur des flux purement numĂ©riques tels que les transferts financiers. Pour les donnĂ©es de trĂšs grande taille, il existe plusieurs algorithmes plus performants pour rĂ©soudre le problĂšme de flot maximum.

Exemple d'application

Une sociĂ©tĂ© de fret dispose de trois centres : un Ă  Paris, le deuxiĂšme Ă  Lyon, le troisiĂšme Ă  Marseille. Trois destinations sont possibles : la Pologne, la SuĂšde, la GrĂšce. Chacun des centres de fret a un stock initial de marchandises (Paris : 100 ; Lyon : 80 ; Marseille : 150). De mĂȘme, chaque pays d'arrivĂ©e a une demande maximale pour les importations (Pologne : 120 ; SuĂšde : 140 ; GrĂšce : 50).

L'algorithme de Ford-Fulkerson va permettre d'optimiser ces flux à l'aide d'un outil de modélisation mathématique. La structure sous-jacente est représentée par un graphe orienté dont le sommet de gauche symbolise le stock initial. Trois arcs en partent, chacun menant à un sommet représentant un centre de fret. Le sommet final symbolise la fin de la livraison, auquel mÚnent trois arcs venant de sommets représentant une destination de livraison.

Dans l'exemple présent, la matrice d'adjacence porte donc dans sa premiÚre ligne les valeurs desdits stocks. Inversement, à l'extrémité de la chaßne, la matrice associée comprendra dans sa derniÚre colonne les demandes respectives des pays cités. Entre les sommets « centre de fret » et les sommets « destination » peuvent se trouver des sommets et des arcs intermédiaires, les capacités de ces arcs correspondant au fret maximal d'un point à l'autre.

             Paris                        Pologne
           /       \                     /       \
    100 ---         -------  ...  -------         ---- 120
       /   80               NƓuds               140   \
Départ ------- Lyon ------ intermé- ---- SuÚde -------- Fin
       \                   diaires                    /
    150 ---         -------  ...  -------         ---- 50
           \       /                     \       /
           Marseille                       GrĂšce

Le problĂšme peut ĂȘtre gĂ©nĂ©ralisĂ© Ă  une circulation dans un rĂ©seau (vĂ©hicules, fluides, monnaie, etc.), les grandeurs mathĂ©matiques remplaçant indistinctement les faits rĂ©els qu'elles sont censĂ©es reprĂ©senter.

RĂ©seau

Soit un réseau avec :

  • un graphe orientĂ© irrĂ©flexif ;
  • une capacitĂ© avec pour convention : si l'arc n'existe pas, ;
  • un sommet source s sans arcs entrants ;
  • un sommet puits t sans arcs sortants.

On suppose qu'il n'y a pas d'arcs anti-parallĂšles, c'est-Ă -dire que l'existence d'un arc exclut l'existence d'un arc .

Flot

Le flot d'un réseau est une fonction qui vérifie :

  • pour tous sommets , on a ;
  • pour tout sommet tel que et : (le flot entrant est Ă©gal au flot sortant : propriĂ©tĂ© de conservation).

La valeur d'un flot f est .

Algorithme

Il s'agit d'un algorithme itĂ©ratif. À chaque itĂ©ration, la solution courante est un flot qui satisfait les contraintes de capacitĂ© (c'est donc un flot rĂ©alisable) et l'algorithme essaie d'augmenter la valeur de ce flot. Cela peut nĂ©cessiter d'annuler les mauvais choix. Pour ce faire, on dĂ©finit le graphe rĂ©siduel de G et de f qui indique les modifications possibles (ajout ou annulation) : c'est un graphe pondĂ©rĂ© oĂč on a

et .

Pseudo-code

  Entrée Un réseau 
  Sortie Un flot maximal f
  Fonction Ford_Fulkerson()
      flot nul
     Tant que il y a un chemin simple  de s à t dans le graphe résiduel  :
        
        Pour toute arĂȘte  :
           Si  :
              
           Sinon :
              
     Renvoyer f

L'algorithme ne précise pas comment trouver chaque chemin . L'algorithme d'Edmonds-Karp, spécialisation de l'algorithme de Ford-Fulkerson, propose de faire un parcours en largeur.

Chaque chemin trouvĂ© est garanti d’augmenter la valeur du flot, car il commence forcĂ©ment par un arc sortant du sommet source et finit par un arc entrant dans le sommet puits.

Exemple d'exécution

On considĂšre le rĂ©seau de flot , consistant du graphe Ă  quatre sommets et cinq arĂȘtes , de la source , du puits et de la fonction de capacitĂ© .

On commence avec le flot vide qui attribue la valeur Ă  chaque arĂȘte. Initialement, le graphe rĂ©siduel et les capacitĂ©s rĂ©siduelles correspondent alors exactement au rĂ©seau avec les capacitĂ©s .

Graphe (avec capacité )
4
1
2
6
3
Flot
0
0
0
0
0
Graphe résiduel (avec capacité résiduelle )
40
10
20
60
30
Supposons que l'algorithme choisisse d'abord le chemin (bleu). Le long de ce chemin, on peut augmenter le dĂ©bit au maximum de puisque l'arĂȘte est limitante (). Il en rĂ©sulte un nouveau flot (qu'on appellera toujours ) avec .

L'arĂȘte a une capacitĂ© de . Elle est utilisĂ©e dans le flot : . Dans le graphe rĂ©siduel, sa capacitĂ© rĂ©siduelle sera donc . De mĂȘme et .

Les trois arĂȘtes sont strictement positives dans le flot. Ces poids dans le flot ne sont peut ĂȘtre pas les plus optimaux. Les nouvelles arĂȘtes arriĂšres (en rouge) dans le graphe rĂ©siduel marquent alors le fait que l'on pourra toujours diminuer le flot sur ces arĂȘtes.

Chemin améliorant (avec capacités résiduelles )
Flot
3
0
0
3
3
Graphe résiduel résultant (avec les nouvelles capacités résiduelles )
13
10
20
33
03
Supposons que l'algorithme sĂ©lectionne le chemin amĂ©liorant . L'augmentation maximale du dĂ©bit est limitĂ©e par la capacitĂ© rĂ©siduelle . Pour la premiĂšre fois, on passe par un arĂȘte arriĂšre (). Alors que le flot f augmente de 1 le long des arĂȘtes (s,v) et (u,t), il diminue de 1 le long de (u,v).

On peut remarquer que les capacitĂ©s rĂ©siduelles des arĂȘtes arriĂšres sont toujours Ă©gales aux poids dans le flot.

Chemin améliorant (avec capacités résiduelles )
Flot
3
1
1
3
2
Graphe résiduel résultant (avec les nouvelles capacités résiduelles )
13
01
11
33
12
Supposons que l'algorithme choisisse Ă  nouveau le chemin . Cette fois, le dĂ©bit le long du chemin ne peut ĂȘtre augmentĂ© que de 1. Cela correspond justement au montant par lequel on a diminuĂ© (u,v) Ă  l'Ă©tape prĂ©cĂ©dente. En effet, l'algorithme peut faire beaucoup de va-et-vient. Chemin amĂ©liorant (avec capacitĂ©s rĂ©siduelles )
Flot
4
1
1
4
3
Graphe résiduel résultant (avec les nouvelles capacités résiduelles )
04
01
11
24
03
Ici, seul le chemin est possible. Cela augmente alors le dĂ©bit de 1. Le flot a alors une valeur de . Les arĂȘtes sortantes de la source sont pleinement utilisĂ©es donc ce flot est un flot maximal. La coupure au niveau de (s,u) et (s,v) est donc une coupe minimale. On respecte donc bien le ThĂ©orĂšme flot-max/coupe-min qui affirme qu'un flot maximal a la mĂȘme valeur qu'une coupe minimale.

L'algorithme se termine alors car aucun chemin de s à t n'existe dans le graphe résiduel obtenu. On a donc bien obtenu un flot maximal.

Chemin améliorant (avec capacités résiduelles )
Flot maximal
4
1
2
5
3
Graphe résiduel résultant (avec les nouvelles capacités résiduelles )
04
01
02
15
03

Propriétés de l'algorithme

Complexité

Le flot maximal est atteint quand plus aucun chemin amĂ©liorant ne peut ĂȘtre trouvĂ©. Cependant, il n'y a aucune certitude que cette situation soit atteinte, mais la rĂ©ponse sera correcte si l'algorithme se termine. Dans le cas oĂč l'algorithme s'exĂ©cute indĂ©finiment, le flot peut mĂȘme ne pas converger vers le flot maximum. NĂ©anmoins, cette situation ne se produit qu'avec des valeurs de flot irrationnelles. Lorsque les capacitĂ©s sont des entiers, le temps d'exĂ©cution de l'algorithme de Ford-Fulkerson est bornĂ© par (voir les notations de Landau), oĂč est le nombre d'arĂȘtes dans le rĂ©seau de flot et est la valeur du flot maximal. En effet, chaque chemin augmentant peut ĂȘtre trouvĂ© en et augmente le dĂ©bit d'une quantitĂ© entiĂšre d'au moins avec comme borne supĂ©rieure.

Une variante de l'algorithme de Ford-Fulkerson avec terminaison garantie et un temps d'exécution indépendant de la valeur de flot maximal est l' algorithme d'Edmonds-Karp, qui a une complexité temporelle en .

Terminaison

Si les capacitĂ©s des arĂȘtes sont des entiers, l'algorithme se termine.

On peut le démontrer par l'absurde, en supposant que l'algorithme ne se termine pas. En considérant la suite des flots calculés, on distingue plusieurs propriétés :

  • la suite est strictement croissante ;
  • elle est majorĂ©e par la valeur du flot maximal ;
  • elle est Ă  valeurs entiĂšres.

Cette suite entiÚre est infinie, majorée et strictement croissante, ce qui est absurde.

Exemple pour lequel l'algorithme ne termine pas

On s'intĂ©resse au graphe suivant, qui a pour sommet source , pour sommet puits . Les arĂȘtes , et ont pour capacitĂ©s respectives , et . La capacitĂ© des autres arĂȘtes est fixĂ©e Ă  . On a choisi la constante de sorte que . On considĂšre l'exĂ©cution de l'algorithme choisissant les chemins suivants, oĂč on note , et .

ÉtapeChemin choisiAugmentation du flotCapacitĂ© residuelle
0
1
2
3
4
5

On remarque qu'aprĂšs les Ă©tapes 1 et 5, les capacitĂ©s rĂ©siduelles des arĂȘtes , et sont respectivement de la forme , et et le flot ajoutĂ© est oĂč . Ainsi, par rĂ©currence on pourra toujours rĂ©pĂ©ter la boucle de chemins , , et tout en ajoutant un flot strictement positif car les capacitĂ©s rĂ©siduelles resteront toujours de la forme , et Ă  la fin de l'exĂ©cution sur les chemins. L'algorithme ne termine donc pas sur cette entrĂ©e. Le fait que l'on ait une capacitĂ© non entiĂšre est cruciale car elle permet d'avoir une suite de taille de flot infinie strictement croissante et majorĂ©e[2].

Notes et références

  1. (en) L. R. Ford et D. R. Fulkerson, « Maximal Flow Through a Network », Canadian Journal of Mathematics, vol. 8,‎ 1956/ed, p. 399–404 (ISSN 0008-414X et 1496-4279, DOI 10.4153/CJM-1956-045-5, lire en ligne, consultĂ© le )
  2. Uri Zwick, « The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate », Theoretical Computer Science, vol. 148, no 1,‎ , p. 165–170 (DOI 10.1016/0304-3975(95)00022-O AccĂšs libre)

Voir aussi

Article connexe

  • L'algorithme d'Edmonds-Karp est une spĂ©cialisation de l'algorithme de Ford-Fulkerson de rĂ©solution du problĂšme de flot maximum dans un rĂ©seau.

Liens externes

Bibliographie

  • A simple algorithm for finding maximal network flows and an application to the Hitchock problem (FORD L.R., FULKERSON D.R), Rand Report Rand Corporation, Santa Monica, .
  • Lester R. Ford et Delbert R. Fulkerson, « Maximal flow through a network », Canadian journal of Mathematics, vol. 8, no 3,‎ , p. 399-404
  • The transhipment problem (ORDEN A.), Management Science 2, 1956.
  • Sur la dĂ©ficience d'un rĂ©seau infini (BERGE C.), Comptes rendus de l'AcadĂ©mie des Sciences 245, 1957.
  • Invitation Ă  la recherche opĂ©rationnelle (KAUFMANN A., FAURE R.) Dunod Entreprise, 1979.
  • Contribution de la thĂ©orie des graphes Ă  l'Ă©tude des problĂšmes d'ordonnancement (ROY B.) CongrĂšs international de recherche opĂ©rationnelle, 1960.
  • Lester Randolph Ford et Delbert Ray Fulkerson, Flows in Networks, Princeton, NJ, Princeton University Press,
  • Ravindra K. Ajuha, Thomas L. Magnanti et James B. Orlin, Network flows - theory, algorithms and applications, Prentice Hall,
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to algorithms, MIT Press,
  • Jon Kleinberg et Eva Tardos, Algorithms design, Pearson Education India,
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.