previous up next

L'algorithme

L'initialisation
Pour pouvoir utiliser l'algorithme, il faut avoir un arbre solution initial. Pour trouver un tel arbre, on utilise le même algorithme. On part d'un arbre solution dont les arcs sont : (1,k) de poids P si k est un puits de P marchandises ou si P = 0 et (k,1) de poids P si k est une source de P marchandises. Mais il est bien sûr possible que ces arcs n'appartiennent pas au graphe original. On lui rajoute ces arcs fictifs avec un coût 1 et on donne aux arcs réels un coût 0. On applique l'algorithme à ce nouveau problème.

 
Figure: Arbre de départ de l'initialisation pour le premier exemple
\includegraphics[height=5cm]{exemple1_init.eps}

Le problème est résolvable si et seulement si le coût de l'arbre obtenu est 0. Si l'arbre ne possède aucun arc fictif, cet arbre est un arbre d'initialisation, du problème, sinon on décompose le problème en plusieurs sous-problèmes (voir figure 3.3).

 
Figure: Décomposition en trois sous-problèmes
\includegraphics[height=7cm]{init.eps}

Remarque
L'arbre de départ est un bon arbre. Les arbres d'initialisation obtenus sont donc tous des bons arbres.

Le coût des n\oeuds
Le calcul des c[i] se fait facilement grâce au tableau des successeurs s.

Choix de l'arc entrant
Pour trouver un arc entrant, on teste un après l'autre les arcs ne faisant pas partie de l'arbre. C'est la phase la plus coûteuse en temps.

Choix de l'arc sortant
La détection du cycle est aisée grâce aux tableaux p et d. Il faut ensuite suivre la tactique anti-cyclage vue précédemment pour choisir l'arc sortant.

Mise à jour de l'arbre
Une fois les arcs entrants et sortants déterminés, il ne reste plus qu'à mettre à jour l'arbre. Ceci représente la phase la plus complexe au niveau algorithmique. Voici une itération pour le premier exemple :

 
Figure 3.4: L'arc (2,1) entre, l'arc (2,4) sort
\includegraphics[height=9cm]{exemple1_arbre_entre.eps}


 
Figure: L'arbre mis à jour
\includegraphics[height=5cm]{exemple1_arbre_nouvel.eps}

La représentation de ce nouvel arbre est la suivante :

i 1 2 3 4 5 6 7
p / 1 2 1 1 1 2
poid / 9 6 10 8 9 15
sens / 0 1 1 1 0 0

i 1 2 3 4 5 6 7
d 0 1 2 1 1 1 2

i 1 2 3 4 5 6 7
s 2 3 7 5 1 4 6


Voyons encore un autre exemple un peu plus général pour mieux voir les modifications, particulièrement celles du tableau s. Considérons l'arbre suivant :

\includegraphics[height=11cm]{arbre1.eps}

Le tableau s correspondant est le suivant :

i 1 2 3 4 5 6 7 8 9 10 11 12
s 2 3 4 5 6 7 9 1 10 12 8 11

Supposons que l'arc (3,10) entre. Alors l'arc (5,7) sort. On obtient :

\includegraphics[height=11cm]{arbre2.eps}

Le tableau s correspondant est à présent :

i 1 2 3 4 5 6 7 8 9 10 11 12
s 2 3 10 5 6 8 9 1 11 12 4 7


previous up next

30-03-1999