Embed Size (px)
Citation preview
INSTITUT SUPERIEUR
D’INFORMATIQUE
DE MODELISATION
ET DE LEURS APPLICATIONS
Complexe des Cézeaux
BP 125 – 63173 Aubière cedex
Rapport de projet de 2ème année
Filière CALCUL SCIENTIFIQUE ET MODELISATION
CHEMIN DANS UN GRAPHE MULTI-CRITERE
Présenté par :
_Ahmed BOWA
_Hamza LEBBAR
Tuteur :
J.L.PARIS
Durée : 100 heures Année Universitaire : 2009/2010
2éme
année F4 ISIMA
Remerciements
Nous tenons à remercier notre chef de projet J.L.PARIS pour ses conseils tout au long du
projet et ses suggestions de généralisations du produit.
2éme
année F4 ISIMA
Glossaire
Langage C
++ : Langage de programmation orienté objet mis au point par
Bjarne Stroustup au début des années 1980. Le C++ est
l’un des langages de programmation les plus populaires
dans l’industrie informatique.
UML : Unified Modeling Language : Langage de modélisation
pour la programmation orientée objet.
Front de Pareto : Problème mathématique nécessitant l’optimisation
d’objectifs (contraintes).
Fichier.txt : Un fichier texte peut simplement contenir du texte dans
Une langue quelconque. Dans ce cas il ne respecte
aucune structure particulière.
Valuation : Fonction associant un poids à chaque arête.
Arête : Connexion entre deux sommets A et B. Dans le cas des
on parle d'arc. Le terme « arête » est alors utilisé pour
designer l'ensemble des deux arcs (A,B), c'est-à-dire de A
vers B et (B,A), c'est-à-dire de B vers A.
2éme
année F4 ISIMA
Table des figures
Figure 1 : Exemple d’un graphe ................................................................................................. 2 Figure 2 : Front de Pareto ........................................................................................................... 4 Figure 3 : Diagramme UML ....................................................................................................... 8 Figure 4 : L’affichage du graphe .............................................................................................. 13
Figure 5 : Exemple d’affichage d’un plus court chemin .......................................................... 14
2éme
année F4 ISIMA
Résumé
Viamichelin est un programme capable d’optimiser un itinéraire selon un seul critère à
la fois : distance ou coût ou temps.
Le sujet consiste à réaliser un programme qui optimise un itinéraire selon plusieurs
critères simultanément : distance et coût et temps.
En premier temps, nous avons réalisé un programme qui optimise l’itinéraire en
monocritère puis nous l’avons généralisé à la gestion de plusieurs critères simultanément.
Après, nous avons fait une compagne de tests sur des exemples fournis par notre tuteur
pour nous assurer du bon fonctionnement de notre code.
Mot-clé : Graphe, Chemin monocritère, Chemin multicritère, Front de Pareto, C++
.
2éme
année F4 ISIMA
Abstract
Viamichelin is an application that can optimize a route on a single criteria: distance,
cost and time.
The subject was to create an application that optimizes a route according to several
criteria simultaneously: cost, distance and time.
First, we developed a program that optimizes the single criteria route, then we
generalized it to manage multiple criteria simultaneously.
After that, we carried out testing on samples provided by our tutor to ensure the
smooth running of our code.
Keyword: Graph, Path single criterion, Path Multicriteria, Pareto Front, C + +
.
2éme
année F4 ISIMA
Table des matières
REMERCIEMENTS
GLOSSAIRE
TABLE DES FIGURES
RESUME
ABSTRACT
1. INTRODUCTION ............................................................................................................ 1
2. PROBLEME DU PLUS COURT CHEMIN .................................................................. 2
2.1. PROBLEME DU PLUS COURT CHEMIN MONOCRITERE .................................... 2
2.2. PROBLEME DU PLUS COURT CHEMIN MULTICRITERE ................................... 4
3. ALGORITHME DE DIJKSTRA .................................................................................... 5
3.1. DESCRIPTION DE L'ALGORITHME ......................................................................... 5
3.2. PSEUDO CODE POUR LE PROBLEME MONOCRITERE ....................................... 5
3.3. PSEUDO CODE POUR LE PROBLEME MULTICRITERE ...................................... 6
4. IMPLEMENTATION EN C++
........................................................................................ 7
4.1. DESCRIPTION DU CODE ........................................................................................... 7
4.2. DIAGRAMME UML ..................................................................................................... 8
5. TEST DU CODE ............................................................................................................ 12
6. CONCLUSION ............................................................................................................... 15
WEBOGRAPHIE ................................................................................................................... 16
1 2éme
année F4 ISIMA
1. Introduction
Dans le cadre de notre deuxième année d’étude a l’Institut Supérieur d’Informatique,
de Modélisation et de leurs Applications, nous avons effectué un projet de cent heures
reparties sur une période de six mois entre octobre 2009 et mars 2010 encadré par Mr
J.L.Paris sur la recherche du plus court chemin dans un graphe multicritère.
La théorie des graphes est une science qui a débuté avec les travaux du célèbre
mathématicien Euler quand il a voulu résoudre des problèmes liés à la vie quotidienne comme
celui des ponts de Königsberg (les habitants de Königsberg se demandaient s'il était possible,
en partant d'un quartier quelconque de la ville, de traverser tous les ponts sans passer deux
fois par le même et de revenir à leur point de départ) ou celui du plus court chemin entre deux
points.
En général, un graphe permet de représenter la structure, les connexions d'un
ensemble complexe en exprimant les relations entre ses éléments : réseau de communication,
réseaux routiers, interaction de diverses espèces animales, circuits électriques, ...
Les graphes constituent donc une méthode de pensée qui permet de modéliser une
grande variété de problèmes en se ramenant à l'étude de sommets et d'arcs.
Un graphe G est un couple G(X, E) constitué d'un ensemble X non vide et fini (dont
les éléments sont appelés sommets), et d'un ensemble E (dont les éléments sont appelés
arêtes) de paires d'éléments de X. Il peut être orienté ou non, selon que l'on munit ou non les
arêtes d'un sens de parcours, pondéré ou non, selon que l'on affecte à chaque arête une
« valeur » ou pas.
Nous présenterons dans une première partie l’objet de notre étude. Puis, dans une
deuxième partie, nous expliquerons notre analyse et les algorithmes que nous avons retenus.
Nous terminerons avec une compagne de tests et nous discuterons de la mise en œuvre
du projet.
2 2éme
année F4 ISIMA
2. Problème du plus court chemin
2.1. Problème du plus court chemin monocritère
Le problème du plus court chemin est un problème très ancien, présent dans de
nombreux domaines (trafics autoroutiers, ferroviaires, maritimes, optimisation d’un réseau,
intelligence artificielle, etc…)
Le problème est simple : Comment, en partant d’un point, arriver à un autre point en
faisant le moins de chemin possible ?
Pour mieux comprendre, prenons un exemple : Une voiture partant de Paris souhaite
se rendre à Toulouse. Mais l’autoroute entre Paris et Toulouse est bouchée. Le conducteur
aimerait savoir si, en passant par Bordeaux, il mettra plus ou moins de temps que pour aller à
Toulouse par l’autoroute. Sachant que le conducteur mettra 7 heures en passant par
l’autoroute, et qu’il mettra 5 heures pour aller à Bordeaux, et 3 heures pour relier Bordeaux à
Toulouse. Le graphe ci-dessous résume le problème.
Figure 1 : Exemple d’un graphe
3 2éme
année F4 ISIMA
Les points représentant les villes sont appelés « sommets », et les traits les liant sont
appelés les « arcs ». Chaque arc possède une valeur appelée « longueur de l’arc » et notée l.
Ainsi, pour l’arc Paris-Bordeaux, 5 correspond à l (Paris-Bordeaux), et non l’inverse,
car la flèche part de Paris pour aller à Bordeaux. On dit que ce graphe est un graphe
« orienté », car les arcs ont un sens.
Pour déterminer le plus court chemin entre Paris et Toulouse, il suffit d’additionner
les longueurs d’arcs des différents passages pour aller de Paris à Toulouse, et de les comparer.
Ici, on a l (P => T) = 7 et l (P => B) + l (B => T) = 5 + 3 = 8
On peut donc voir que l’automobiliste ferait mieux de passer par l’autoroute Paris-
Toulouse, plutôt que de faire un détour par Bordeaux, où il perdrait une heure !
Bien sur, les graphes utilisés dans le milieu professionnel sont beaucoup plus
complexes que celui du problème précédent. C’est pourquoi il existe des algorithmes
permettant de résoudre ces problèmes difficiles.
Néanmoins, certaines conditions régissent l’utilisation des algorithmes :
Il ne doit pas exister de « circuit absorbant » sur le chemin d’un point à un autre, c'est-
à-dire de boucle (on part d’un point et on revient à ce point) dans le graphe tel que la
somme des longueurs des arcs de cette boucle donne un chiffre négatif. Dans quel cas
il n’existe pas de plus court chemin entre ces deux points.
S’il n’y a pas de circuit absorbant, le plus court chemin entre ces deux points doit être
un « chemin élémentaire », c'est-à-dire que tous les arcs sont orientés dans le même
sens, et que le chemin ne passe pas deux fois par le même sommet.
Ensuite, certaines conditions sont spécifiques à chaque algorithme.
Il existe plusieurs algorithmes pour résoudre ces problèmes mais nous allons citer les 4
les plus utilisés : Bellman, Ford, Floyd et Dijkstra.
4 2éme
année F4 ISIMA
2.2. Problème du plus court chemin multicritère
Le problème du plus court chemin multicritère est un problème basé sur le problème
monocritère ; nous gérerons le multicritère selon l’approche de front de Pareto ce qui induit à
la gestion de plusieurs meilleures solutions. En d’autres termes il faut chercher des solutions
dont aucune ne domine l’autre.
Ceci est un exemple de front de Pareto dans un problème nécessitant la minimisation
de deux objectifs(ou deux critères) (f1 et f2). Les points A et B sont « non dominés » : parce
que si A dominait B, nous aurions f1(A)>f1(B) et f2(A)>f2(B) alors que ce n’est pas le cas.
Toute la zone au dessus de la ligne rouge appartient au front de Pareto.
Figure 2 : Front de Pareto
5 2éme
année F4 ISIMA
3. Algorithme de Dijkstra
3.1. Description de l'algorithme
L'algorithme de Dijkstra est un algorithme de type glouton : à chaque nouvelle étape,
on traite un nouveau sommet.
Tout au long du calcul, on va donc maintenir deux ensembles :
C, l'ensemble des sommets qui restent à visiter ; au départ C=S-{source} ou S est
l’ensemble des sommets et source est le sommet de départ.
D, l'ensemble des sommets pour lesquels on connaît déjà leur plus petite distance à la
source ; au départ, D={source}.
L'algorithme se termine bien évidemment lorsque C est vide.
Pour chaque sommet s dans D, on conservera dans un tableau distances le poids du plus
court chemin jusqu'à la source, et dans un tableau parcours le sommet p qui le précède dans
un plus court chemin de la source à s. Ainsi, pour retrouver le chemin le plus court, il suffira
de remonter de prédécesseur en prédécesseur jusqu'à la source, ce qui pourra se faire grâce à
un unique appel récursif.
3.2. Pseudo Code pour le problème monocritère
L’algorithme de recherche du plus court chemin monocritère est le suivant (Dijsktra) :
Tous les sommets sont marqués non définitif, ont une distance égale à l’infini et n’ont
aucune provenance.
Le sommet origine est marqué définitif, sa distance est égale à 0 et sa provenance est
lui-même.
Sommet courant = sommet origine.
Tant que le sommet destination n’est pas marque définitif
Pour chaque sommet voisin du sommet courant
D=distance du sommet courant + distance de l’arc entre le sommet
Courant et le sommet voisin.
Si D<distance du sommet voisin, alors
distance du sommet voisin = D ;
origine du sommet voisin = sommet courant ;
Fin si
Fin Pour
Sommet courant = le sommet non marque définitif ayant la plus petite distance.
Sommet courant est marque définitif.
Fin du tant que
6 2éme
année F4 ISIMA
3.3. Pseudo Code pour le problème multicritère
L’algorithme de recherche du plus court chemin multicritère est le suivant (Dijsktra
modifié) :
Tous les sommets sont marqués non définitif, ont une valuation égale à l’infini et n’ont
aucune provenance.
Le sommet origine est marqué définitif, sa distance est égale à 0 et sa provenance est
lui-même.
Sommet courant = sommet origine.
Tant que le sommet destination n’est pas marque définitif
Si sommet courant du sommet destination, alors
Si sommet courant améliore le chemin entre lui et le sommet
Destination, alors
Pour chaque sommet voisin du sommet courant
Chercher le plus court chemin entre sommet courant et
sommet de destination selon tous les critères (ce qui
nous donne un chemin par critère)
Mettre à jour le graphe ;
Fin pour
Fin si
Fin si
Sommet courant = le sommet non marqué définitif ayant la valeur qui minimise
tous les critères.
Sommet courant est marqué définitif.
Fin du tant que
7 2éme
année F4 ISIMA
4. Implémentation en C++
4.1. Description du code
Conformément à l’énoncé du sujet, nous avons programmé la solution du problème du
plus court chemin multicritère en C++
.
Pour décrire un graphe, nous avons utilisé un fichier de format txt dont la syntaxe
suivante :
NbSommets
NomVille1
NbVoisinsVille1
IdVoisin1 Critère1 Critère2 Critère3
.
.
.
IdVoisinN Critère1 Critère2 Critère3
NomVille2
NbVoisinsVille2
IdVoisin1 Critère1 Critère2 Critère3
.
.
.
IdVoisinN Critère1 Critère2 Critère3
.
.
.
NomVilleN
NbVoisinsVilleN
IdVoisin1 Critère1 Critère2 Critère3
.
.
.
IdVoisinN Critère1 Critère2 Critère3
NbSommets : le nombre de sommets dans le graphe ou autrement le nombre de villes.
NomVille : nom d’une ville représentant un sommet.
NbVoisinsVille : nombre de voisin de la ville courante
IdVoisinI : identifiant du Iiéme
voisin de la ville courante : chaque ville dispose
d’un unique identifiant qui permet de la retrouver.
CritèreI : c’est le Iiéme
critère
Par exemple :
14
Lille
3
2 400 200 30
3 150 10 35
4 650 57 70
8 2éme
année F4 ISIMA
Rennes
3
1 400 200 30
3 350 45 60
5 200 170 75
Le code que nous avons élaboré se compose de cinq classes :
Sommet : cette classe décrit un sommet d’un graphe.
Solution : la description d’une solution.
PileSol : elle choisi les solutions qui constituent le front de Pareto, parmi un
ensemble de solutions.
Graphe : elle charge un graphe depuis un fichier txt et implemente l’algorithme
de recherche du plus court chemin multicritère.
Test : une classe qui contient la methode main pour tester les classes précédentes.
4.2. Diagramme UML
Figure 3 : Diagramme UML
9 2éme
année F4 ISIMA
10 2éme
année F4 ISIMA
11 2éme
année F4 ISIMA
12 2éme
année F4 ISIMA
5. Test du code
Nous avons choisi de tester notre code avec l’exemple fourni par notre tuteur.
14
Lille
3
2 400 200 30
3 150 10 35
4 650 57 70
Rennes
3
1 400 200 30
3 350 45 60
5 200 170 75
Paris
4
1 150 10 35
2 350 45 60
4 550 49 90
6 250 11 39
Strasbourg
3
1 650 57 70
3 550 49 90
9 400 20 55
Nantes
3
2 200 170 5
6 400 20 40
7 350 230 17
Orleans
4
5 400 20 40
3 250 11 39
9 420 10 45
8 300 15 38
LaRochelle
3
5 350 230 17
8 450 70 48
11 550 270 70
Clermont
5
7 450 70 48
6 300 15 38
9 380 20 80
10 400 30 90
12 380 20 80
Dijon
4
4 400 20 55
6 420 10 45
8 380 47 70
10 150 18 32
Lyon
3
9 150 18 32
8 400 30 90
13 450 22 60
Pau
2
7 550 270 70
14 580 60 10
Millau
3
8 380 20 80
13 420 15 10
14 460 51 15
Marseille
2
10 450 22 60
12 420 21 15
Perpignan
2
12 460 15 10
11 580 60 10
14
Lille
3
2 400 20 30
3 150 10 35
4 650 57 70
Rennes
3
1 400 20 30
3 350 45 60
5 200 17 75
Paris
4
1 150 10 35
2 350 45 60
4 550 49 90
6 250 11 39
Strasbourg
3
1 650 57 70
3 550 49 90
9 400 20 55
Nantes
3
2 200 17 75
6 400 20 40
7 350 23 17
Orleans
4
5 400 20 40
3 250 11 39
9 420 10 45
8 300 15 38
LaRochelle
3
5 350 230 17
8 450 70 48
11 550 270 70
13 2éme
année F4 ISIMA
La figure suivante montre l’affichage que nous avons choisi pour le graphe. Cet affichage
permet de voir chaque ville, son identifiant, le nombre de ses voisins et leurs noms
accompagnés des valeurs de tous les critères.
Figure 4 : L’affichage du graphe
14 2éme
année F4 ISIMA
Voici un exemple d’une exécution de notre programme, montrant le plus court chemin entre
Lille et Nantes.
Figure 5 : Exemple d’affichage d’un plus court chemin
15 2éme
année F4 ISIMA
6. Conclusion
L’objectif de notre projet était de permettre de trouver le plus court chemin dans un
graphe multicritère. Les objectifs fixés au départ du projet pour arriver à ce résultat ont pu
être atteints.
Par ailleurs, notre solution est encore améliorable. D’une part l’affichage graphique
des solutions et d’autre part la sélection des options.
En dehors du cadre de notre projet, notre programme pourrait être encore amélioré en
ajoutant de nouvelles fonctionnalités de gestion du graphe : ajout et suppression de
sommets et d’arêtes. D’autre part , il serait intéressant de pouvoir faire la manipulation
autrement selon le choix d’un critère.
16 2éme
année F4 ISIMA
Webographie
1. http://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes
2. http://www.nimbustier.net/publications/djikstra/djikstra.html
3. http://frog.isima.fr/antoine/sommaire.shtml
