Français

Algorithmes de plus court chemin

LycéeInformatiqueGraphe en grille avec 4 voisins ; coût des routes : 1, coût de la boue : 5, les murs bloquent le passage

Débloquez ce laboratoire avec un pass

Un pass donne accès à toutes les simulations du site, y compris au mode Présentation pour les cours. Les ressources pédagogiques ci-dessous restent gratuites pour tout le monde.

Voir les passJ’ai déjà un pass

Paiement unique, sans abonnement.

À propos de cette expérience

Les planificateurs d’itinéraires dans les cartes, les robots et les jeux vidéo résolvent tous le même problème : trouver le moyen le moins coûteux d’aller d’un départ à une arrivée. Sur cette grille, chaque pas sur une route coûte 1, un pas dans la boue coûte 5 et les murs sont infranchissables. Observez trois algorithmes classiques s’étendre depuis S. La recherche en largeur compte les pas et ignore la boue, Dijkstra explore toujours en premier la cellule la moins coûteuse, et A* ajoute une estimation de la distance restante pour pouvoir se diriger directement vers l’arrivée. Créez vos propres cartes et comparez la quantité de travail effectuée par chacun.

Objectifs pédagogiques

  • Représenter une carte comme un graphe de cellules reliées à leurs voisines, avec un coût pour chaque déplacement
  • Décrire comment la recherche en largeur explore la carte en anneaux de même nombre de pas
  • Explique pourquoi Dijkstra trouve le chemin le moins coûteux lorsque les étapes ont des coûts différents
  • Expliquez comment l’heuristique A* réduit le nombre de cellules explorées sans perdre le meilleur chemin
  • Comparez les algorithmes selon le coût du chemin trouvé et la quantité de travail effectuée

Comment l’utiliser

  1. 1Choisissez BFS et appuyez sur Rechercher. Le chemin trouvé passe-t-il dans la boue ? Consultez son coût dans le tableau.
  2. 2Choisissez Dijkstra et lancez une nouvelle recherche. Comparez le chemin et son coût avec ceux de BFS.
  3. 3Choisissez A*. Le coût de son chemin est-il le même que celui de Dijkstra ? Combien de cellules en moins a-t-il explorées ?
  4. 4Observez la frontière bleue pendant une recherche. En quoi sa forme diffère-t-elle avec Dijkstra et A* ?
  5. 5Peignez un mur pour bloquer la route qui contourne la boue. Quel algorithme modifie son chemin, et pourquoi ?
  6. 6Appuyez sur Effacer la carte et éloignez S et G en les faisant glisser. Sans obstacles, combien de cellules chaque algorithme explore-t-il ?

Le modèle

Le coût minimal pour atteindre une cellule est le minimum, parmi ses voisines, de leur coût auquel s’ajoute le coût du déplacement.
A* explore la cellule dont la valeur f est la plus faible : le coût déjà parcouru g plus le coût estimé restant h.
Distance de Manhattan jusqu’à l’objectif. Elle ne surestime jamais le coût réel, donc A* trouve toujours le chemin le moins coûteux.

Hypothèses

  • Les déplacements se font uniquement vers le haut, le bas, la gauche et la droite. Entrer dans une case coûte 1 sur une route et 5 dans la boue ; il est impossible d’entrer dans les murs.
  • Lors de la recherche, BFS considère que chaque déplacement coûte 1 ; il trouve donc le chemin comportant le moins de déplacements. Le coût indiqué dans le tableau est le coût réel de ce chemin, boue comprise.
  • Si deux cases ont la même priorité, celle qui a été ajoutée en premier est explorée en premier. Ainsi, avec la même carte, chaque exécution donne exactement le même ordre.
  • La recherche s’arrête dès que l’objectif est retiré de la frontière ; son coût minimal est alors connu.

À essayer en classe

  1. Q1Pourquoi BFS peut-il donner un chemin plus coûteux que Dijkstra, même s’il comporte moins de déplacements ?
  2. Q2Si toutes les cases étaient des routes, BFS et Dijkstra trouveraient-ils des chemins de même coût ? Pourquoi ?
  3. Q3Que se passerait-il pour A* si l’estimation h était dix fois supérieure à la distance de Manhattan ?
  4. Q4Pourquoi A* explore-t-il moins de cases lorsque l’objectif se trouve dans une zone dégagée, mais à peu près autant que Dijkstra dans un labyrinthe ?
  5. Q5Un GPS trouve en moins d’une seconde un itinéraire rapide à travers un pays comptant des millions d’intersections. Quelles idées de ce laboratoire rendent cela possible ?

Foire aux questions

Quel est le meilleur algorithme ?

Cela dépend du problème. BFS est simple et correct lorsque chaque étape a le même coût. Dijkstra gère des coûts différents. A* donne le même résultat que Dijkstra tout en explorant moins de cases, à condition de disposer d’une bonne estimation de la distance jusqu’à l’objectif.

Qu’est-ce que la frontière ?

La frontière est l’ensemble des cases qui ont été atteintes, mais pas encore explorées. Chaque algorithme retire une case de la frontière à la fois ; la seule différence entre eux est la règle qui détermine quelle case retirer ensuite.

Ces algorithmes peuvent-ils gérer des coûts négatifs ?

Dijkstra et A* supposent qu’aucune étape n’a un coût négatif. Avec des coûts négatifs, une case dont le coût avait été fixé pourrait ensuite se révéler accessible par un itinéraire moins coûteux ; un autre algorithme, comme Bellman-Ford, est alors nécessaire.