Activité pratique

Consignes globales

Cette activité étend la précédente en proposant d’implémenter de nouveaux algorithmes de parcours de graphe, qui permettent de trouver des 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).

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é

1 — Algorithme de Dijkstra

1.1 — Préparation

Tout d’abord, nous allons créer un joueur et un script pour visualiser son comportement.

• players/Dijkstra.py – Inspirez vous de ce que vous avez fait lors des séances précédentes pour créer un joueur Dijkstra héritant de Player, et ayant :

  • Un constructeur __init__(...).
  • Une méthode preprocessing(...).
  • Une méthode turn(...).

  Dans un premier temps, ne vous préoccupez pas du comportement de votre joueur, créez juste le strict minimum pour pouvoir lancer une partie avec votre joueur Dijkstra sans que ça crashe.

• games/visualize_Dijkstra.py – Créez un fichier qui lancera une partie avec un joueur Dijkstra, 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). Inspirez-vous des autres fichiers du sous-dossier games que vous avez rencontrés lors des séances précédentes.

• tests/tests_Dijkstra.py – En vous inspirant des fichiers test_DFS.py et test_BFS.py rencontrés lors de la séance précédente, créez un fichier test_Dijkstra.py. Ce fichier contiendra les tests unitaires que vous développerez pour tester les fonctions définies dans Dijkstra.py.

1.2 — Programmer l’algorithme de Dijkstra

L’objectif principal de cette séance est d’implémenter l’algorithme de Dijkstra pour guider votre personnage dans le labyrinthe. En effet, maintenant que nous avons de la boue dans le labyrinthe, un simple parcours en largeur (BFS) ne suffit plus pour trouver le chemin le plus rapide vers le fromage.

1.2.1 — Identifier les fonctions

La dernière fois, en programmant les algorithmes BFS et DFS, nous avons identifié quelques tâches pour lesquelles nous avons créé des fonctions dédiées : les méthodes traversal(...) et find_route(...). Séparer ces deux blocs nous a permis d’écrire plus facilement des tests unitaires et d’obtenir un code pleinement fonctionnel.

1.2.2 — Réfléchir aux tests unitaires

Pour programmer vos fonctions, 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 dans test_Dijkstra.py. Cela vous permettra de tester vos méthodes plus fréquemment pendant leur développement, et vous pourrez être convaincu 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.

1.2.3 — Programmer et tester

La vidéo suivante montre un exemple de ce que vous devriez observer :

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

Pour aller plus loin

2 — Comparer avec les autres parcours

Comme précédemment, une chose simple que vous pouvez faire maintenant est de comparer tous les joueurs RandomX.py, DFS.py, BFS.py et Dijkstra.py sur des graphes pondérés.

3 — Factoriser les codes

Si vous avez suivi la partie optionnelle de la session précédente, vous devriez avoir factorisé vos fichiers BFS.py et DFS.py dans une classe Traversal à partir de laquelle vous dérivez deux classes BFSTraversal et DFSTraversal.

Voici le diagramme UML de la séance 2, auquel nous avons ajouté cette nouvelle classe :

Pour aller encore plus loin

4 — 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.

5 — 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.

6 — 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.