Extraire un graphe d’un graphe

Nous avons vu qu’il était généralement plus simple de résoudre un problème en le formalisant, et que les graphes pouvaient être utiles pour cela. Certains graphes sont assez intuitifs, comme par exemple pour représenter un labyrinthe :

maze_nodes_edges

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.

maze_nodes_edges_cheese

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 :

meta_graph

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.

Publié le

Laisser un commentaire