Graphique

[anonyme]

Bonsoir,

Je dois, dans le cadre d'un projet interdisciplinaire Maths-Informatique, créer un petit projet en Python. La consigne de mon professeur est :

A partir de l'algorithme de Dijkstra vu en cours, concevez un programme de 600 lignes environ afin de comparer différents types de transports de marchandises en France : routier, ferroviaire, et fluvial. Vous pourrez vous aider de la liste des gares de France disponible ici : https://data.sncf.com/explore/dataset/l ... res/table/. Vous pourrez la télécharger en CSV, pour ensuite la manipuler dans le programme Python. On considérera que toutes les gares sont ouvertes au transport de marchandises. Enfin, pour le calcul des distances routières, vous pourrez utiliser le module pyroutelib. A vous de trouver une solution pour calculer l'itinéraire fluvial et l'itinéraire ferroviaire.

Le transport est effectué d'un point A, pas forcément accessible au train ou à la péniche, à un point B, pas non plus forcément accessible au train ou à la péniche. Un pré-transport en camion jusqu'à une gare de marchandises ou un port fluvial est donc, le plus souvent, nécessaire. Les points A et B sont repérés par des coordonnées (latitude, longitude). La comparaison doit être basée sur les critères suivants : coût, empreinte environnementale, durée.

Une dernière indication : il est possible de combiner plusieurs modes de transports. Je vous encourage même à faire en sorte dans votre programme qu'une combinaison de transports intéressante apparaisse.

Voici là où j'en suis de ce problème :

Je ne sais pas du tout quoi faire... J'avoue être un peu - beaucoup - désemparé par ce projet...

Par quoi commencer ? Sachant que j'ai bien compris l'algorithme de Dijkstra... Mais je ne vois pas comment l'utiliser. Comment puis-je utiliser la liste des gares du site Internet ? J'ai vraiment du mal à commencer...

Merci beaucoup par avance pour votre aide, et joyeuses fêtes de fin d'année 2019.

[sos-math(21)]

Bonjour,
sur ce forum, nous répondons à des questions concrètes de mathématiques.
Ton projet est encore trop flou pour que nous puissions y apporter une aide précise. Par ailleurs, cela semble être un projet informatique (un script python de 600 lignes, cela ne relève plus de l'algorithmique/programmation traitée dans les programmes de mathématiques).
Je te recommande de demander des précisions auprès de ton professeur et qu'il vous transmette une sitographie pour vous aider.
Bon courage

[anonyme]

Bonjour,

Merci beaucoup pour votre réponse.

Je viens d'envoyer un mail à mon professeur pour avoir des précisions, je vous tiendrai au courant de sa réponse.

En attendant, je vais essayer de construire un graphe, et ça c'est des maths... Je ne sais pas comment le construire car j'ai la liste des gares avec latitude et longitude, mais il me faudrait les distances entre chaque gare pour construire le graphique de Dijkstra ? Comment connaître ces distances ? Avec une fonction Python ? Mais je ne sais pas comment calculer une distance entre deux points dont on a que les coordonnées, et ça c'est des maths...

J'espère que vous pourrez m'aider en attendant plus de précisions de mon professeur. Merci beaucoup.

[SoS-Math(9)]

Bonjour,
En quelle classe es tu ? Ton problème ne ressemble pas à celui d'un élève de lycée.
Pour calculer une disatance entre deux points A(\(x_{A}\) ; \(y_{A}\)) et B(\(x_{B}\) ; \(y_{B}\)) il y a une formule : AB = \(\sqrt{(x_{B} - x_{A})^2+(y_{B} - y_{A})^2}\).
J'espère que cela va t'aider.
SoSMath.

[anonyme]

Merci beaucoup pour votre réponse.

Je suis en Terminale S, option ISN. C'est un projet qui est coordonné par le prof d'ISN, mais aussi par celui de maths.

Merci pour la formule, j'ai écrit un programme Python qui fonctionne ! Mais maintenant j'ai un fichier CSV avec les coordonnées (latitude, longitude) de chaque gare de France. Comment puis-je calculer la distance entre chaque gare sur une même ligne ? Parce que ça n'a pas de sens de calculer la distance AB si A c'est la gare de Dijon et B la gare de Marseille : avec votre formule on calcule la ligne droite, mais la ligne ferroviaire n'est pas en ligne droite : pour faire Dijon-Marseille, il faut passer par Lyon, puis Valence, pour arriver enfin à Marseille.

Ma question est donc : comment calculer la distance ferroviaire entre un point A et un point B ? Donc pas en ligne droite. J'ai demandé à mon prof mais il refuse de me donner plus d'indications... Il dit simplement qu'il faut s'aider des maths. Voilà pourquoi je vous pose la question... Il faut s'aider de Dijkstra peut-être ? Mais je ne vois pas comment si c'est cela.

Merci encore pour l'aide.

[SoS-Math(9)]

Je ne connais pas "Dijkstra" …
Dans ton fichier, tu as peut-être la distance entre chaque gare ? Il suffit alors d'additionner les distances entre les gares de ton trajet.
Sinon calcule la distance entre chaque gare … puis additionne les distances entre les gares de ton trajet.
Je n'ai pas d'autres idées !

SoSMath.

[anonyme]

Merci beaucoup pour votre réponse.

Malheureusement je n'ai pas la distance entre chaque gare, c'est bien le problème...

Est-ce que une autre personne de SoS-Math aurait une idée ?
Je crois que SoS-Math 21 connaît Dijkstra car j'ai vu avec une recherche sur le site qu'il/elle avait déjà aidé quelqu'un dessus : viewtopic.php?f=9&t=18982.

Si SoS-Math 21 a donc une idée, ce serait formidable.

Merci encore pour l'aide.

[anonyme]

Ou toute autre personne que SoS-Math 21 qui aurait une idée bien sûr peut m'aider, car j'ai cherché tout l'après-midi, mais je n'ai rien trouvé...

Aussi, comment puis-je déterminer la gare la plus "intéressante" pour le trajet et proche du point A selon vous ?

Car ce n'est pas forcément la plus proche. Par exemple si le point A correspond à la ville de Foix (dans les Pyrénées), et que la destination est Marseille, il sera plus intéressant d'aller à la gare de Perpignan plutôt que d'aller à la gare de Toulouse qui est pourtant plus proche... Plus intéressant car pas de changement. Enfin c'est un simple exemple, comprenez-vous ce que je veux dire ?

Comment faire pour déterminer cette fameuse gare ?
Selon les profs il faut s'aider des maths...

Merci encore pour l'aide.

[sos-math(21)]

Bonjour,
en python, un graphe pondéré peut se représenter par un dictionnaire de listes ou un dictionnaire de dictionnaires, pour chaque sommet, on attribue un autre dictionnaire contenant les sommets et leur valuation, c'est-à-dire la distance qui les sépare.
On peut dès lors construire l'algorithme de Dijkstra en parcourant ce graphe. Pour plus d'explication, voir : https://www.supinfo.com/cours/2GRA/chap ... ts-chemins

Dans tous les cas, l'implémentation est compliquée, je te donne un lien vers un exemple de programmation : https://www.google.fr/url?sa=t&rct=j&q= ... GcKw_DBXU8

Le plus difficile est de constituer le graphe à partir des données du fichier csv, d'autant que je n'ai pas bien compris d'où venaient les différents moyens de locomotion : ton professeur parle de voie fluviale ?
Bonne continuation

[anonyme]

Merci pour votre réponse.

Mon professeur m'a envoyé un mail ce matin et voici ce qu'il dit :

"Dans un premier temps, concentrez-vous sur l'étude du mode de transport ferroviaire. Pour cela, commencez par modéliser le réseau ferroviaire français. Avec la liste des coordonnées (latitude, longitude) des gares de France disponible en fichier CSV, construisez un graphe pour ensuite utiliser l'algorithme de Dijkstra."

Mais voici mon problème : comment construire ce graphe ? Je vais expliciter mon problème avec un exemple. Si on s'intéresse à une partie de la région PACA, il y a par exemple les gares de Valence, Marseille, Montpellier, et Nice. Pour le graphe, il y a donc un segment entre Marseille et Montpellier, Marseille et Nice, Valence et Marseille, MAIS : pas entre Valence et Montpellier ou entre Valence et Nice, car les lignes directes n'existent pas !

Donc, comment construire le graphe ? Si vous avez une idée...

Merci infiniment pour votre aide.

[sos-math(27)]

Bonjour Anonyme,
Je ne suis pas du tout experte sur la construction de graphes...
J'ai fait quelques recherches rapides, mais pour ton niveau (terminale), je n'ai pas trouvé beaucoup de ressources :
une vidéo de M Monka : https://www.youtube.com/watch?v=yRBCx3uxN9A
un article destiné plutôt à des enseignants de math http://irem.univ-reunion.fr/spip.php?article705

mais le plus utile pour toi sera sans doute un article de wikipédia : https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
J'espère que cela te permettra de continuer ton projet, bon courage à toi !
à bientôt

[sos-math(21)]

Bonjour,
une fois que tu as la liste des gares avec leur coordonnées géographiques, https://www.data.gouv.fr/fr/datasets/r/ ... 5d1f654d28, tu peux lire le fichier csv et extraire les coordonnées de chaque gare et calculer les distances entre chaque gare en te servant du module pyroutelib3 qui permet de choisir le moyen de locomotion. Je te donne un début possible de code que tu pourrais utiliser dans ton projet

Code : Tout sélectionner

from pyroutelib3 import Router # Import the router
router = Router("train") # initialisation du moyen de locomotion, on peut choisir  car, cycle, foot, horse, tram, train

start = router.findNode(lat, lon) # coordonnées du point de départ
end = router.findNode(lat, lon) # coordonnées du point d'arrivée

status, route = router.doRoute(start, end) # recherche d'une route en s"appuyant sur des nœuds d'openstreetmap

if status == 'success': # si une route existe
    routeLatLons = list(map(router.nodeLatLon, route)) # la variable "routeLatLons" contient la liste des coordonnées 
    des points de cheminement (points qui constituent le chemin entre le point de départ et le point d'arrivée), 
    on peut ensuite calculer la longueur de cet itinéraire en prenant la fonction distance que l'on applique 
    de proche en proche aux termes de cette liste 

Bon courage

[anonyme]

Bonsoir,

Merci beaucoup pour vos réponses. Avoir une réponse même le 1er janvier, c'est remarquable !

SoS-21, je suis en train (sans mauvais jeu de mot) de construire le graphe. J'ai trouvé qu'il faut que je le fasse avec une liste d'adjacence (https://fr.wikipedia.org/wiki/Liste_d%27adjacence).

Mais j'ai un souci. Il faut donc que je connaisse chaque gare voisine d'une gare, car l'arête existe uniquement si la voie ferrée entre les 2 gares existe !
Dans votre fichier, il y a les numéros des lignes. J'ai donc, pour chaque ligne, la liste des gares voisines car on peut les trier dans l'ordre de succession sur la ligne avec Excel.

Par contre, comment puis-je ensuite relier les lignes ? Savoir, en quelque sorte, quelle ligne est voisine d'une autre ?

J'ai trouvé ce fichier : https://ressources.data.sncf.com/explor ... ype/table/. Je pense qu'il peut m'être utile car il y a les coordonnées géographiques du début de la ligne et de la fin, ainsi que le numéro de la ligne. Comment puis-je donc utiliser ce fichier pour relier les lignes entre elles dans le graphe ?

Merci encore, je sens vraiment que je progresse dans le projet, maintenant je vois mieux où je dois aller ! :)

[sos-math(21)]

Bonjour,
je ne suis pas sûr que l'on puisse construire la matrice de valuation/adjacence avec ce fichier csv ou alors cela va être fastidieux.
En première intention, j'aurais plutôt pensé à utilisé le fameux module pyroutelib qui doit fonctionner comme un gps et s'efforcer de construire un trajet en train au plus près des deux points donnés : si ces points sont des gares, on devrait avoir des trajets de type sncf avec des correspondances et des changements de ligne.
Mais je n'ai pas creusé plus que cela le problème et si tu parviens à construire la matrice d'adjacence en extrayant les informations grâce à des commandes python ou tableur, alors ce sera très bien.
Bonne continuation

[anonyme]

Une fois de plus, merci beaucoup pour votre réponse.

Désolé de vous déranger encore.

En fait, le problème est que je crois que le calcul d'un itinéraire ferroviaire avec pyroutelib n'est pas disponible pour la France... C'est pour cela que le professeur disait d'utiliser uniquement pyroutelib pour le calcul d'itinéraire routier, car ça c'est disponible en France.

L'objectif est donc de construire la matrice d'adjacence à partir de 2 données (j'ai demandé à mon prof et il m'a dit que j'étais sur la bonne voie !) : la donnée des gares et de leur appartenance à une ligne précise, tout ceci étant disponible dans votre fichier data.gouv.... Et avec la liste des lignes repérées par leur point de départ et leur point d'arrivée : https://ressources.data.sncf.com/explor ... ype/table/

À partir de ça, comment construire la matrice d'adjacence ? Normalement c'est possible car mon professeur m'a dit par mail ce matin que c'était bien à partir de ça qu'il fallait le faire...

Encore merci et désolé !