Un tel graphe est très pratique pour étudier par exemple les chemins d’un point du labyrinthe à tous les autres, mais n’est pas forcément optimal pour résoudre d’autres problèmes.
Notion de méta-graphe
Considérons le problème du voyageur de commerce appliqué à PyRat. Nous aimerions trouver le chemin le plus court pour ramasser tous les morceau de fromage dans le labyrinthe. Considérons le graphe présenté plus haut, et ajoutons-y quelques morceaux de fromage, représentés par des sommets colorés en jaune. Notons aussi notre position de départ, colorée en rouge.
Si on utilise ce graphe pour le problème du voyageur de commerce, on voit qu’il existe de nombreux sommets “parasites”, auxquels on se fiche d’accéder ou non. En revanche, ce qui nous intéresse, c’est de connaître les distances minimales entre les morceaux de fromage. En effet, le chemin le plus court pour ramasser tous les morceaux de fromage prendra forcément le chemin le plus court entre deux fromages ramassés successivement.
Pour cela, on décide d’extraire un méta-graphe du graphe d’origine, c’est à dire un graphe plus petit, plus abstrait, mais avec lequel il sera plus simple de travailler. Ici, on souhaite un graphe complet reliant les différents sommets colorés, et indiquant les longueurs des chemins les plus courts entre eux. Il nous suffira ensuite de calculer le chemin élémentaire le plus court sur ce graphe pondéré pour obtenir la solution.
Si on fait cela pour tout couple de sommets colorés dans l’exemple précédent, on obtient un graphe complet à 7 sommets, construit comme suit :
Notez que les pondérations de ce méta-graphe sont calculées en se basant sur le graphe du labyrinthe. Par exemple, la pondération 10 entre la position de départ et le fromage le plus en haut à gauche du labyrinthe correspond à la longueur du plus court chemin (par les mouvements droite – haut – haut – haut – haut – haut – haut – gauche – haut – droite), et est obtenue par un algorithme au choix (par exemple Dijkstra ou Floyd-Warshall).
On peut résoudre plus facilement le problème du voyageur de commerce sur ce graphe simplifié, et se servir du graphe d’origine pour déterminer les mouvements correspondant à la solution. Remarque : Notez qu’il faudra garder en mémoire non seulement les longueurs des chemins, mais aussi les mouvements à effectuer.