Photographie Numérique et Image · 3e Trimestre

Calcul d'itinéraire et algorithmes

Étude des algorithmes de recherche de chemin le plus court dans un graphe routier.

À propos de ce thème

Le calcul d'itinéraire est un problème algorithmique fondamental que les élèves utilisent quotidiennement sans en connaître les rouages. Trouver le chemin le plus court dans un graphe routier implique des algorithmes comme celui de Dijkstra, qui explore méthodiquement les nœuds d'un réseau en partant du point de départ. Ce sujet de SNT en Seconde permet de relier la théorie des graphes à une application concrète que chaque élève maîtrise déjà en tant qu'utilisateur.

La complexité du problème devient palpable quand on réalise qu'un réseau routier national comporte des millions de nœuds et d'arêtes. Les algorithmes modernes utilisent des heuristiques (comme A*) et des données de trafic en temps réel pour accélérer la recherche. Les élèves découvrent ainsi que l'optimalité dépend du critère choisi : distance, temps, consommation de carburant.

Manipuler des graphes sur papier ou sur un plateau de jeu, puis comparer les résultats avec ceux d'un algorithme programmé, permet aux élèves de construire une intuition solide avant de formaliser les concepts.

Objectifs d'apprentissage

• Comparer la complexité des algorithmes de recherche de chemin le plus court pour différents types de graphes routiers.
• Expliquer le fonctionnement de l'algorithme de Dijkstra pour trouver le chemin le plus court dans un graphe pondéré.
• Analyser l'impact des données de trafic en temps réel sur le calcul d'un itinéraire optimal.
• Concevoir une représentation simplifiée d'un réseau routier sous forme de graphe pour résoudre un problème d'itinéraire.
• Évaluer la pertinence de différents critères (distance, temps) pour définir le 'meilleur' itinéraire.

Avant de commencer

Introduction aux algorithmes

Pourquoi : Les élèves doivent avoir une compréhension de base de ce qu'est un algorithme et de son rôle dans la résolution de problèmes.

Notions de base sur les réseaux et connexions

Pourquoi : Une familiarité avec l'idée de points connectés par des lignes est nécessaire pour comprendre la représentation sous forme de graphe.

Vocabulaire clé

Graphe	Structure mathématique composée de sommets (ou nœuds) reliés par des arêtes. Dans notre cas, les villes sont des sommets et les routes sont des arêtes.
Algorithme de Dijkstra	Algorithme qui trouve le chemin le plus court entre un sommet de départ et tous les autres sommets d'un graphe dont les poids des arêtes sont non négatifs.
Poids d'une arête	Valeur associée à une arête dans un graphe, représentant par exemple la distance ou le temps de trajet entre deux sommets.
Nœud	Point dans un graphe, représentant par exemple une intersection ou une ville. Également appelé sommet.
Heuristique	Technique de résolution de problèmes qui utilise une approche pratique, souvent plus rapide mais pas garantie d'être optimale, comme l'algorithme A*.

Idées d'apprentissage actif

Jeu de plateau : Le plus court chemin

Les élèves reçoivent un plateau représentant un réseau routier simplifié avec des poids sur chaque arête (temps ou distance). En binôme, ils cherchent manuellement le chemin le plus court entre deux villes, puis comparent leur solution avec celle obtenue en appliquant l'algorithme de Dijkstra pas à pas.

⏱ 40 min·Binômes

Générer mission

Galerie marchande: Les critères d'optimisation

Chaque groupe affiche un poster présentant un itinéraire optimisé selon un critère différent (temps, distance, péages, émissions CO2). Les élèves circulent, annotent les posters avec des post-it et votent pour le critère le plus pertinent selon différents scénarios proposés.

⏱ 30 min·Petits groupes

Générer mission

Programmation guidée : Dijkstra en Python

Les élèves implémentent pas à pas l'algorithme de Dijkstra sur un graphe de 10 nœuds. L'enseignant fournit la structure de données et les élèves complètent la boucle principale. Ils testent ensuite leur code sur le réseau du plateau de jeu pour vérifier la cohérence avec leur résultat manuel.

⏱ 45 min·Binômes

Générer mission

Liens avec le monde réel

Les ingénieurs de Google Maps ou Waze utilisent des algorithmes avancés, souvent basés sur Dijkstra ou A*, pour calculer les itinéraires les plus rapides en tenant compte du trafic en temps réel et des limitations de vitesse. Ils doivent gérer des graphes contenant des millions de routes et d'intersections.

Les entreprises de logistique, comme Chronopost ou UPS, optimisent les tournées de leurs chauffeurs grâce à des algorithmes de calcul d'itinéraire. Cela permet de réduire les coûts de carburant et les délais de livraison, en calculant le chemin le plus efficace pour livrer plusieurs colis dans une zone géographique donnée.

Les systèmes de navigation embarqués dans les voitures modernes (GPS) emploient ces algorithmes pour proposer des trajets adaptés aux conditions de circulation actuelles, en recalculant constamment l'itinéraire en cas de ralentissement ou d'accident.

Attention à ces idées reçues

Idée reçue courante

Le chemin le plus court en distance est toujours le plus rapide.

Ce qu'il faut enseigner à la place

Un chemin court peut traverser des zones urbaines congestionnées ou des routes à vitesse limitée. Le temps de parcours dépend de la vitesse autorisée, du trafic et des feux. Comparer les itinéraires proposés par un GPS selon les critères temps/distance aide les élèves à saisir cette distinction.

Idée reçue courante

Le GPS teste tous les chemins possibles pour trouver le meilleur.

Ce qu'il faut enseigner à la place

Tester toutes les combinaisons serait impossible : pour 20 villes, il existe plus de 2 milliards de milliards de chemins. L'algorithme de Dijkstra élimine intelligemment les chemins non prometteurs. Faire chercher manuellement le meilleur chemin dans un graphe de 8 nœuds, puis compter les opérations, rend cette explosion combinatoire concrète.

Idée reçue courante

Un seul algorithme gère tout le calcul d'itinéraire.

Ce qu'il faut enseigner à la place

Les systèmes de navigation combinent plusieurs algorithmes : pré-calcul hiérarchique pour les grandes distances, Dijkstra ou A* pour le dernier kilomètre, et des modèles prédictifs pour intégrer le trafic. Décomposer un trajet long en étapes aide les élèves à comprendre cette architecture multicouche.

Idées d'évaluation

Vérification rapide

Présentez aux élèves un petit graphe routier simple (4-5 villes, quelques routes avec distances). Demandez-leur de tracer à la main les étapes de l'algorithme de Dijkstra pour trouver le chemin le plus court entre deux villes spécifiques. Vérifiez la bonne application des étapes.

Question de discussion

Posez la question : 'Si vous deviez concevoir un GPS pour des vélos, quels seraient les critères les plus importants pour définir le 'meilleur' itinéraire, et comment cela changerait-il l'algorithme par rapport à une voiture ?' Encouragez la discussion sur les poids des arêtes (dénivelé, pistes cyclables, sécurité).

Billet de sortie

Demandez aux élèves d'écrire sur un post-it : 1) Le nom d'un algorithme de calcul d'itinéraire étudié. 2) Une phrase expliquant pourquoi les données de trafic en temps réel sont cruciales pour un GPS. 3) Un exemple concret où le chemin le plus court n'est pas forcément le plus rapide.

Questions fréquentes

Comment fonctionne l'algorithme de Dijkstra pour trouver le plus court chemin ?

L'algorithme de Dijkstra part du nœud de départ et explore progressivement les nœuds voisins en retenant toujours le chemin de coût minimal connu. À chaque étape, il marque un nœud comme visité et met à jour les distances de ses voisins. Il s'arrête quand le nœud d'arrivée est atteint. Cette approche garantit de trouver le chemin optimal sans explorer l'ensemble du graphe.

Pourquoi le GPS propose-t-il parfois un itinéraire plus long que prévu ?

Le GPS optimise le temps de trajet, pas nécessairement la distance. Il intègre les limitations de vitesse, les feux de circulation, les travaux et les données de trafic en temps réel. Un détour par autoroute peut être plus long en kilomètres mais plus rapide en minutes. Certains systèmes prennent aussi en compte les péages et la consommation de carburant.

Quelle activité pour enseigner les algorithmes de plus court chemin en SNT ?

Un jeu de plateau avec un graphe pondéré fonctionne très bien. Les élèves cherchent d'abord le chemin optimal par intuition, puis appliquent l'algorithme de Dijkstra étape par étape et comparent les résultats. Ce passage du tâtonnement à la méthode systématique illustre l'intérêt de l'algorithmique et ancre la compréhension dans l'expérience.

Quelle différence entre Dijkstra et A* en calcul d'itinéraire ?

Dijkstra explore les nœuds dans toutes les directions sans préférence. A* ajoute une heuristique qui estime la distance restante vers la destination, ce qui oriente la recherche et accélère le calcul. Sur un réseau routier, A* utilise typiquement la distance à vol d'oiseau comme heuristique. Il trouve le même résultat optimal que Dijkstra, mais en visitant moins de nœuds.