TP 4 : Programmer un algorithme exhaustif

Lors de ce TP, nous allons programmer un algorithme de recherche exhaustif pour aller chercher plusieurs morceaux de fromage dans le labyrinthe en un minimum de temps. On utilisera donc l’option “-p ” du programme PyRat. Pensez à vérifier que le nombre de morceaux de fromages n’est pas trop haut.Pour ce faire, nous allons d’abord créer le “méta-graphe” permettant de réduire notre problème à celui du voyageur de commerce.

Obtention du méta-graphe

Ecrivez une fonction qui, à partir de la carte du labyrinthe, renvoie un graphe complet dont les sommets sont les emplacements des morceaux de fromage et la position de départ, et dont les arêtes sont pondérées par les longueurs des plus courts chemins reliant ces sommets.

Algorithme exhaustif

Programmez une recherche exhaustive du meilleur parcours pour le voyageur de commerce sur le méta-graphe. Cette fonction pourra au choix renvoyer une table de routage permettant de retrouver le chemin solution, ou directement ce chemin.

Lien avec le labyrinthe

Une fois le résultat du voyageur de commerce obtenu, écrivez une fonction pour transformer le chemin solution en une suite de mouvements permettant de se déplacer dans le labyrinthe.

Quoi faire ensuite ?

Les résultats obtenus en suivant ce TP seront présentés lors de l’entretien de la séance 6.