Algorithme de Busacker et Gowen

L'algorithme de Busacker et Gowen est un algorithme de la théorie des graphes, énoncé par John Busacker et Brian Gowen, permettant de résoudre le problème du flot de coût minimum.

Description

Usages

Algorithme de Busacker et Gowen centralisé

L'algorithme de Busacker et Gowen centralisé permet de résoudre le calcul V à un coût minimal dans un graphe G=(X;U) où à chaque arc u de U est associé une capacité maximale Cu et un coût u. En effet, cet algorithme consiste à construire le graphe d'écart et ensuite à rechercher le chemin de coût minimal entre le nœud source s et le nœud de destination t. Si un chemin existe et que la capacité v à atteindre n'est donc pas réalisable, ainsi les variables et le graphe d'écart sont mis à jour. À l'opposé, l'algorithme de Busacker et Gowen recherche par étapes les flots attribués aux arcs appartenant au graphe orienté en procédant de la façon suivante :

1. : rechercher le chemin de coût minimal π du graphe ;
2. : si l'addition des chemins précédemment calculées et la capacité du chemin est supérieure ou égale à la capacité λ désirée, alors l'algorithme se termine ;
3. : sinon, le graphe est mis à jour quel que soit u appartenant à λ :
   1. ajout d'un arc dans le sens opposé de la capacité égale à la différence entre le minimum de la capacité des arcs et du chemin de la capacité de l'arc courant ; et de coût négatif à celui dans le sens initial,
   2. mise à jour de la capacité de l'arc qui est elle-même égale à la capacité de l'arc moins le minimum de la capacité des arcs du chemin ;
4. : retour à l'étape 1.

Algorithme de Busacker et Gowen distribué

La version de l'algorithme de Busacker et Gowen distribué répond au problème de tuyau de coût minimal pour une capacité donnée. Il cherche le chemin de plus faible coût. Ensuite, chaque domaine effectue les mises à jour des arcs comme indiqué dans l'algorithme de Busacker et Gowen centralisé. L'algorithme se termine quand la valeur du flot λ est atteinte ou s'il n'existe plus de chaîne de contrats admissibles permettant de satisfaire λ.

Ainsi, les différences entre les algorithmes de Busacker et Gowen centralisé et distribué sont :

• la fonction objectif optimisée par l'algorithme de Viterbi. Dans le cas de l'algorithme de Ford-Fulkerson, il s'agit de maximiser la capacité de la chaîne contrats alors que dans l'algorithme de Busacker et Gowen, la fonction objectif est une fonction de coût minimisant la somme des prix ;
• la condition d'arrêt : dans le cas de l'algorithme de Busacker et Gowen, le nombre de connexions λ souhaité borne la recherche ;

Ici nous n'avons pas, dans cette approche, considéré qu'il existe une fonction exprimant la consommation de ressources d'une classe mais plutôt qu'une classe de Qualité de Service est associée à un nombre entier de contrats possibles. Dans un contexte centralisé, l'hypothèse initiale de l'existence d'une fonction aurait des répercussions sur le graphe. En effet, il nous faudrait alors considérer un graphe de façon à exprimer la relation entre les différents arcs du graphe orienté puisque la fonction de consommation couple l'utilisation des contrats.

Complexité

Algorithme de Busacker et Gowen centralisé

La complexité de l'algorithme de Busacker et Gowen centralisé est $O(N^{4})$ où N=2n, n étant le nombre de sommets sources ou cibles si l'algorithme de Busacker et Gowen opère dans le contexte d'un problème d'affectation (on veut affecter T tâches à M machines) où le nombre de sommets sources est identique au nombre de sommets cibles.

Algorithme de Busacker et Gowen Distribué

La complexité de l'algorithme de Busacker et Gowen centralisé est $O(N^{4})$. Cette complexité est fonction de celle de recherche du chemin de plus faible coût. Dans le cas de la négociation, dans l'hypothèse que les classes de Qualité de Service répondent à des critères établis conjointement. Le nombre d'itération est quant à lui fonction du nombre de connexions souhaitées et des capacités de flores des chemins admissibles. Le pire des cas se produit si toutes les chaînes de contrats sont distinctes c'est-à-dire si elles ne partagent pas de classes de Qualité de Service.

Variantes

Une variante de l'algorithme de Busacker et Gowen est celui de Ford-Fulkerson. L'algorithme de Ford-Fulkerson consiste en une procédure itérative qui permet de déterminer un flot (ou flux) 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. 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, touriers, ferroviaires, etc. Il s'applique également à tous les autres problèmes de transferts comme importations/exportations, les flux migratoires, démographiques mais aussi sur les flux plus abstraits tels que les transferts financiers. Pour les données de très grande taille, il existe plusieurs algorithmes plus performants pour résoudre le même problème connu sous le nom de problème de flot maximum.

Voir aussi

Article connexe

• Algorithme de Dijkstra (sert à résoudre le problème du plus court chemin)

Liens externes

• (en) Algorithme en pseudo-code sur stackoverflow.com
• Jean-Luc Raffy, Problème du flot de coût minimal / Algorithme de Busacker et Gowen, cours en ligne
• Rodolphe Giroudeau et Hervé Dicky, « Cours Algorithmique/Complexité/Calculabilité », sur lirmm, 2010