Activité pratique

Consignes globales

Dans cette activité, vous allez programmer un joueur qui attrape plusieurs morceaux de fromage en un minimum de tours. Comme vu dans les articles, cela revient à résoudre le problème du voyageur de commerce (TSP) sur un méta-graphe. Nous allons travailler avec la configuration suivante :

• Un seul joueur.
• Plusieurs morceaux de fromage à attraper (5 pour commencer).
• De la boue dans le labyrinthe (20% des arêtes, par exemple).

Vous commencerez par une recherche exhaustive, que vous accélérerez ensuite avec une stratégie de backtracking. Vous évaluerez enfin si ces améliorations accélèrent vraiment la résolution du TSP. Si vous souhaitez aller plus loin, les sections suivantes vous proposent de factoriser vos codes, puis de découvrir des algorithmes plus efficaces : branch-and-bound, solveurs, et algorithme de Held-Karp.

Comme pour la séance précédente, cette activité est peu guidée. Nous restons néanmoins disponibles pour vous aider si vous avez des questions, en classe ou sur Discord.

Contenu de l’activité

L’algorithme exhaustif

Préparation

• players/exhaustive_player.py — Dupliquez le fichier template_player.py et renommez-le en exhaustive_player.py. Ensuite, renommez la classe en ExhaustivePlayer.

• games/visualize_exhaustive_player.py — Créez un script qui lancera une partie avec un joueur ExhaustivePlayer, dans un labyrinthe respectant les critères listés plus haut (arguments mud_percentage et nb_cheese). 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).

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

Découper le problème

Pour écrire votre joueur, suivez la même démarche que lors des séances précédentes : commencez par découper le problème en sous-problèmes plus petits, chacun traité par une méthode.

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

Implémentation

Identifier tous les chemins possibles dans un graphe complet peut se faire de plusieurs manières :

• Parcours — Dans les articles, nous vous proposons une approche basée sur un parcours en profondeur (DFS). C’est encore plus simple avec un DFS récursif (voir la section « Pour aller encore plus loin » de la séance 2) qu’avec la version itérative de la séance 2. Cette approche a l’avantage de permettre d’intégrer des optimisations à différentes étapes de la recherche.

• Permutations — Chaque chemin dans le graphe complet correspond à une permutation de sommets (et vice versa). Vous pouvez donc facilement itérer sur toutes les permutations possibles, en utilisant par exemple la bibliothèque Python itertools. Cette solution est plus simple à programmer, mais ne vous permettra pas d’ajouter un backtracking dans votre recherche (voir plus bas). Nous vous suggérons donc d’utiliser cette approche uniquement si vous rencontrez trop de difficultés avec l’autre.

À 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 :

Jusqu’où peut-on aller ?

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

Ajouter du backtracking

Couper les branches inutiles

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.

Explorer d’abord les sommets prometteurs

La qualité de cette stratégie dépend de la rapidité avec laquelle on trouve une bonne solution. En effet, plus on trouve tôt une bonne solution, plus on peut couper de branches.

É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.

Temps de calcul

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

• Tracer le temps moyen (sur une vingtaine de parties par exemple) requis pour le prétraitement, en fonction du nombre de morceaux de fromage dans le labyrinthe. Les statistiques renvoyées par game.start() contiennent la durée du prétraitement de chaque joueur.

• Pour un nombre fixe de morceaux de fromage, comparer les temps nécessaires à chaque programme, avec un test statistique adapté. Comme à la séance 3, faites jouer tous les programmes sur les mêmes labyrinthes : cela permet d’utiliser un test apparié, et de vérifier des propriétés qui doivent être vraies sur chaque labyrinthe.

Branches explorées

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

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 méthode dans ces fichiers, ce qui est problématique. En effet, si vous trouvez une erreur dans une telle méthode maintenant, vous devrez mettre à jour plusieurs endroits dans vos codes. C’est une surcharge de travail inutile, et vous pourriez introduire de nouvelles erreurs en le faisant.

Comme lors de la séance 2, vous pouvez séparer le joueur de l’algorithme qu’il utilise :

• Créez une classe abstraite TSPSolver (dans un fichier utils/tsp/tsp_solver.py), qui définit ce qu’ont en commun tous les algorithmes de résolution du TSP : une méthode solve(...), qui stocke la solution trouvée dans des attributs route et length.

• Écrivez les classes ExhaustiveTSPSolver, BacktrackingTSPSolver et SortedNeighborsTSPSolver, qui héritent de TSPSolver (directement ou non), chacune dans son propre fichier d’un nouveau dossier utils/tsp. Essayez d’organiser la recherche pour que chaque amélioration n’ait à redéfinir qu’une petite méthode, comme le faisaient les parcours de la séance 2.

• Créez un joueur TSPPlayer (dans un fichier players/tsp_player.py), qui construit le méta-graphe avec votre classe DijkstraTraversal, et utilise le solveur choisi à sa création. Comme TraversalPlayer lors des séances précédentes, le joueur reçoit le solveur à utiliser à sa création, par exemple TSPPlayer(BacktrackingTSPSolver()).

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

Dans cette organisation, les trois solveurs forment une chaîne d’héritage :

• ExhaustiveTSPSolver contient toute la recherche (méthodes solve(...) et explore(...)). Elle fait appel à deux petites méthodes : must_cut(...), qui indique s’il faut abandonner la branche en cours (jamais, pour une recherche exhaustive), et order_neighbors(...), qui donne l’ordre dans lequel explorer les voisins d’un sommet (l’ordre donné, pour une recherche exhaustive).
• BacktrackingTSPSolver ne redéfinit que must_cut(...), et SortedNeighborsTSPSolver ne redéfinit que order_neighbors(...).

Contrairement aux joueurs, order_neighbors(...) et le compteur cut_branches remontent dans ExhaustiveTSPSolver, pour que chaque sous-classe n’ait qu’une méthode à redéfinir.

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 explore plusieurs branches de front, comme un BFS, ou plus précisément en commençant par la plus prometteuse (on parle d’exploration « meilleur d’abord »). 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

Solveurs

Intuition des améliorations possibles

Il peut sembler étrange que nous ayons du mal à trouver la solution du TSP dans un graphe avec une dizaine ou une quinzaine de sommets seulement, 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 séance.

Cependant, il reste encore des possibilités d’amélioration avec des algorithmes exacts. En effet, on peut facilement imaginer 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 conséquence de l’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 bien d’autres, sont exploitées par des outils avancés appelés « solveurs ».

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 explorent ce graphe intelligemment pour trouver une très bonne solution, optimale si on leur en laisse le temps.

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

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 OR-Tools pour résoudre le TSP sur un labyrinthe PyRat.

Si vous avez factorisé vos codes, écrivez ce solveur comme une nouvelle sous-classe de TSPSolver (dans un fichier utils/tsp/ortools_tsp_solver.py), et ajoutez-le aux algorithmes proposés par TSPPlayer. Sinon, créez un joueur qui hérite de votre joueur ExhaustivePlayer, et redéfinit sa méthode solve_tsp(...).

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 méthode preprocessing(...).

L’algorithme de Held-Karp

L’article sur le TSP présente un algorithme exact plus rapide que la recherche exhaustive : l’algorithme de Held-Karp. Il évite de refaire plusieurs fois les mêmes calculs grâce à la programmation dynamique, et a une complexité de $O(k^2 \cdot 2^k)$ en temps et de $O(k \cdot 2^k)$ en mémoire, pour $k$ morceaux de fromage.