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.
Allez chercher tous les morceaux de fromage en un minimum de déplacements grâce à l’utilisation d’un algorithme exhaustif.
Tracez l’influence du nombre de morceaux de fromages (ou d’un autre paramètre plus intéressant) sur le temps de calcul de votre programme.
Allez plus loin !