R.K.Ahuja & James B.Orlin (1988)

Un algorithme simple et rapide pour

le problème de Flot MaximumR.K.Ahuja & James B.Orlin

(1988)

2

Jadis, naguère, autrefois, ...• Fulkerson & Dantzig (1955 1956)• Multiples approches

– Augmentations de flots [Ford/Fulkerson 1956]– Préflots et réseau par couches [Karzanov 1974]– Arbres dynamiques (pires cas) [Sleator/Tarjan 1983]– Préflots (couches) et pousse flots plus près du puits en

terme de distance étiquetée [Goldberg/Tarjan 1985]• Meilleurs résultats (pour graphes épars) grâce à

une excellente utilisation des arbres dynamiques

IFT6542 - A07 - Présentation - Nicola Grenon

3

Mal de tête ...


4.4

4.4.1

4.5

4

Faudrait pas zoublier!• s, t, n, m, U, etc.• On assume quelques bases s.p.g., dont:

– Pas de chemin de capacité infinie (teste en O(m))– Si un uij infini, on peut poser = autres uij

• U, un entier et O(nk)• Basé sur Goldberg & Tarjan [1985]• Approche par phases (scaling) [Edmonds/Karp]

... utilisé pour flot à coût minimum ( )• Arc admissible si d(i)=d(j)+1

– Où la définition de la fonction de distance d est:d(t)=0 et d(i)d(j)+1 (i,j)A où rij >0


log2 U

5

L'eau à la bouche...• O(nm+n2logU)• Facile à implanter• Faible coût constant (overheads)• S'implante bien en parallèle


Poussée de préflots(Preflow-Push Algorithm)

Premier algorithme

7

C’est quoi l’idée?L’algorithme va agir ainsi:• À chaque itération, sauf la première et la

dernière, il y aura toujours au moins un noeud actif (un is,t avec un excès positif), on va donc conserver un préflot à chaque itération.

• On va pousser les excès présents à chaque noeud «vers» le puits.

• Si on n'arrive pas à «rapprocher» du flot d'un noeud en excès, on va reétiqueter celui-ci comme étant un pas plus loin.


8

Pseudotrucprocedure poussée_de_préflot (entrée: G=(V,A); sortie: x)début

{initialisation}pour tout iV, s,t

d(i):=1 et e(i):=0 {possible un peu mieux}

d(s):=n d(t):=0

pour tout (s,j)V+(s)xsj:=usj {ajuster e(j)}

{corps}tant que e(i)>0 où is,t {noeud actif}début

choisir un noeud actifsi il y a un arc admissible dans V+(i)début

choisir un arc (i,j) admissiblepousser =min{e(i),rij} sur (i,j) {ajuster

xij, e(i), e(j)}finsinon

d(i):=min{d(j)+1|(i,j)V+(i) et rij>0} {rij du graphe résiduel}

finfin


9

Tits dessins ...


TS

2

1

d=1e=0

d=1e=0

d=0

d=n=4

[7]

[4] [5][3]

flot[capacité]d=distancee=excès

Actif: e(i)>0Admissible: d(i)=d(j)+1reétiquetage: d(i):=min{d(j)+1 de V+(i)|rij>0}Poussée: :=min{e(i),rij}

10

Tits dessins ...


TS

2

1

d=1e=7

d=1e=4

d=0

d=4

[7]

[4] [5][3]



7

4

11

Tits dessins ...


TS

2

1

d=1e=7

d=1e=4

d=0

d=4

3



0

7

0

0

4 5

0

12

Tits dessins ...


TS

2

1

d=1e=7

d=1e=4

d=0

d=4

3



0

7

0

0

4 5

0

13

Tits dessins ...


TS

2

1

d=1e=7

d=1e=4

d=0

d=4

3



0

7

0

0

4 5

0

14

Tits dessins ...


TS

2

1

d=2e=7

d=1e=4

d=0

d=4

3



0

7

0

0

4 5

0

15

Tits dessins ...


TS

2

1

d=2e=7

d=1e=4

d=0

d=4

3



0

7

0

0

4 5

0

16

Tits dessins ...


TS

2

1

d=2e=7

d=1e=4

d=0

d=4

3



0

7

0

0

4 5

0

17

Tits dessins ...


TS

2

1

d=2e=7

d=1e=4

d=0

d=4

3



0

7

0

0

4 5

0

3

18

Tits dessins ...


TS

2

1

d=2e=4

d=1e=7

d=0

d=4

0



3

7

0

0

4 5

0

19

Tits dessins ...


TS

2

1

d=5e=3

d=1e=7

d=0

d=4

0



3

7

0

0

4 5

0

20

Tits dessins ...


TS

2

1

d=5e=3

d=1e=7

d=0

d=4

0



3

7

0

0

4 5

0

3

21

Tits dessins ...


TS

2

1

d=5e=0

d=1e=7

d=0

d=4

0



3

3

4

0

4 5

0

22

Tits dessins ...


TS

2

1

d=5e=0

d=1e=7

d=0

d=4

0



3

3

4

0

4 5

0

23

Tits dessins ...


TS

2

1

d=5e=0

d=1e=7

d=0

d=4

0



3

3

4

0

4 5

0

24

Tits dessins ...


TS

2

1

d=5e=0

d=1e=7

d=0

d=4

0



3

3

4

0

4 5

05

25

Tits dessins ...


TS

2

1

d=5e=0

d=1e=2

d=0

d=4

0



3

3

4

0

4 0

5

26

Tits dessins ...


TS

2

1

d=5e=0

d=1e=2

d=0

d=4

0



3

3

4

0

4 0

5

27

Tits dessins ...


TS

2

1

d=5e=0

d=5e=2

d=0

d=4

0



3

3

4

0

4 0

5

28

Tits dessins ...


TS

2

1

d=5e=0

d=5e=2

d=0

d=4

0



3

3

4

0

4 0

5

29

Tits dessins ...


TS

2

1

d=5e=0

d=5e=2

d=0

d=4

0



3

3

4

0

4 0

52

30

Tits dessins ...


TS

2

1

d=5e=0

d=5e=0

d=0

d=4

0



3

3

4

2

2 0

5

31

Tits dessins ...


TS

2

1

d=1e=0

d=1e=0

d=0

d=4

[7]

[4] [5][3]



2

3

3

5

32

Propriétés et compagnie• Cet algorithme générique maintient des étiquettes de distance

valides et toujours croissantes.– L'initialisation créé des étiquettes valides. Pendant la poussée, un arc de

G(x) peut disparaître (pas d'impact) ou apparaître, et alors, puisqu'il était admissible, la condition reste remplie. Et lors du reétiquetage, on augmente d(i) au min des d(j)+1...

• En tout temps de l’algorithme, il y a un chemin depuis chaque noeud en excès vers s (dans G(x)).– En décomposant les préflots dans G en trois types: les chemins de s vers

t, ceux de s vers un i en excès et ceux formant des cycles. Seuls ceux de s vers un i en excès peuvent expliquer cet excès. Ils sont donc présents dans le graphe résiduel.

• Pour tout iV, d(i)<2n.– Juste avant le dernier reétiquetage de i, il avait un excès, donc G(x)

contenait un chemin de i vers s (long d’au plus n-1). Comme d(s)=n et d(i)d(j)+1 si rij >0, alors d(i)d(s)+(n-1)<2n.


33

Propriétés... second épisode.• Il y a moins de 2n2 reétiquetages– Chaque reétiquetage augmente la distance d'au moins 1... et on

vient de voir qu'on ne pouvait reétiqueter plus de 2n fois.• Il n'y a pas plus que nm poussées saturantes.– Supposons que (i,j) devient saturé. Alors pour pouvoir renvoyer du

flot sur (i,j), il faut d'abord que du flot soit poussé sur (j,i). À ce moment, d'(j)=d'(i)+1d(i)+1=d(j)+2*. Donc, au maximum il y aura n saturations (2n/2)… pour m arcs. *Ça vous rappelle quelque chose?

• Il n'y a pas plus de 2n2m poussées non-saturantes.• L'algorithme s'arrête sur un flot maximum.– Comme plus aucun noeud (s,t) n'a d'excès, le flot est réalisable.– Comme d(s)=n, d(t)=0 et d(i)d(j)+1 si rij>0, alors il n’y a plus de

chemin de s vers t.


34

C’est long ...• On remarque que le nombre de poussées saturantes est

donc limité comparativement au nombre de poussées non-saturantes. Le problème vient principalement du fait que lors des poussées non-saturantes, il n’y a pas les changements de structures aisément restreints qu’occasionnent les poussées saturantes.

• Dans un FIFO de base, il peut y en avoir O(n3).• On peut toutefois se rendre à O(n2logU/loglogU) ou à

O(n2(logU)1/2). (Structures complexes d'arbres et facteur multiplicatif plus important)

• Ici, avec par l'approche par phases, nous allons atteindre O(n2logU).


Par réduction d'échelle des excès(Excess Scaling Algorithm)

Second algorithme

36

Quoi encore?L’algorithme cette fois va agir ainsi:• Pour réduire le nombre de poussées non saturantes à

O(n2logU), on utilise un qui pour chaque phase va descendre d’une puissance de 2 (en débutant à )* et on va garantir qu’à chaque poussée non saturante, au moins /2 unités de flot seront poussées. Pour réussir ceci, on ne va que considérer les sommets ayant au moins cet excès.

• Ensuite, en prenant le sommet le plus près du puits, cela nous assure que le sommet de destination a un «faible» excès.

• L’astuce pour choisir efficacement un sommet ayant un excès de plus de /2 sera de maintenir une série de listes de sommets en fonction de leurs distances, ainsi qu’une variable de niveau.

• Finalement, pour chaque sommet, on conserve une liste fixée des arcs incidents vers l’extérieur et un pointeur vers l’arc courant. On va examiner cette liste séquentiellement pour trouver un arc admissible où pousser du flot. Cela évite de revisiter un arc avant un reétiquetage.


log2 U

37

Pseudotruc, le retour...


procédure flot_max_par_phases (entrée: G=(V,A); sortie: x)début

{initialisation}mêmes initialisations que pour le précédent algorithme

:=2logU

{corps}tant que 1début

pour iVsi e(i)>/2 alors

ajouter i à LISTE(d(i))niveau:=1tant que niveau<2n

si LISTE(niveau)= alorsniveau:=niveau+1

sinondébut

choisir un sommet i dans LISTE(niveau)pousser_ou_reétiqueter(i)

fin:=/2

finfin

38

Pseudotruc, la fin!procédure pousser_ou_reétiqueter (entrée: i, LISTE, G, x; sortie: LISTE, G, x)début

trouvé:=faux(i,j):=courant(i) {L’arc courant du sommet i}tant que trouvé=faux et (i,j)vide

si d(i)=d(j)+1 et rij>0 alorstrouvé:=vrai

sinon(i,j):=l’arc suivant parmi le V+(i) fixé. («vide» si

terminé)si trouvé=vraidébut

pousser =min{e(i),rij,-e(j)} sur (i,j) {ajuster xij, e(i) et e(j)}si e(i)/2 alors

LISTE(d(i)):=LISTE(d(i))\{i}si js,t et e(j)>/2 alorsdébut

LISTE(d(j)):=LISTE(d(j)){j}niveau:=niveau-1

finfinsinon{fin de la liste des arcs de i}début{reétiquetage}

LISTE(d(i)):=LISTE(d(i))\{i}d(i):=min{d(j)+1|(i,j)V+(i) et rij>0}LISTE(d(i)):=LISTE(d(i)){i}courant(i):=premier arc de V+(i) fixé

fin2


39

Qu’est-ce que je gagne?L’algorithme agit un peu comme un glouton,

mais que l’on aurait calmé un peu. En effet :

• On s’assure de pousser au moins /2 (si non saturant)

• Aucun excès n'augmente à plus de – Comme on pousse min{e(i), rij, -e(j)}

Ceci nous permet de conserver le niveau de complexité voulu.


40

Hmmm ...• Le total des poussées non saturantes est

alors au maximum de 8n2.– e(i) et d(i)2n, Donc, prenons

F=e(i)d(i)/2n2. Alors, quand on examine i :• Soit, plus d’admissiblereétiquetageF augmente,

mais la valeur maximale de d(i) étant 2n, F ne peut augmenter de plus de 2n2 fois de cette manière.

• Soit on effectue une poussée et F diminue d’au moins la moitié.

– Au total, F ne pourra donc augmenter de plus de 4n2. Ce qui donne 8n2 augmentations au maximum.


41

Bingo!• On obtient finalement O(n2logU) poussées non

saturantes.– Comme 2U et qu’on le divise par 2 après chaque phase

qui a nécessité au maximum 8n2 poussées non saturantes…• La complexité totale est donc de O(nm+n2logU).– La complexité dépend du nombre d’exécutions de la boucle

«tant que». À chaque itération, soit niveau augmente, soit on «pousse ou reétiquette».• Si on pousse, on a calculé le nombre de poussées non saturantes à

O(n2logU) et il y a O(nm) poussées saturantes.• On ne peut augmenter niveau que O(n) fois pour chaque sommet. Ce

qui donne O(n2), négligeable ici.– L’ensemble des autres opérations est aussi négligeable.


42

Ça achève ...Petites améliorations possibles :• Changer le ratio de d’une phase à l’autre.– Ne change pas la complexité, mais peut être efficace

selon les cas. Ça ajoute un facteur multiplicatif à la complexité, mais les poussées sont plus efficaces.

• Permettre des petites poussées non saturantes.– En pressant le citron d’un sommet, même si l’algorithme

nous demande de le sortir de G(x) jusqu’à ce qu’il n’ait plus d’excès ou qu’on réalise une poussée de /2.

• En essayant, de temps en temps, d’éliminer les sommets déconnectés du puits dans G(x) par une recherche en largeur...


C’est assez!

Documents

R.K.Ahuja & James B.Orlin (1988)