Algorithme de calcul du flot maximum

Discutez d'informatique ici !
thedream01
Membre Relatif
Messages: 289
Enregistré le: 20 Avr 2007, 12:57

algorithme de calcul du flot maximum

par thedream01 » 13 Mar 2008, 16:25

Bonjour!
Est-ce que quelqu'un pourrait m'expliquer cet algorithme svp?!(algorithme de ford-fulkeson)
merci



Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 13 Mar 2008, 17:07

Dit plutot quelle etape t'achappe dans l'algo, ca evitera de se perdre dans une explication sans fin.

Rappel vulgaire de l'algo :

1/ Recherche d'un flot quelconque initial qui respecte les contraintes
2/ Etape de marquage (permet de verifier si le flot est max ou pas)
3/ Augmentation du flot par deplacement de flux et retour a l'etape 2

thedream01
Membre Relatif
Messages: 289
Enregistré le: 20 Avr 2007, 12:57

par thedream01 » 13 Mar 2008, 17:52

Le problème est que je n'ai pas d'exemples!
Je voudrai bien avoir un exemple avec les étapes détaillées...

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 13 Mar 2008, 18:08

tapes "ford-fulkeson" dans google, a mon avis tu trouveras facilement des exemples déroulés. Cet algo est un grand classique.

thedream01
Membre Relatif
Messages: 289
Enregistré le: 20 Avr 2007, 12:57

par thedream01 » 13 Mar 2008, 18:28

C'est ce que j'ai fait...
Mais par exemple pour ce site:
http://www.math-info.univ-paris5.fr/~seret/Algo5-cours4.pdf

Je ne comprends pas le passage du diapo 6 à 7! C'est quoi le 2?

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 13 Mar 2008, 18:35

thedream01 a écrit:C'est ce que j'ai fait...
Mais par exemple pour ce site:
http://www.math-info.univ-paris5.fr/~seret/Algo5-cours4.pdf

Je ne comprends pas le passage du diapo 6 à 7! C'est quoi le 2?


Vois le graph comme un reseau de plomberie, où les couts sur les arcs sont le débit max de flotte qu'on peut faire passer.
La il recherche un flot de départ compatible avec les contraintes des arcs, pour commencer, il fait passer un débit de 2 sur le chemin du haut, rien de plus. Pourquoi il met pas plus que 2? parceque sur ce chemin, l'un des arcs (E,H) limite le flot a 2.

thedream01
Membre Relatif
Messages: 289
Enregistré le: 20 Avr 2007, 12:57

par thedream01 » 13 Mar 2008, 18:49

les chemins sont choisis de façon aléatoires?
Et C'est quoi les lettres qu'on a rajouté sur le diapo 10?

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 13 Mar 2008, 19:01

thedream01 a écrit:les chemins sont choisis de façon aléatoires?
Et C'est quoi les lettres qu'on a rajouté sur le diapo 10?


Non pour trouver un flot initial tu procedes comme suit :
Cherche un chemin qui relit la source et le puit, fait passer un flot valant le min du cout des arcs sur le chemin.
Tu refait ca autant de fois que tu le désire (enretirant a chaque cout des arcs du chemin la valeur de ton flot) et t'obtiens un flot initial. Si tu fais cette étape jusqu'a que tu ne puisse plus trouver de chemin, dans ce cas la tu part d'une bonne solution initiale et le deroulement de l'algo sera plus rapide.

Les lettres c'est pour la phase de marquage. Ca va permetre de dire ou y a encore possibilité d'augmenter un flot et ou il faudrait les diminuer pour optimiser notre flot global.

Dans le transparent 3 ils t'expliquent comment sont marqué les sommets.

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite