TP 6 : Parcours d'une arborescence.

Une équipe de spéléologues s'est perdue dans un réseau de galeries souterraines.

Ce réseau de galeries souterraines n'a qu'une entrée, et il est impossible d'y tourner en rond ; on peut donc le modéliser par un arbre.

L'équipe de secours étant très sollicitée, elle cherche à minimiser le nombre de sauveteurs à envoyer dans la grotte pour retrouver l'équipe de spéléologues.

Pour cela, elle dispose des plans du réseau de galeries.

Attention ! Les spéléologues perdus peuvent se déplacer pendant qu'on les recherche. Il faut donc faire attention à ce que l'équipe perdue ne se déplace pas dans une galerie déjà visitée par les sauveteurs sans que l'un d'eux ne s'en aperçoive.

Exemple de déplacement possible si les sauveteurs ne sécurisent pas correctement les carrefours entre les grottes :

On note l'endroit où se trouvent les spéléologues perdus d'un P rouge.

Les galeries déjà visitées par les sauveteurs sont symbolisées par des liens bleus, et les intersections de galeries surveillées par des sauveteurs sont marquées par un S bleu.

Initialement (cf. figure 1), les spéléologues perdus se trouvent dans la galerie de droite, et sauveteurs ont visité la partie gauche de la grotte.

Les spéléologues perdus peuvent redescendre dans la galerie située en bas à gauche en passant par le carrefour de galerie du haut (cf. figure 2).

Cette situation n'aurait pas été possible si un sauveteur était resté à l'entrée de la grotte.

Figure1

;

Figure2

Données fournies : La topologie du réseau de grotte sera fourni sous forme de codage « vecteurs de pères ».

Travail à réaliser :

A l'issue de l'exécution de votre programme, il faudra fournir le nombre minimum de sauveteurs à envoyer pour la recherche, ainsi que l'itinéraire que chacun devra suivre pour effectuer la recherche.

Attention : ce problème est très complexe si l'on cherche à obtenir une solution optimale. Il vous est donc demander de donner une solution offrant un résultat satisfaisant sans être optimal. N'utilisez pas autant de sauveteurs qu'il y a d'intersections dans la grotte, ce résultat n'est pas satisfaisant !!!