Activité pratique

Consignes globales

Dans cette activité, vous devrez développer une solution pour récupérer plusieurs morceaux de fromage en un minimum d’actions. Pour cela, nous allons programmer une recherche exhaustive, puis la compléter avec une stratégie de backtracking.

Si vous souhaitez aller plus loin, nous vous conseillons de jeter un œil à la partie sur les solveurs. Vous y découvrirez des concepts supplémentaires intéressants.

Contenu de l’activité

1 — L’algorithme exhaustif

1.1 — Préparation

• players/Exhaustive.py – Dupliquez le fichier TemplatePlayer.py et renommez-le en Exhaustive.py. Ensuite, renommez la classe en Exhaustive.

• games/visualize_Exhaustive.py – Créez un fichier qui lancera une partie avec un joueur Exhaustive, dans un labyrinthe avec de la boue (argument mud_percentage) et 5 morceaux de fromage (argument nb_cheese). Vous pouvez éventuellement définir un random_seed et une trace_length.

• tests/test_Exhaustive.py – En vous inspirant des fichiers test_DFS.py, test_BFS.py et test_Dijkstra.py vus lors des sessions précédentes, créez un fichier test_Exhaustive.py. Ce fichier contiendra les tests unitaires que vous développerez pour tester les méthodes de votre joueur Exhaustive.

1.2 — Programmer l’algorithme exhaustif

Pour écrire un algorithme exhaustif, suivez les mêmes étapes que la dernière fois. Commençons par les méthodes pour découper notre problème en sous-problèmes plus petits.

Maintenant que nous avons découpé le problème, réfléchissons aux tests unitaires nécessaires pour valider chaque méthode.

Maintenant que nous avons les prototypes des méthodes et des tests, nous pouvons implémenter tout ça.

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

Une fois votre programme fonctionnel, essayez d’augmenter le nombre de morceaux de fromage.

1.3 — Ajouter du backtracking

1.3.1 — Améliorations de la recherche exhaustive

Nous allons maintenant ajouter une stratégie de backtracking à notre recherche exhaustive. L’idée est de couper certaines branches de l’arbre d’exploration lorsque nous savons qu’elles ne mèneront pas à une meilleure solution que celle déjà trouvée.

On va donc essayer deux améliorations successives de notre algorithme exhaustif.

La qualité de cette stratégie dépendra de la manière dont vous décidez de couper les branches. En effet, plus on trouve tôt une bonne solution, plus on peut couper de branches.

Encore une fois, n’oubliez pas les tests !

1.3.2 — Évaluer vos améliorations

Vous avez maintenant trois programmes basés sur une recherche exhaustive. Il serait intéressant d’évaluer si vos améliorations accélèrent effectivement la résolution du TSP, ou si vos calculs supplémentaires nuisent aux performances.

Pour mesurer le temps nécessaire pour résoudre le TSP, vous pouvez :

• Tracer le temps moyen (sur 100 parties par exemple) requis pour terminer une partie, en fonction du nombre de morceaux de fromage dans le labyrinthe.

• Pour un nombre fixe de morceaux de fromage, calculer les distributions des temps nécessaires pour chaque programme. Ensuite, utilisez des tests statistiques adaptés pour évaluer si les distributions sont significativement différentes.

Pour comparer les branches, vous pouvez :

• Adapter votre code pour compter combien de branches ont été coupées lors de l’exploration. Un graphique intéressant que vous pourriez produire est le nombre de branches coupées, en fonction de leur profondeur dans l’arbre (c’est-à-dire, le nombre de sommets dans le chemin avant la coupure). En effet, plus tôt vous coupez une branche, moins vous avez de branches complètes à explorer, et donc plus l’algorithme sera rapide.

• Adapter votre code pour compter combien de branches complètes ont été explorées. Un graphique intéressant que vous pourriez produire est le nombre de branches complètes explorées de longueur au plus $l$, en fonction de la longueur $l$.

Pour aller plus loin

2 — Factoriser les codes

Dans les parties précédentes, nous vous avons demandé plusieurs fois de copier le fichier précédent comme base. Il en résulte probablement que vous avez plusieurs fois la même fonction dans ces fichiers, ce qui est problématique. En effet, si vous trouvez une erreur dans une telle fonction maintenant, vous devrez mettre à jour plusieurs endroits dans vos codes. C’est une surcharge de travail inutile, et vous pourriez ajouter de nouvelles erreurs en le faisant mal.

Voici deux choses possibles que vous pouvez faire (choisissez votre préférée) :

• Bibliothèque – Vous pouvez créer un fichier Python externe (par exemple appelé tsp_utils.py) et y écrire vos fonctions dupliquées. Ensuite, mettez à jour vos joueurs pour importer les fonctions nécessaires depuis ce fichier.

• Classe – Vous pouvez créer une classe abstraite TSPSolver (dans un répertoire utils), qui regroupe les méthodes communes à tous les solveurs exhaustifs. Ensuite, écrivez les classes ExhaustiveTSPSolver, BacktrackingTSPSolver et SortedNeighborsTSPSolver qui héritent de TSPSolver. Enfin, créez un joueur TSPPlayer.py qui utilise le solveur souhaité.

  Voici un petit diagramme UML représentant une factorisation possible. Consultez la séance 2 pour un guide sur la lecture de celui-ci.

  

3 — L’algorithme de branch-and-bound

Alors que le backtracking est une optimisation basée sur un algorithme DFS, l’algorithme de branch-and-bound repose sur une approche de type BFS. Cet algorithme vous a été présenté dans la section optionnelle d’un article que vous deviez étudier pour aujourd’hui.

Pour aller encore plus loin

4 — Solveurs

4.1 — Intuition des améliorations possibles

Il peut sembler étrange que nous ayons du mal à trouver la solution du TSP dans un graphe avec aussi peu de sommets que 10-15, alors que des outils comme les GPS, les planificateurs de trajets, etc., existent. En pratique, la plupart de ces outils reposent sur ce que nous appelons des “heuristiques”, qui trouvent des solutions approximatives (et non exactes). Vous étudierez de telles approches lors de la prochaine session.

Cependant, il reste encore des possibilités d’amélioration avec des algorithmes exacts. En effet, nous pouvons facilement penser à des améliorations simples. Par exemple, c’est probablement une mauvaise décision de faire des allers-retours dans le labyrinthe comme suit :

Attraper des morceaux de fromage proches est évidemment mieux que cette approche. Par exemple, cette permutation est nettement plus courte (bien qu’elle ne soit pas nécessairement la meilleure) :

Vous pouvez voir cette optimisation comme une sorte d’inégalité triangulaire. En effet, le méta-graphe qui représente la répartition des morceaux de fromage dans le labyrinthe est une matrice de distances avec des propriétés particulières. Cette propriété (et de nombreuses autres) sont exploitées par des outils avancés appelés “solveurs”.

4.2 — Qu’est-ce qu’un solveur ?

Un solveur est un outil générique qui, pour un problème donné, explore l’espace des solutions de manière intelligente. En effet, les solutions peuvent être organisées dans un espace abstrait, et leur proximité dans cet espace indique une similarité entre les solutions. Vous pouvez voir cela comme un graphe de solutions, et les solveurs exploreront ce graphe intelligemment pour trouver la solution optimale.

Nous n’entrerons pas dans les détails sur le fonctionnement des solveurs, mais voici un lien sur comment le formaliser mathématiquement si vous êtes intéressé(e).

4.3 — Utilisons un solveur

Pour l’utiliser, vous devez définir une matrice de distances qui modélise votre problème. Ensuite, adaptez l’exemple fourni par ORTools pour résoudre le TSP sur un labyrinthe PyRat.

Avec cette solution, vous devriez être capable de calculer la solution du TSP pour un grand nombre de morceaux de fromage dans le temps alloué à la fonction preprocessing(...).