| CHAPITRE 9 |
| APPLICATIONS À LA RÉSOLUTION DE PROBLÈME EN TURBO PASCAL VERSION DOS 7.0 |
OBJECTIF
? INTÉGRER LES DIFFÉRENTES NOTIONS ET APPROCHES EXPOSÉES DANS LES CHAPITRES PRÉCÉDENTS DANS
UNE DÉMARCHE CONCRÈTE DE RÉSOLUTION DE PROBLÈME EN TURBO PASCAL VERSION DOS 7.0.
216 INTRODUCTION À LA PROGRAMMATION EN PASCAL/DELPHI
Après avoir abordé dans les chapitres précédents les éléments de base de l’algorithmique et du langage PASCAL, il apparaît naturel de chercher à intégrer ces différentes notions et approches dans une démarche concrète de résolution de problème. Dans ce chapitre, nous allons traiter deux problèmes de recherche opérationnelle dont les applications pratiques demeurent nombreuses: il s’agit du problème de la recherche d’un arbre sous-tendant minimum et celui de la localisation de concentrateurs ou d’entrepôts. Ces deux problèmes peuvent être résolus, le premier par les algorithmes de Prim et de Kruskal, le deuxième par les algorithmes ADD et DROP. Afin de faciliter la compréhension de l’exposé, nous allons débuter par un rappel de quelques notions de la théorie des graphes.
9.1 NOTIONS DE LA THÉORIE DES GRAPHES
On appelle graphe un ensemble de nœuds (ou sommets) reliés entre eux par des arcs (ou arêtes). La figure 9.1 en est une illustration.
GRAPHE DE 5 NOEUDS ET DE 7 ARCS.
Si on désigne par N l’ensemble des nœuds et par A l’ensemble des arcs, on peut noter G= ( N,A ) le graphe qui en résulte. Pour un ensemble N de n nœuds, le nombre maximum d’arcs est désigné par mmax = n(n– 1 )/2. Ainsi, dans le cas de la figure 9.1, on a:
N = {1, 2, 3, 4, 5}
n = 5
A = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}
m = 7 mmax = 5(5– 1 )/2 = 10.
En effet, le graphe comprend 7 arcs, sur une possibilité de 10, les 3 arcs non considérés étant (1,4 ), (1,5 ) et (2,3 ). Tout graphe construit à partir d’un sous-ensemble des nœuds de G est appelé une composante de G.
Tout arc qui possède une origine et une destination non interchangeables est dit orienté, la destination étant généralement indiquée par une flèche à l’extrémité correspondante de l’arc. Dans le cas contraire, l’arc est dit non orienté.
On dit d’un graphe qu’il est orienté lorsque tous ses arcs le sont. Dans le cas de la figure
9.2 qui en est un exemple, l’ensemble des arcs orientés est:
A = {(1, 2), (2, 5), (3, 1), (3, 4), (4, 2), (5, 3), (5, 4)}
GRAPHE ORIENTÉ.
Lorsque tous les arcs d’un graphe sont non orientés, le graphe en question est dit non orienté. C’est le cas du graphe de la figure9 .1.
On dit d’un arc qu’il est incident à un nœud si cet arc admet ce nœud comme origine ou destination. Dans le cas de la figure 9.1, l’arc (1,2 ) est à la fois incident au nœud1 et au nœud2 . Ainsi, on appelle degré d’incidence d’un nœud le nombre d’arcs incidents à ce nœud; par exemple, les nœud2 , 3, 4 et 5 de la figure9 .1 sont de degré3 , alors que le nœud1 est de degré2 . On désigne par degré d’un graphe le degré d’incidence du nœud le plus faible de ce graphe; à titre d’exemple, le graphe de la figure9 .1 est de degré2 , le plus faible degré d’incidence d’un nœud étant de degré2 .
On appelle chemin i-j entre deux nœud i et j d’un graphe la suite d’arcs permettant, à partir du nœud i, d’atteindre le nœud j. Par exemple, en considérant le graphe de la figure9 .1, pour aller du nœud1 au nœud5 , on peut utiliser l’une ou l’autre des séquences d’arcs suivantes:
(1, 2)–(2, 5)
(1, 2)–(2, 4)–(4, 5)
(1, 2)–(2, 4)–(4, 3)–(3, 5)
(1, 3)–(3, 5)
(1, 3)–(3, 4)–(4, 5)
(1, 3)–(3, 4)–(4, 2)–(2, 5)
qui sont autant de chemins reliant les deux nœuds1 et 5.
Chaque arc est muni d’une longueur qui n’est autre que la distance euclidienne entre ses nœuds d’origine et de destination. En conséquence, on désigne par longueur d’un chemin la somme des longueurs d’arcs qui composent celui-ci. Un chemin dont l’origine se confond à la destination constitue un cycle. Par rapport au graphe de la figure9 .1, le chemin formé par la suite d’arcs (1, 3)–(3, 4)–(4, 2)–(2, 1), par exemple, est un cycle.
On dit d’un graphe qu’il est connexe lorsque chacune de ses paires de nœuds est reliée par au moins un chemin. On parle alors de connexité simple ou de 1–connexité. Dans le cas où il existe au moins k chemins distincts entre chaque paire de nœuds du graphe (k> 1 ), on dit que le graphe est de degré de connexité k ou qu’il est k–connexe. Par exemple, le graphe de la figure9 .1 est 2–connexe; dans un graphe connexe, aucun nœud n’est de degré d’incidence nul.
On désigne par arbre ou arborescence un graphe connexe sans cycle; le degré de connexité d’un tel graphe est donc égal à 1. Un arbre est dit sous-tendant minimum lorsqu’il relie tous les nœuds au moyen d’arcs dont la somme totale des longueurs est la plus petite possible. La figure9 .3 en est une illustration.
ARBRE SOUS-TENDANT MINIMUM.
9.2 LA CONSTRUCTION D’UN ARBRE SOUS-TENDANT MINIMUM
Considérons un ensemble de n nœuds numérotés de 1 à n et définissons le coût d’un arbre comme la longueur totale des liaisons qui composent cet arbre. La construction d’un arbre sous-tendant minimum (ASM) pour cet ensemble de nœuds consiste à déterminer un tracé qui permet de relier tous ces nœuds en un arbre de coût minimum. Un tel problème, dont la formulation peut être modifiée pour tenir compte de certaines contraintes, est généralement résolu soit par l’algorithme de Prim ou par celui de Kruskal.
Considérons un ensemble I de nœuds déjà inclus dans l’arbre en construction et un ensemble NI de nœuds non encore inclus. L’algorithme de Prim se définit par les étapes suivantes:
| Étape 1: | Initialiser: I = { } NI = {1, ..., n}. |
| Étape 2: | Inclure le nœud1 dans l’arbre, comme premier nœud; et par suite: I = {1} NI = {2, 3, ..., n}. |
| Étape 3: | Si l’arbre est connexe, alors aller à l’étape 5. |
| Étape 4: | Trouver le nœud i dont la distance à un nœud quelconque j de I est minimale, relier ce nœud i au nœud j; faire: I = I + {i} NI = NI – {i}, puis retourner à l’étape 3. |
| Étape 5: | Arrêt. |
Considérons un ensemble de 15 nœuds de coordonnées cartésiennes respectives:
1. (35, 45) 6. (35, 25) 11. (65, 60)
2. (5, 20) 7. (45, 60) 12. (65, 20)
3. (10, 60) 8. (50, 10) 13. (75, 45) 4. (20, 40) 9. (55, 40) 14. (85, 65) 5. (30, 70) 10. (60, 80) 15. (90, 15)
La figure9 .4 montre le résultat de l’application de l’algorithme de Prim sur l’ensemble de nœuds du graphe. Les chiffres entre parenthèses indiquent l’ordre d’insertion des liaisons dans l’ASM.
EXEMPLE DE L’ALGORITHME DE PRIM.
L’algorithme de Prim construit l’arbre sous-tendant minimum en faisant croître une composante connexe à partir d’un nœud donné (ici le nœud1 ). L’ensemble I contient les nœuds de cette composante connexe. À chaque étape de l’algorithme, on doit trouver un arc de longueur minimum joignant I à NI. Au lieu de faire cette recherche parmi toutes les paires (i, j) avec i ? I et j ? NI, on peut maintenir deux tableaux
PlusPresDe et DistanceMin qui auront la propriété invariante suivante:
Pour chaque nœud i ? NI:
– s’il existe au moins un nœud de I adjacent à i, alors DistanceMin[i] est la valeur de l’arc de coût minimum joignant i à un élément de I et PlusPresDe[i] représente un des nœuds de I pour lequel:
ValeurArc(i, PlusPres[i]) = DistanceMin[i]
– s’il n’existe pas d’élément de I adjacent à i, on l’indique en donnant la valeur infini (?) à DistanceMin[i].
Cela impose toutefois une restriction quant aux valeurs des arcs du graphe: elles devront être strictement inférieures à l’infini, c’est-à-dire, en pratique, une valeur limite qui dépend de la machine. Ainsi, à chaque étape, on recherche le nœud i ?NI qui minimise DistMin[i], et on ajoute à l’ASM l’arc joignant i et PlusPresDe[i]. Puis, on met à jour I, NI, PlusPresDe et DistanceMin.
Toutes les fois que le corps de la boucle principale est exécuté, un arc est ajouté à l’ASM. On devra donc ajouter (n– 1 ) arcs, car un arbre qui a n nœuds possède n– 1 arcs.
Le programme de l’exemple9 .2 est une implantation de l’algorithme de Prim. Ce programme est écrit en Turbo Pascal qui accepte des identificateurs de longueur supérieure à celle que permet le PASCAL (standard).
PROGRAM Prim(INPUT, OUTPUT);
(*
* Ce programme fait une mise en oeuvre de l'algorithme de Prim. * Une interface par menu permet a un usager de definir les parametres * et d'appliquer l'algorithme.
*)
(* Definition d'un type graphe value non oriente *)
CONST
Infini = 10.0E20;
MaxNoeud = 20; (* Nombre maximum de noeuds *)
TYPE
TypeValeur = REAL; (* Type de valeur des arcs *)
Noeud = 1..MaxNoeud;
Graphe = RECORD
nbNoeuds : 0..MaxNoeud;
MatAdjacence : ARRAY[Noeud, Noeud] OF BOOLEAN;
MatValeur : ARRAY[Noeud, Noeud] OF TypeValeur;
END;
PROCEDURE InitGraphe(VAR g : Graphe; nbNoeuds : INTEGER);
(* But : Initialise g comme un graphe de nbNoeuds sans arc. *)
VAR i, j : Noeud;
BEGIN
g.nbNoeuds := nbNoeuds; FOR i := 1 TO nbNoeuds DO
FOR j := 1 TO nbNoeuds DO
g.MatAdjacence[i, j] := FALSE;
END; (* InitGraphe *)
PROCEDURE AjouterArc(VAR g : Graphe; n1, n2 : Noeud; val : TypeValeur); (* But : Ajoute entre les noeuds n1 et n2 de g un arc de valeur val. *)
BEGIN
WITH g DO
BEGIN
MatAdjacence[n1, n2] := TRUE;
MatAdjacence[n2, n1] := TRUE;
MatValeur[n1, n2] := val;
MatValeur[n2, n1] := val;
END;
END;
PROCEDURE RetirerArc(VAR g : Graphe; n1, n2 : Noeud);
(* Enleve de g l'arc joignant n1 et n2. *)
BEGIN
g.MatAdjacence[n1, n2] := FALSE;
g.MatAdjacence[n2, n1] := FALSE;
END;
FUNCTION Adjacent(g : Graphe; n1, n2 : Noeud) : BOOLEAN;
(* But : Donne TRUE si un arc joint n1 et n2;
* donne FALSE sinon. *)
BEGIN
Adjacent := g.MatAdjacence[n1, n2]; END;
FUNCTION ValeurArc(VAR g : Graphe; n1, n2 : Noeud) : TypeValeur; (* But : Donne la valeur de l'arc joignant n1 et n2.
* Suppose : Adjacent(g, n1, n2) = TRUE. *)
BEGIN
ValeurArc := g.MatValeur[n1, n2];
END;
FUNCTION NombreDeNoeuds(VAR g : Graphe) : INTEGER;
(* But : Donne le nombre de noeuds de g. *)
BEGIN
NombreDeNoeuds := g.NbNoeuds;
END;
FUNCTION SommeValeurArc(VAR g : Graphe) : REAL;
(* But : Donne la somme des valeurs des arcs de g. *)
VAR
i, j : INTEGER; Total : REAL;
BEGIN
Total := 0.0;
FOR i := 1 TO g.NbNoeuds DO
FOR j := i + 1 TO g.NbNoeuds DO
IF Adjacent(g, i, j) THEN
Total := Total + ValeurArc(g, i, j);
SommeValeurArc := Total;
END;
(*————————————— Algorithme de Prim ———————————*)
PROCEDURE ProcPrim(VAR g : Graphe; VAR ASM : Graphe);
(* But : Donne dans ASM, un arbre recouvrant de cout minimum de g.
* Suppose : g est connexe. *)
VAR
PlusPresDe : ARRAY[1..MaxNoeud] OF Noeud;
DistanceMin : ARRAY[1..MaxNoeud] OF TypeValeur; NonInclus : SET OF Noeud; i, k, m : Noeud; min : TypeValeur;
(*
* Implicitement Inclus = [1..NombreDeNoeuds(g)] – NonInclus, * represente les noeuds de ASM accessibles a partir du noeud 1.
* Les vecteurs DistanceMin et PlusPresDe possedent la propriete que
* pour chaque noeud s dans NonInclus, DistanceMin[s] est la valeur
* de l'arc de valeur minimum joignant ce noeud a un noeud quelconque de Inclus; * PlusPresDe[s] represente ce noeud, s'il n'y a aucun noeud de Inclus adjacent a s * alors DistanceMin[s] = Infini. *)
BEGIN (* ProcPrim *)
InitGraphe(ASM, NombreDeNoeuds(g));
NonInclus := [2..NombreDeNoeuds(g)]; (* Implicitement Inclus = [1] *)
(* Initialisation de DistanceMin et PlusPresDe par rapport a [1] *)
FOR i := 2 TO NombreDeNoeuds(g) DO
IF Adjacent(g, i, 1) THEN
BEGIN
DistanceMin[i] := ValeurArc(g, 1, i);
PlusPresDe[i] := 1;
END
ELSE
DistanceMin[i] := Infini;
FOR m := 2 TO NombreDeNoeuds(g) DO (* Repeter (NombreDeNoeuds(g) – 1) fois *)
BEGIN
(* Recherche de l'arc (k, PlusPresDe[k]) de valeur minimum joignant
* un noeud k de NonInclus a un noeud de Inclus. *) min := Infini;
FOR i := 2 TO NombreDeNoeuds(g) DO
IF (i IN NonInclus) AND (DistanceMin[i] < min) THEN
BEGIN
min := DistanceMin[i]; k := i;
END;
AjouterArc(ASM, k, PlusPresDe[k], min);
NonInclus := NonInclus – [k];
(* Mise a jour de DistanceMin et PlusPresDe *)
FOR i := 2 TO NombreDeNoeuds(g) DO
IF (i IN NonInclus) AND Adjacent(g, k, i) THEN
IF ValeurArc(g, k, i) < DistanceMin[i] THEN
BEGIN
DistanceMin[i] := ValeurArc(g, k, i);
PlusPresDe[i] := k;
END;
END; (* NonInclus = [ ] c'est-a-dire Inclus = [1..NombreDeNoeuds(g)] *)
END; (* ProcPrim *)
(*———————— Procedures utilitaires pour l'interface ———————*)
PROCEDURE FaireUnePause;
(* But : Fait une pause jusqu'a ce que l'usager presse sur retour. *)
BEGIN
WRITE(' ');
WRITE( ' appuyez sur retour');
READLN;
END; (* FaireUnePause *)
PROCEDURE SauterLigne(n : INTEGER);
(* But : Saute n ligne a l'ecran. *)
VAR
i : INTEGER; BEGIN
FOR i := 1 TO n DO
WRITELN; END; (* SauterLigne *)
PROCEDURE ViderEcran;
(* But : Fait defiler l'ecran jusqu'a ce qu'il n'y ait plus rien d'affiche. *)
BEGIN
SauterLigne(25);
END; (* ViderEcran *)
(*———————————— Test de Prim ——————————*)
(* Teste l'algorithme de Prim sur un graphe complet genere a partir
* des coordonnees de points. *)
CONST
MaxCoordonnees = MaxNoeud;
TYPE
Coordonnee = RECORD
Abscisse : REAL;
Ordonnee : REAL;
END;
VectCoord = ARRAY[1..MaxCoordonnees] OF Coordonnee;
TypeSpecCoord = RECORD
NbCoordonnees : INTEGER;
Coordonnees : VectCoord; END;
FUNCTION Distance(x1, x2 : Coordonnee) : REAL;
(* But : Donne la distance euclidienne entre les coordonnees x1 et x2. *)
BEGIN
Distance := SQRT(SQR(x1.abscisse – x2.abscisse) + SQR(x1.ordonnee – x2.ordonnee));
END; (* Distance *)
FUNCTION CoordPresente(VAR v : VectCoord ; n1, n2 : INTEGER; abs, ord : REAL) : BOOLEAN;
(* But : Teste si pour une coordonnee de v[n] (n1 <= n <= n2)
* v[n].Abscisse = abs et v[n].Ordonnee = ord. *)
VAR
k : INTEGER;
CoordPresente := FALSE;
FOR k := n1 TO n2 DO
IF (v[k].Abscisse = abs) AND (v[k].Ordonnee = ord) THEN
CoordPresente := TRUE;
END; (* CoordPresente *)
PROCEDURE SaisirCoordonnees(VAR Spec : TypeSpecCoord);
(* But : – Saisit le nombre de coordonnees;
* – saisit les coordonnees dans Spec. *)
PROCEDURE SaisiCoordonnee(i : INTEGER; VAR abscisse, ordonnee : REAL;
(* But : Saisit et donne la i-ieme coordonnee. *)
BEGIN
SauterLigne(2);
WRITELN('Coordonnee ', i : 3);
WRITE( ' abscisse : '); READLN(abscisse);
WRITE( ' ordonnee : '); READLN(ordonnee); END;
PROCEDURE SaisiToutesCoordonnees(VAR Spec : TypeSpecCoord; n : INTEGER);
(* But : Saisir dans Spec des coordonnees 1.. n. *)
VAR
i : INTEGER;
abscisse, ordonnee : REAL;
BEGIN
SauterLigne(3);
WRITELN('Entrez les coordonnees des noeuds '); SauterLigne(2); i := 1;
WHILE i <= n DO
BEGIN
SaisiCoordonnee(i, abscisse, ordonnee);
IF NOT CoordPresente(Spec.Coordonnees, 1, i – 1, abscisse, ordonnee) THEN
BEGIN
Spec.Coordonnees[i].Abscisse := abscisse; Spec.Coordonnees[i].Ordonnee := ordonnee; i := i + 1
END
ELSE
WRITELN('Coordonnee deja definie, recommencez s.v.p.');
END;
END;
ViderEcran;
WRITELN(' Specification des coordonnees');
WRITELN;
WRITE('Entrez le nombre de noeuds (max. ', MaxNoeud : 2,') : ');
READLN(Spec.NbCoordonnees);
SaisiToutesCoordonnees(Spec, Spec.nbCoordonnees);
END; (* SaisirCoordonnees *)
PROCEDURE AfficherCoordonnees(Spec : TypeSpecCoord);
(* But : Affiche les coordonnees de Spec. *)
VAR
i : INTEGER; BEGIN
ViderEcran;
WITH Spec DO
BEGIN
WRITELN;
WRITELN(' Coordonnees des noeuds ');
SauterLigne(2);
FOR i := 1 TO NbCoordonnees DO
BEGIN
IF ((i MOD 16) = 0) THEN
FaireUnePause;
WRITELN(' ', i : 2,' ', '(', Coordonnees[i].abscisse : 12 : 2,
', ', Coordonnees[i].ordonnee : 12 : 2,')');
END;
END; (* WITH *)
FaireUnePause;
END; (* AfficherCoordonnees *)
PROCEDURE AfficherGraphe(g : Graphe);
(* But : –Affiche les arcs de g et leurs valeurs;
* – affiche le total des valeurs des arcs. *)
VAR
i, j : INTEGER; k : INTEGER; (* Compteur pour pause *) k := 0;
FOR i := 1 TO NombreDeNoeuds(g) DO
FOR j := i + 1 TO NombreDeNoeuds(g) DO
IF Adjacent(g, i, j) THEN
BEGIN
k := k + 1;
IF ((k MOD 16) = 0) THEN
FaireUnePause;
WRITELN('arc(', i : 2, ', ', j : 2, ') valeur : ', ValeurArc(g, i, j) : 12 : 2);
END;
SauterLigne(1);
WRITELN(' cout total : ', SommeValeurArc(g) : 12 : 2);
END; (* AfficherGraphe *)
PROCEDURE AppliquerPrim(VAR Spec : TypeSpecCoord);
(* But : – Definit un graphe g complet ou les valeurs des arcs sont egales
* aux distances entre les coordonnees correspondantes;
* – applique l'algorithme de Prim sur g -> ASM;
* – affiche les arcs de ASM et la somme de leurs valeurs. *)
VAR
i, j : INTEGER; g, ASM : Graphe;
BEGIN
InitGraphe(g, Spec.NbCoordonnees);
FOR i := 1 TO Spec.NbCoordonnees DO
FOR j := i + 1 TO Spec.NbCoordonnees DO
AjouterArc(g, i, j, Distance(Spec.Coordonnees[i], Spec.Coordonnees[j]));
ProcPrim(g, ASM);
ViderEcran;
WRITELN('Arcs de l''arbre recouvrant de cout minimum suivant l''algorithme de Prim');
SauterLigne(2);
AfficherGraphe(ASM);
SauterLigne(2);
FaireUnePause;
END; (* AppliquerPrim *)
PROCEDURE TesterPrim;
(* But : Menu permettant a l'usager de :
* 1. definir les coordonnees des noeuds d'un graphe
* 2. afficher les coordonnees du graphe courant
* 3. trouver l'ASM a l'aide de PRIM et de l'afficher *)
VAR
Choix : CHAR; (* Choix de l'usager *)
Spec : TypeSpecCoord; (* Contient les coordonnees. *)
CoordSontDefinies : BOOLEAN; (* A-t-on defini des coordonnees? *)
PROCEDURE SignifierCoordNonDefinies;
(* Affiche un message indiquant qu'on doit definir des coordonnees. *)
BEGIN
ViderEcran;
WRITELN('Vous devez d''abord definir les coordonnees. '); FaireUnePause;
END;
BEGIN
CoordSontDefinies := FALSE;
REPEAT
ViderEcran;
| WRITELN(' SauterLigne(2); | Test de Prim'); |
| WRITELN(' WRITELN; | 1. Definir les coordonnees'); |
| WRITELN(' WRITELN; | 2. Afficher les coordonnees'); |
| WRITELN(' WRITELN; | 3. Resultat de Prim'); |
| WRITELN(' | 0. Terminer'); |
SauterLigne(5);
WRITE('Entrez votre choix : ');
READLN(Choix);
CASE Choix OF
'1' : BEGIN
SaisirCoordonnees(Spec);
CoordSontDefinies := TRUE;
END;
'2' : IF CoordSontDefinies THEN AfficherCoordonnees(Spec)
ELSE
SignifierCoordNonDefinies;
'3' : IF CoordSontDefinies THEN AppliquerPrim(Spec)
ELSE
SignifierCoordNonDefinies;
'0' : ;
END;
UNTIL Choix = '0';
END; (* TesterPrim *)
(*———————— Programme principal ———————— *)
BEGIN
TesterPrim;
ViderEcran; END.
Considérons un tableau TabTri destiné à contenir les longueurs des liaisons triées en ordre croissant. L’algorithme de Kruskal comprend les étapes suivantes:
| Étape 1: | Calculer les distances entre toutes les paires de noeuds. |
| Étape 2: | Trier ces distances ou liaisons potentielles dans l’ordre croissant de leur longueur et les placer dans TabTri. |
| Étape 3: | Inclure dans l’arbre la liaison ( i, j), la plus courte de TabTri. |
| Étape 4: | Enlever la liaison ( i, j) de TabTri. |
| Étape 5: | Si l’arbre est connexe, alors aller à l’étape 9. |
| Étape 6: | Retenir pour insertion la liaison ( i, j), la plus courte de TabTri. |
| Étape 7: | Si l’insertion de ( i, j) conduit à la formation d’un cycle, alors retourner à l’étape4 . |
| Étape 8: | Insérer la liaison ( i, j) dans l’arbre et retourner à l’étape 4. |
| Étape 9: | Arrêt. |
La figure9 .5 montre le résultat de l’application de l’algorithme de Kruskal sur l’ensemble de nœuds. Les chiffres entre parenthèses indiquent l’ordre d’insertion des liaisons dans l’ASM dont les nœuds ont été définis à l’exemple9 .1.
EXEMPLE D’APPLICATION DE L’ALGORITHME DE KRUSKAL.
L’algorithme de Kruskal ajoute des arcs à l’ASM suivant l’ordre croissant de leur longueur, l’ajout d’un arc ne devant pas induire de cycle. On peut montrer que, dans un graphe sans cycle, l’ajout d’un arc ne conduit pas à la formation de cycle si et seulement si cet arc joint deux composantes connexes différentes. Cette propriété nous fournit un moyen simple de tester si un arc peut être ajouté. Il faut cependant pouvoir déterminer si deux nœuds ou sommets appartiennent à des composantes connexes différentes. Ceci se réalise simplement en utilisant un vecteur Composantes[1..n] ayant la propriété invariante suivante:
Deux nœud i et j de l’ASM font partie de la même composante connexe si et seulement si:
Composantes[i] = Composantes[j].
Au départ, l’ASM ne possède aucun arc; il contient donc n composantes connexes dégénérées, d’un seul nœud chacune. Nous initialisons alors Composantes de telle sorte que Composantes[i] = i, avec i ? {1, 2, ..., n}. Puis, lorsqu’un arc est ajouté, il joint deux nœuds ou sommets s1 et s2 appartenant à des composantes connexes différentes (disons C1 et C2). Il faudra alors joindre les composantes C1 et C2.
Toutes les fois qu’un arc est ajouté, le nombre de composantes connexes diminue de1 . L’exécution de la boucle principale se terminera donc lorsqu’il n’y aura plus qu’une seule composante connexe (un arbre étant un graphe connexe sans cycle).
Le programme9 .3 constitue une implantation de l’algorithme de Kruskal. Ce programme est écrit en Turbo Pascal qui accepte des identificateurs de longueur supérieure à celle que permet le PASCAL standard.
PROGRAM Kruskal(INPUT, OUTPUT);
(* Ce programme fait une mise en oeuvre des algorithmes Kruskal.
* Une interface par menu permet a un usager de definir les parametres
* et d'appliquer l'algorithme. *)
(*————— Definition d'un type graphe value non oriente ————*)
CONST
Infini = 10.0E20;
MaxNoeud = 20; (* Nombre maximum de noeuds *)
TYPE
TypeValeur = REAL; (* Type de valeur des arcs *)
Noeud = 1..MaxNoeud;
Graphe = RECORD nbNoeuds : 0..MaxNoeud;
MatAdjacence : ARRAY[Noeud, Noeud] OF BOOLEAN;
MatValeur : ARRAY[Noeud, Noeud] OF TypeValeur; END;
PROCEDURE InitGraphe(VAR g : Graphe; nbNoeuds : INTEGER);
(* But : Initialise g comme un graphe de nbNoeuds sans arc. *)
VAR i, j : Noeud;
BEGIN
g.nbNoeuds := nbNoeuds; FOR i := 1 TO nbNoeuds DO
FOR j := 1 TO nbNoeuds DO
g.MatAdjacence[i, j] := FALSE;
END; (* InitGraphe *)
PROCEDURE AjouterArc(VAR g : Graphe; n1, n2 : Noeud; val : TypeValeur); (* But : Ajoute entre les noeuds n1 et n2 de g un arc de valeur val. *)
BEGIN
WITH g DO
BEGIN
MatAdjacence[n1, n2] := TRUE;
MatAdjacence[n2, n1] := TRUE;
MatValeur[n1, n2] := val;
MatValeur[n2, n1] := val;
END;
END;
PROCEDURE RetirerArc(VAR g : Graphe; n1, n2 : Noeud);
(* Enleve de g l'arc joignant n1 et n2. *)
BEGIN
g.MatAdjacence[n1, n2] := FALSE;
g.MatAdjacence[n2, n1] := FALSE;
END;
FUNCTION Adjacent(g : Graphe; n1, n2 : Noeud) : BOOLEAN;
(* But : Donne TRUE si un arc joint n1 et n2;
* donne FALSE sinon. *)
BEGIN
Adjacent := g.MatAdjacence[n1, n2]; END;
FUNCTION ValeurArc(VAR g : Graphe; n1, n2 : Noeud) : TypeValeur; (* But : Donne la valeur de l'arc joignant n1 et n2.
* Suppose : Adjacent(g, n1, n2) = TRUE *)
BEGIN
ValeurArc := g.MatValeur[n1, n2]; END;
FUNCTION NombreDeNoeuds(VAR g : Graphe) : INTEGER;
(* But : Donne le nombre de noeuds de g . *)
BEGIN
NombreDeNoeuds := g.NbNoeuds; END;
FUNCTION SommeValeurArc(VAR g : Graphe) : REAL;
(* But : Donne la somme des valeurs des arcs de g. *)
VAR
i, j : INTEGER; Total : REAL;
BEGIN
Total := 0.0;
FOR i := 1 TO g.NbNoeuds DO
FOR j := i + 1 TO g.NbNoeuds DO
IF Adjacent(g, i, j) THEN
Total := Total + ValeurArc(g, i, j);
SommeValeurArc := Total;
END;
(*———————————— Algorithme de Kruskal ——————————*)
PROCEDURE ProcKruskal(VAR g : Graphe; VAR ASM : Graphe);
(* But : Donne dans ASM, un arbre recouvrant de cout minimum de g.
* Suppose : g est connexe. *)
TYPE
Arc = RECORD
noeud1, noeud2 : Noeud; valeur : TypeValeur; END;
TypeVecteurArc = ARRAY[0..(MaxNoeud * MaxNoeud)] OF Arc;
VAR
NbComposantes : INTEGER; (* Nombre de composantes connexes *)
Composantes : ARRAY[Noeud] OF Noeud;
VectArcs : TypeVecteurArc; NbArcsTot : INTEGER; i, j, k : INTEGER; compTemp : INTEGER;
PROCEDURE TrierArcs(VAR v : TypeVecteurArc; n : INTEGER);
(* Tri par insertion *)
VAR
i, j : INTEGER; temp : Arc; ValTemp : TypeValeur; BEGIN
v[0].valeur := – Infini;
FOR i := 2 TO n DO
BEGIN
j := i; temp := v[i];
ValTemp := v[i].valeur;
WHILE ValTemp < v[j – 1].valeur DO
BEGIN
v[j] := v[j – 1]; j := j – 1;
END;
v[j] := temp;
END; END; (* TrieInsertion *)
(* Le vecteur Composantes sert a contenir les noeuds des composantes connexes. * i et j appartiennent a la meme composante connexe
* si Composantes[i] = Composantes[j]. *)
BEGIN (* ProcKruskal *)
InitGraphe(ASM, NombreDeNoeuds(g));
(* Initialisation de VectArcs : vecteur trie des arcs de g. *)
NbArcsTot := 0;
FOR i := 1 TO NombreDeNoeuds(g) DO
FOR j := i + 1 TO NombreDeNoeuds(g) DO
IF Adjacent(g, i, j) THEN
BEGIN
NbArcsTot := NbArcsTot + 1;
VectArcs[NbArcsTot].noeud1 := i;
VectArcs[NbArcsTot].noeud2 := j;
VectArcs[NbArcsTot].valeur := ValeurArc(g, i, j);
END; TrierArcs(VectArcs, NbArcsTot);
(* Initialisation de Composantes a NombreDeNoeuds(g) composantes connexes
* d'un seul noeud chacune. *)
FOR i := 1 TO NombreDeNoeuds(g) DO Composantes[i] := i; NbComposantes := NombreDeNoeuds(g);
k := 0; (* Indice de l'arc courant *)
WHILE NbComposantes <> 1 DO
BEGIN
k := k + 1;
(* Inclure VectArcs[k] si l'arc joint deux composantes connexes différentes
* c'est-a-dire n'introduit pas de cycle dans ASM. *)
WITH VectArcs[k] DO
IF Composantes[noeud1] <> Composantes[noeud2] THEN
BEGIN
AjouterArc(ASM, noeud1, noeud2, valeur);
(* Joint composante de noeud2 a la composante de noeud1. *)
compTemp := Composantes[noeud2]; FOR i := 1 TO NombreDeNoeuds(g) DO
IF Composantes[i] = compTemp THEN
Composantes[i] := Composantes[noeud1];
NbComposantes := NbComposantes – 1; END;
END; END; (* ProcKruskal *)
(*———————— Procedures utilitaires pour l'interface ———————*)
PROCEDURE FaireUnePause;
(* But : Fait une pause jusqu'a ce que l'usager presse sur retour. *)
BEGIN
WRITE(' ');
WRITE( ' appuyez sur retour');
READLN; END; (* FaireUnePause *)
PROCEDURE SauterLigne(n : INTEGER);
(* But : Saute n ligne a l'ecran. *)
VAR
i : INTEGER; BEGIN
FOR i := 1 TO n DO
WRITELN; END; (* SauterLigne *)
PROCEDURE ViderEcran;
(* But : Fait defiler l'ecran jusqu'a ce qu'il n'y ait plus rien d'affiche. *)
BEGIN
SauterLigne(25);
END; (* ViderEcran *)
(*———————————— Test de Kruskal ——————————*)
(* Teste l'algorithme de Kruskal sur un graphe complet genere a partir
* des coordonnees de points. *)
CONST
MaxCoordonnees = MaxNoeud;
TYPE
Coordonnee = RECORD
Abscisse : REAL;
Ordonnee : REAL;
END;
VectCoord = ARRAY[1..MaxCoordonnees] OF Coordonnee;
TypeSpecCoord = RECORD
NbCoordonnees : INTEGER;
Coordonnees : VectCoord; END;
FUNCTION Distance(x1, x2 : Coordonnee) : REAL;
(* But : Donne la distance euclidienne entre les coordonnées x1 et x2. *)
BEGIN
Distance := SQRT(SQR(x1.abscisse – x2.abscisse) + SQR(x1.ordonnee – x2.ordonnee));
END; (* Distance *)
FUNCTION CoordPresente(VAR v : VectCoord; n1, n2 : INTEGER; abs, ord : REAL) : BOOLEAN;
(* But: Teste si une pour une coordonnee de v[n] (n1 <= n <= n2) * v[n].Abscisse = abs et v[n].Ordonnee = ord *)
VAR
k : INTEGER;
BEGIN
CoordPresente := FALSE;
FOR k := n1 TO n2 DO
IF (v[k].Abscisse = abs) AND (v[k].Ordonnee = ord) THEN
CoordPresente := TRUE;
END; (* CoordPresente *)
PROCEDURE SaisirCoordonnees(VAR Spec : TypeSpecCoord);
(* But : – Saisit le nombre de coordonnees;
* – saisit les coordonnees dans Spec. *)
PROCEDURE SaisirCoordonnee(i : INTEGER; VAR abscisse, ordonnee : REAL;
(* But : Saisit et donne la i-ieme coordonnee. *)
BEGIN
SauterLigne(2);
WRITELN('Coordonnee ', i : 3);
WRITE( ' abscisse : '); READLN(abscisse);
WRITE( ' ordonnee : '); READLN(ordonnee); END;
PROCEDURE SaisirToutesCoordonnees(VAR Spec : TypeSpecCoord; n : INTEGER);
(* But : Saisir dans Spec des coordonnees 1..n. *)
VAR
i : INTEGER;
abscisse, ordonnee : REAL;
BEGIN
SauterLigne(3);
WRITELN('Entrez les coordonnees des noeuds '); SauterLigne(2);
i := 1;
WHILE i <= n DO
BEGIN
SaisirCoordonnee(i, abscisse, ordonnee);
IF NOT CoordPresente(Spec.Coordonnees, 1, i – 1, abscisse, ordonnee) THEN
BEGIN
Spec.Coordonnees[i].Abscisse := abscisse; Spec.Coordonnees[i].Ordonnee := ordonnee; i := i + 1
END
ELSE
WRITELN('Coordonnee deja definie, recommencez s.v.p.');
END;
END;
BEGIN
ViderEcran;
WRITELN(' Specification des coordonnees');
WRITELN;
WRITE('Entrez le nombre de noeuds (max. ', MaxNoeud : 2,') : ');
READLN(Spec.NbCoordonnees);
SaisirToutesCoordonnees(Spec, Spec.nbCoordonnees);
END; (* SaisirCoordonnees *)
PROCEDURE AfficherCoordonnees(Spec : TypeSpecCoord);
(* But : Affiche les coordonnees de Spec. *)
VAR
i : INTEGER;
BEGIN
ViderEcran;
WITH Spec DO
BEGIN
WRITELN;
WRITELN(' Coordonnees des noeuds ');
SauterLigne(2);
FOR i := 1 TO NbCoordonnees DO
BEGIN
IF ((i MOD 16) = 0) THEN
FaireUnePause;
WRITELN(' ', i : 2,' ', '(', Coordonnees[i].abscisse : 12 : 2,
', ', Coordonnees[i].ordonnee : 12 : 2, ')');
END;
END; (* WITH *)
FaireUnePause;
END; (* AfficherCoordonnees *)
PROCEDURE AfficherGraphe(g : Graphe);
(* But : – Affiche les arcs de g et leurs valeurs;
* – affiche le total des valeurs des arcs. *)
VAR
i, j : INTEGER;
k : INTEGER; (* Compteur pour pause *)
BEGIN
k := 0;
FOR i := 1 TO NombreDeNoeuds(g) DO
FOR j := i + 1 TO NombreDeNoeuds(g) DO
IF Adjacent(g, i, j) THEN
BEGIN
k := k + 1;
IF ((k MOD 16) = 0) THEN
FaireUnePause;
WRITELN('arc (', i : 2, ',' , j : 2,') valeur : ', ValeurArc(g, i, j) : 12 : 2);
END;
SauterLigne(1);
WRITELN(' cout total : ', SommeValeurArc(g) : 12 : 2);
END; (* AfficherGraphe *)
PROCEDURE AppliquerKruskal (VAR Spec : TypeSpecCoord);
(* But : – Definit un graphe g complet ou les valeurs d'arcs sont egales
* aux distances entre les coordonnees correspondantes;
* – applique l'algorithme de Kruskal sur g -> ASM;
* – affiche les arcs de ASM et la somme de leurs valeurs. *)
VAR
i, j : INTEGER; g, ASM : Graphe;
BEGIN
InitGraphe(g, Spec.NbCoordonnees);
FOR i := 1 TO Spec.NbCoordonnees DO
FOR j := i + 1 TO Spec.NbCoordonnees DO
AjouterArc(g, i, j, Distance(Spec.Coordonnees[i], Spec.Coordonnees[j]));
ProcKruskal(g, ASM);
ViderEcran;
WRITELN('Arcs de l''arbre recouvrant de cout minimum suivant l''algorithme de Kruskal');
SauterLigne(2);
AfficherGraphe(ASM);
SauterLigne(2);
FaireUnePause;
END; (* AppliquerKruskal *)
PROCEDURE TesterKruskal;
(* But : Menu permettant a l'usager de :
* 1. definir les coordonnees des noeuds d'un graphe,
* 2. afficher les coordonnees du graphe courant,
* 3. trouver l'ASM a l'aide de Kruskal et de l'afficher. *)
VAR
Choix : CHAR; (* Choix de l'usager *)
Spec : TypeSpecCoord; (* Contient les coordonnees. *)
CoordSontDefinies : BOOLEAN; (* A-t-on defini des coordonnees? *)
PROCEDURE SignifierCoordNonDefinies;
(* Affiche un message indiquant qu'on doit definir des coordonnees. *)
BEGIN
ViderEcran;
WRITELN('Vous devez d''abord definir les coordonnees. '); FaireUnePause; END;
BEGIN
CoordSontDefinies := FALSE;
REPEAT
ViderEcran;
WRITELN(' Test de Kruskal');
SauterLigne(2);
WRITELN(' 1. Definir les coordonnees');
WRITELN;
WRITELN(' 2. Afficher les coordonnees');
WRITELN;
WRITELN(' 3. Resultat de Kruskal');
WRITELN;
WRITELN(' 0. Terminer');
SauterLigne(5);
WRITE('Entrez votre choix : ');
READLN(Choix);
CASE Choix OF
'1' : BEGIN
SaisirCoordonnees(Spec);
CoordSontDefinies := TRUE;
END;
'2' : IF CoordSontDefinies THEN
AfficherCoordonnees(Spec)
ELSE
SignifierCoordNonDefinies;
'3': IF CoordSontDefinies THEN
AppliquerKruskal(Spec)
ELSE
SignifierCoordNonDefinies;
'0' : ;
END
UNTIL Choix = '0';
END; (* TesterKruskal *)
(* ———————— Programme principal ———————— *)
BEGIN
TesterKruskal;
ViderEcran; END.
9.3 LA LOCALISATION DE CONCENTRATEURS OU D’ENTREPÔTS
En considérant que chaque groupe de terminaux (ou de points de vente) doit être desservi par un concentrateur (ou un entrepôt), terminaux et concentrateur constituant une partition, le problème consiste à déterminer le nombre et les emplacements réels de concentrateurs (ou d’entrepôts) devant desservir un certain nombre de terminaux (ou de points de vente), et ce avec une contrainte de coût.
On suppose que chaque terminal est affecté à un et à un seul concentrateur et qu’il n’y a pas de limite quant au nombre de terminaux pouvant être affectés à chaque concentrateur. Si aucun terminal n’est affecté à un emplacement potentiel de concentrateur, cet emplacement ne contiendra aucun concentrateur.
Désignons par Dij le coût d’affectation d’un terminal i à un concentrateur j, avec i ?T = {1, 2, ..., n} et j ?C = { 1, 2, ..., m}. Le coût total d’affectation est donné par la relation suivante:
n m m
D = ? ? tijDij+? ujCj (9.1)
i =1 j =1 j =1
où tijvaut 1 si le terminal i est relié au concentrateur j, et 0 dans le cas contraire. Cj désigne le coût du concentrateur j, n le nombre de terminaux et m le nombre d’emplacements potentiels de terminaux. Quant à uj, il vaut 1 si un terminal au moins est affecté à l’emplacement j, et 0 dans le cas contraire. Il s’agit alors de déterminer les emplacements réels des concentrateurs, le nombre réel de ceux-ci et l’affectation des terminaux aux concentrateurs, de manière à minimiser le coût total d’affectation, tel qu’il est exprimé par la relation (9.1).
Ce problème, classé décidable mais difficile, peut être résolu par l’un ou l’autre des algorithmes ADD et DROP, considérés comme des méthodes heuristiques de résolution en ce sens qu’ils permettent de trouver, non pas des solutions optimales, mais plutôt des solutions proches de l’optimum. Les deux prochaines sections en illustrent le fonctionnement, avec les données de l’exemple 9.4.
Considérons 8 terminaux et 5 positions possibles de concentrateur. Le coût d’affectation d’un terminal à un concentrateur est constant et égal à 3 unités. Les concentrateurs sont numérotés de 1 à 5. Il n’y a aucune contrainte sur le nombre de terminaux gérés par un concentrateur. Le tableau 8.1 présente, sous forme matricielle, les coûts Dijd’affectation du terminal i au concentrateur j, avec i= 1 ,2 ,. ..,8 et j= 1 ,2 ,. ..,5 .
Avec les données de l’exemple 8.4, l’algorithme comprendrait les étapes suivantes:
Étape 1: On relie tous les terminaux au concentrateur1 , puis on calcule le coût de cette configuration considérée comme une partition de base (tableau 9.1).
COÛTS D’AFFECTATION DES TERMINAUX AUX CONCENTRATEURS
CONCENTRATEUR
1 2 3 4 5
| 1 | 8 | 3 | 7 | 4 |
| 6 | 2 | 6 | 3 | 5 |
| 2 | 1 | 5 | 5 | 3 |
| 5 | 5 | 2 | 6 | 7 |
| 8 | 4 | 1 | 4 | 6 |
| 7 | 3 | 4 | 2 | 8 |
| 3 | 6 | 7 | 1 | 2 |
| 4 | 7 | 8 | 8 | 1 |
1
2
3
4
5
6
7
8
Coût = 39
Étape 2: On introduit dans la partition de base le concentrateur2 , puis on relie chaque terminal soit à l’ordinateur central soit au nouveau concentrateur introduit, selon la liaison la plus économique. On obtient ainsi une nouvelle partition, représentée au tableau9 .2, dont le coût total d’affectation D est de2 9.
SCHÉMA D’AFFECTATION (ÉTAPE 2)
CONCENTRATEUR
1 2 3 4 5
| 1 | 8 | 3 | 7 | 4 |
| 6 | 2 | 6 | 3 | 5 |
| 2 | 1 | 5 | 5 | 3 |
| 5 | 5 | 2 | 6 | 7 |
| 8 | 4 | 1 | 4 | 6 |
| 7 | 3 | 4 | 2 | 8 |
| 3 | 6 | 7 | 1 | 2 |
| 4 | 7 | 8 | 8 | 1 |
1
2
3
4
5
6
7
8
Coût = 29
Étape 3: On répète l’étape 2 pour les paires de concentrateurs 1-3, 1-4 et 1-5; c’est ce que représentent les tableaux9 .3, 9.4 et 9.5.
SCHÉMA D’AFFECTATION 1-3 SCHÉMA D’AFFECTATION 1-4
1 2 3 4 5 1 2 3 4 5
| 1 | 8 | 3 | 7 | 4 | 1 2 3 4 5 6 7 8 | 1 | 8 | 3 | 7 | 4 |
| 6 | 2 | 6 | 3 | 5 | 6 | 2 | 6 | 3 | 5 | |
| 2 | 1 | 5 | 5 | 3 | 2 | 1 | 5 | 5 | 3 | |
| 5 | 5 | 2 | 6 | 7 | 5 | 5 | 2 | 6 | 7 | |
| 8 | 4 | 1 | 4 | 6 | 8 | 4 | 1 | 4 | 6 | |
| 7 | 3 | 4 | 2 | 8 | 7 | 3 | 4 | 2 | 8 | |
| 3 | 6 | 7 | 1 | 2 | 3 | 6 | 7 | 1 | 2 | |
| 4 | 7 | 8 | 8 | 1 | 4 | 7 | 8 | 8 | 1 |
1
2
3
4
5
6
7
8
Coût = 29 Coût = 28
SCHÉMA D’AFFECTATION 1-5
CONCENTRATEUR
1 2 3 4 5
| 1 | 8 | 3 | 7 | 4 |
| 6 | 2 | 6 | 3 | 5 |
| 2 | 1 | 5 | 5 | 3 |
| 5 | 5 | 2 | 6 | 7 |
| 8 | 4 | 1 | 4 | 6 |
| 7 | 3 | 4 | 2 | 8 |
| 3 | 6 | 7 | 1 | 2 |
| 4 | 7 | 8 | 8 | 1 |
1
2
3
4
5
6
7
8
Coût = 35
| Étape 4: | On compare la partition la plus économique parmi celles correspondantes aux paires de concentrateurs1 -2, 1-3, 1-4 et 1-5 avec celle de l’étape1 . Celle dont le coût est le plus faible est alors considérée comme nouvelle partition de base. Ainsi, la partition du tableau9 .4, correspondant à la paire 1-4 et de coût2 8, devient la partition de base. |
| Étape 5: | On introduit successivement les concentrateurs2 , 3 et 5 pour former les partitions correspondant aux triplets1 -4-2, 1-4-3 et 1-4-5, en ayant soin de calculer le coût respectif de chacune de ces partitions, ce que montrent les tableaux9 .6, 9.7 et 9.8. |
| TABLEAU 9.6 | TABLEAU 9.7 |
SCHÉMA D’AFFECTATION 1-4-2 SCHÉMA D’AFFECTATION 1-4-3
CONCENTRATEUR CONCENTRATEUR
1 2 3 4 5 1 2 3 4 5
| 1 | 8 | 3 | 7 | 4 | 1 2 3 4 |
