Activité pratique

Consignes globales

Cette activité prolonge la précédente : vous allez programmer un nouvel algorithme de parcours, l’algorithme de Dijkstra, qui permet de trouver des plus courts chemins dans un graphe pondéré. Nous allons travailler avec la configuration suivante :

• Un seul joueur.
• Un seul morceau de fromage à attraper.
• On ajoute de la boue dans le labyrinthe (20-30% des arêtes).

Autant que possible, vous repartirez du code factorisé à la fin de la séance 2 : vous verrez que l’algorithme de Dijkstra s’y intègre très naturellement. Vous comparerez ensuite ce nouveau joueur aux précédents.

Cette séance sera moins guidée que la précédente, et ce sera de plus en plus le cas à mesure que vous avancerez dans le projet. Nous restons néanmoins disponibles pour vous aider si vous avez des questions, en classe ou sur Discord.

Contenu de l’activité

Constater le problème

L’algorithme BFS trouve le chemin qui comporte le moins de cases. Dans un labyrinthe sans boue, c’est aussi le chemin le plus rapide. Voyons ce qu’il en est quand on ajoute de la boue.

Algorithme de Dijkstra

Partir de la version factorisée

Lors de la séance précédente, vous avez factorisé les parcours en profondeur et en largeur dans une classe abstraite Traversal. Ses sous-classes BFSTraversal et DFSTraversal ne diffèrent que par la structure de données qui stocke les sommets à explorer : une file pour l’une, une pile pour l’autre.

Comme vous l’avez vu dans l’article sur l’algorithme de Dijkstra, cet algorithme suit exactement le même schéma. Seule la structure change : c’est une file de priorité (un tas min), qui renvoie toujours le sommet le plus proche de la source parmi ceux qui restent à explorer.

• Quelle(s) classe(s) faut-il créer ou modifier pour ajouter l’algorithme de Dijkstra à cette organisation ? Complétez le diagramme en conséquence (sur papier, ça suffit).
• Quels attributs et méthodes doivent être créés ?
• La bibliothèque heapq, présentée dans l’article sur les tas min, vous sera utile. Comment pouvez-vous l’utiliser ?
• Votre méthode traversal(...) utilise-t-elle les poids des arêtes pour calculer les distances ? Si vous devez la modifier, cela change-t-il quelque chose pour BFSTraversal et DFSTraversal ?

Préparation

• utils/traversal/dijkstra_traversal.py — Créez une classe DijkstraTraversal héritant de Traversal, en vous inspirant de bfs_traversal.py.

  Si vous n’avez pas factorisé à la séance précédente, vous pouvez commencer par créer directement une classe Dijkstra dans players/dijkstra.py en vous inspirant de players/bfs.py.

• players/traversal_player.py — Rien à modifier : le joueur reçoit son parcours à sa création. Vous pouvez éventuellement faire de DijkstraTraversal son parcours par défaut, utilisé quand aucun parcours n’est donné.

  Si vous n’avez pas factorisé à la séance précédente, vous n’avez rien à faire ici.

• games/visualize_factorized_dijkstra.py — Créez un script qui lancera une partie avec ce joueur, dans un labyrinthe respectant les critères listés plus haut. Vous pouvez éventuellement définir une random_seed (pour toujours travailler avec le même labyrinthe) et une trace_length (pour suivre la trajectoire de votre joueur).

  Si vous n’avez pas factorisé à la séance précédente, nommez plutôt votre script games/visualize_dijkstra.py.

• tests/test_dijkstra_traversal.py — Créez un fichier qui contiendra les tests unitaires de votre algorithme. Pour le moment, créez juste le fichier avec une classe de tests copiée-collée de test_bfs_traversal.py (ou de test_bfs.py), en changeant le nom de la classe et en enlevant les méthodes de test.

  Si vous n’avez pas factorisé à la séance précédente, nommez plutôt votre fichier tests/test_dijkstra.py.

Implémentation

Tests

Pour programmer et tester votre algorithme, vous pouvez choisir entre deux approches :

• Approche classique — La méthode la plus courante pour développer un programme est de programmer le corps d’une méthode, puis de la tester. Une fois validée, passez à la méthode suivante, etc., jusqu’à ce que toutes les méthodes soient programmées.

• Développement piloté par les tests — Si vous préférez, avant de coder le contenu de vos méthodes, vous pouvez déjà écrire les tests unitaires. Cela vous permettra de tester vos méthodes plus fréquemment pendant leur développement, et vous pourrez être convaincu(e)s de votre travail lorsqu’elles passeront tous les tests que vous avez conçus.

Que vous les écriviez avant ou après le code, il est important de concevoir des tests qui vous convainquent que votre programme fonctionne comme prévu !

Par exemple, supposons que vous souhaitiez concevoir un test pour vous assurer que Dijkstra trouve le chemin le plus court dans un graphe pondéré, contrairement à un BFS. Intuitivement, vous voulez créer un graphe fixe, identifier le chemin le plus court à la main, et vérifier que la sortie de Dijkstra correspond à ce chemin. Cependant, le choix du graphe utilisé a une grande importance :

• Si vous choisissez un labyrinthe dans lequel il n’y a qu’un seul chemin entre votre position initiale et le morceau de fromage, alors les algorithmes BFS et Dijkstra trouveront tous deux le chemin correct.

• De même, s’il n’y a pas de boue le long du chemin le plus court entre votre position initiale et le morceau de fromage (ou s’il est toujours plus rapide de traverser cette boue que de l’éviter), alors encore une fois, les algorithmes BFS et Dijkstra trouveront le chemin correct.

À quoi ça ressemble ?

À présent, utilisez votre script de visualisation pour observer votre joueur. La vidéo suivante montre un exemple de ce que vous devriez observer :

Notez que le rat a volontairement évité la boue car le nombre de tours nécessaires pour l’esquiver est inférieur au nombre de tours nécessaires pour la traverser.

Comparer avec les autres parcours

Lors des séances précédentes, vous avez comparé vos joueurs en les faisant jouer un grand nombre de parties, puis en comparant leurs nombres de tours moyens. Maintenant que vous avez un joueur de plus, il est tentant de recommencer en l’ajoutant simplement à la liste. Mais une comparaison n’est utile que si elle répond à une question précise, et une bonne comparaison se prépare.

• Quels joueurs comparer ? Est-il utile de comparer à nouveau Dijkstra aux joueurs aléatoires, ou au DFS ? Quelle est la comparaison qui vous apprendra vraiment quelque chose ?

• Que sait-on déjà du résultat ? D’après le cours, certaines propriétés doivent être vraies sur chaque labyrinthe, et pas seulement en moyenne. Lesquelles ? Comment vérifier qu’elles sont bien respectées, plutôt que de le supposer ?

• Que mesurer ? Le nombre de tours est-il la seule mesure intéressante ? Que gagne-t-on en utilisant Dijkstra, et que perd-on ? Pour compter les cases traversées, notez que stats["players"][name]["actions"] donne le nombre de déplacements effectués dans chaque direction.

• Sur quels labyrinthes ? Que gagne-t-on à faire jouer tous les joueurs sur les mêmes labyrinthes ? Quel paramètre du jeu faire varier pour voir quand Dijkstra fait vraiment la différence ?

Pour aller plus loin

Comparer deux implémentations de la file de priorité

La complexité de l’algorithme de Dijkstra dépend de la file de priorité utilisée (voir la section sur la complexité dans l’article sur l’algorithme de Dijkstra). Avec un tas min comme celui de heapq, elle est de $O(n \cdot log(n))$ dans un labyrinthe PyRat. Avec une simple liste non triée, dans laquelle on cherche le minimum à chaque extraction, elle est de $O(n^2)$ dans le pire des cas.

Grâce à la factorisation, essayer une autre structure de données revient simplement à créer une nouvelle sous-classe de Traversal. Profitons-en pour vérifier en pratique ce que dit la théorie !

Pour aller encore plus loin

L’algorithme de Floyd-Warshall

L’algorithme de Dijkstra est ce que nous appelons un algorithme « 1-to-* ». Cela signifie qu’il trouvera les chemins les plus courts d’une position initiale unique à toutes les autres positions du graphe.

L’algorithme de Floyd-Warshall est ce que nous appelons un algorithme « *-to-* ». Il calculera simultanément tous les chemins les plus courts de tous les sommets à tous les sommets.

L’algorithme de Bellman-Ford

L’algorithme de Bellman-Ford est également un algorithme « 1-to-* ». Cependant, contrairement à l’algorithme de Dijkstra, il a la propriété de pouvoir trouver le chemin le plus court si certains arcs ont des poids négatifs. De plus, il peut être utilisé pour détecter un cycle absorbant dans le graphe.

L’algorithme de Johnson

L’algorithme de Johnson est un algorithme « *-to-* », qui exploite l’algorithme de Bellman-Ford pour trouver tous les chemins les plus courts dans le graphe.