Aller au contenu

Séance 1   Calculs d'itinéraires

Activité 1   « En route vers la meilleure choco du monde! »

chocolatine

Objectifs

  Comprendre le principe de représentation des chemins et routes par un graphe ;

  Savoir utiliser différents services de cartographie pour optimiser un calcul d'itinéraire selon un critère donné.

carte

Problématique

Marcel est en vacances dans les Pyrénées. Il a trouvé un hotel bon marché où loger à Lannemezan, et avant d'aller admirer le magnifique cirque de Garvarnie, il veut absolument goûter à la meilleure chocolatine du monde, dans la boulangerie d'Argelès-gazos. Aide-le à trouver le meilleur itinéraire à emprunter.

Recherche manuelle d’un itinéraire optimisé

 Icône de crayon Travail à effectuer

1⃣   À l’aide du service d'exploration de cartes de cartes.gouv.fr, indiquer sur le graphe ci-dessous le nom des villes manquantes

Image de cartes.gouv.fr

2⃣   La route entre Capvern et Ibos est une autoroute (vitesse maximale autorisée : 130 km/h), alors que toutes les autres routes sont des routes départementales (vitesse maximale autorisée : 80 km/h). Complète le graphe en indiquant entre chaque ville le temps de parcours, si l’automobiliste roule à la vitesse maximale autorisée.

graphe_a_completer

3⃣ Quel est l’itinéraire le plus rapide?

4⃣ Quels sont les autres critères qui pourraient être pris en compte pour choisir le « meilleur » itinéraire?

  Villes, routes et graphe

graphe

  • Pour représenter un ensemble de villes et l'ensemble des routes les reliants, on utilise un graphe

  • Chaque ville est représentée par un point appelé sommet, et chaque route par un segment appelé arête.

  • La forme des routes n'est pas prise en compte ; seul compte leur longeur que l'on indique au-dessus des arêtes.

  • Cette représentation permet la manipulation par un ordinateur

Utilisation d’un logiciel de calcul d’itinéraire

 Icône de crayon Travail à effectuer

2⃣   Recopie sur ton carnet de bord puis complète le tableau suivant à l'aide des trois services de calcul d'itinéraires proposés.

cartes.gouv.fr Google Maps Via Michelin
Distance parcourue (km)
Durée (min)
Coût (€)
Critères d'optimisation

3⃣ Que peux-tu en conclure ?

4⃣ Effectue une recherche pour trouver quel est l’Algorithme le plus célèbre pour trouver le chemin le plus court dans un graphe? En quel année a-t-il été publié ?

Utilisation d'un algorithme de calcul de plus court chemin

Dans la partie précédente, tu as calculé « à la main » le plus court chemin entre Lannemezan et Argelès-gazos, de façon intuitive. Pour qu'une machine puisse arriver à ce résultat, il faut obligatoirement lui « dire comment faire » en lui fournissant un algorithme.

C'est exactement de ce que fait l'algorithme de Dijkstra ; il permet de calculer le plus court chemin entre deux sommets d'un graphe.

  Lien vers le tutoriel sur l'algorithme de Dijkstra par Y. Monka

 Icône de crayon Travail à effectuer

Visionne le tutoriel sur l'algorithme de Dijkstra, puis exécute-le sur le graphe représentant les routes entre Lannemezan et Argelès-gazot pour trouver le plus court chemin, puis compare-le à celui que tu as trouvé dans la première partie.

COURS