Algorithme de Ford-Fulkerson
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

L' algorithme de Ford-Fulkerson, du nom de ses auteurs L.R. Ford et D.R. Fulkerson, consiste en une procédure itérative qui permet de déterminer un flux (ou flot) de valeur maximale (ou minimale) à partir d'un flot constaté. Il s'agit donc d'un problème d'optimisation classique dans le domaine de la recherche opérationnelle (La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l'ensemble des méthodes et techniques rationnelles d'analyse et de synthèse des phénomènes d'organisation...).

Ce problème d'optimisation peut être représenté par un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) comportant une entrée (à gauche) et une sortie (à droite). Le flot représente la circulation (La circulation routière (anglicisme: trafic routier) est le déplacement de véhicules automobiles sur une route.) 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 (Le mot flux (du latin fluxus, écoulement) désigne en général un ensemble d'éléments (informations / données, énergie, matière, ...) évoluant dans un sens commun. Plus précisément le terme est...) migratoires, démographiques mais aussi sur les flux plus abstraits tels que les transferts financiers.

Exemple

Une société de fret (Le transport de marchandises est une activité économique réglementée, à la fois par chaque pays et au niveau international.) dispose de 3 centres : un à Paris (Paris est une ville française, capitale de la France et le chef-lieu de la région d’Île-de-France. Cette ville est construite sur une boucle de la Seine, au centre du bassin parisien, entre les confluents de la Marne et de la...), 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 une capacité maximale de transport (Le transport est le fait de porter quelque chose, ou quelqu'un, d'un lieu à un autre, le plus souvent en utilisant des véhicules et des voies de communications (la route, le canal ..). Par assimilation,...) ainsi qu'un stock initial de marchandises. De même, chaque pays (Pays vient du latin pagus qui désignait une subdivision territoriale et tribale d'étendue restreinte (de l'ordre de quelques centaines de km²), subdivision de la civitas gallo-romaine. Comme la...) d'arrivée a une demande maximale pour les importations.

L'algorithme de Ford-Fulkerson (L' algorithme de Ford-Fulkerson, du nom de ses auteurs L.R. Ford et D.R. Fulkerson, consiste en une procédure itérative qui permet de déterminer un flux (ou flot) de valeur maximale (ou minimale) à...) va permettre d'optimiser ces flux à l'aide d'un outil (Un outil est un objet finalisé utilisé par un être vivant dans le but d'augmenter son efficacité naturelle dans l'action. Cette augmentation se traduit par la simplification des actions...) de modélisation mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les mathématiques...). La structure sous-jacente est représentée par un graphe orienté dont le sommet de gauche symbolise le stock initial. Celui-ci est relié à chacun des premiers arcs ou arêtes.

Dans l'exemple présent, la matrice associée porte donc dans sa première colonne les valeurs des dits stocks. Inversement, à l'extrémité de la chaîne (Le mot chaîne peut avoir plusieurs significations :), la matrice associée comprendra dans sa dernière colonne les demandes respectives des pays cités. Les sommets centraux comprendront les différentes combinaisons de fret maximal d'un point (Graphie) à l'autre.

Le problème peut être généralisé à toute circulation dans un réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un filet (un réseau est un « petit rets »,...) (véhicules, fluides, monnaie, etc. Les grandeurs mathématiques remplaçant indistinctement les faits réels qu'elles sont censées représenter.

Algorithme

Il s'agit d'un algorithme itératif. A 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.

Considérons un flux possible dont les sous-ensembles sont les différents flux associés à chaque arête ou arc du graphe. A chaque itération de la boucle, deux sous procédures viennent compléter le processus :

  • le "marquage" qui consiste à tester si une amélioration du flux est possible.
  • le changement de flux, soit la procédure qui donne la meilleure solution à partir de l'observation (L’observation est l’action de suivi attentif des phénomènes, sans volonté de les modifier, à l’aide de moyens d’enquête et...) précédente.

En pseudo-code (En programmation, le pseudo-code est une façon de décrire un algorithme sans référence à un langage de programmation en particulier.) informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport...), l'algorithme peut se présenter ainsi :

  • initialisation
  • tant que les sommets ne sont pas marqués
    • sélectionner un sommet non marqué, tous les précédents ayant été marqués et en déterminer la marque
    • mettre à jour (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la période entre deux nuits, pendant laquelle les rayons du Soleil éclairent le ciel. Son début (par...) l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble),...) des sommets marqués
  • fin
Page générée en 0.124 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique