Promenades dans un labyrinthe

1  Les labyrinthes

Ce labyrinthe, et d'autres, sont disponibles sous forme de fichiers textes. En voici la liste :

La première étape consiste à lire ces fichiers pour en construire une représentation interne. Le labyrinthe étant un tableau de cases, on pourra avantageusement utiliser un tableau, chaque case contenant un pointeur vers une structure qui mémorise différentes informations, comme la liste des cases voisines accessibles.

Écrivez les structures de données pour la représentation du labyrinthe. Le labyrinthe lui-même pourra être contenu dans une variable globale.

Pour la lecture du labyrinthe, vous pouvez vous inspirer de la procédure partielle suivante :

void lire_labyrinthe(char *fichier){
  FILE *file;
  char tampon[MAX_TAMPON]; //MAX_TAMPON doit avoir été défini par #define
  int i,j,l;
  file = fopen(fichier,"r");
  fgets(tampon, MAX_TAMPON, file);
  l = strlen(tampon);
  if(tampon[l-1]!='\n'){
    fprintf(stderr,"Labyrinthe trop large.");
    exit(1);
  }
  for(i=0;fgets(tampon, MAX_TAMPON, file);i++); 
  init_labyrinthe(i/2,(l-2)/2);
  fclose(file);
  file=fopen(fichier,"r");
  fgets(tampon, MAX_TAMPON, file);
  for(i=1; fgets(tampon, MAX_TAMPON, file); i++){
    for(j=1; j<lab_larg; j++){//lab_larg est une variable globale initialisée par init_labyrinthe
      if(tampon[j*2]==' ') {
        /* ajouter un voisin aux cases (i,j) et (i,j+1) */
      }
    }
    fgets(tampon, MAX_TAMPON, file);
    for(j=1; j<lab_larg; j++){
      if(tampon[j*2-1]==' ') {
        /* ajouter un voisin aux cases (i,j) et (i+1,j) */
      }
    }
  }
  fclose(file);
}

Pour faciliter les parcours et leur impression, ajoutez à vos structures de case un champ qui indique si une case est dans le parcours et des champs pour indiquer dans quelle direction on va.

Écrivez une fonction qui imprime un labyrinthe et la solution en cours.

Une solution possible

2  Première promenade : chercher la sortie

Écrire cette première promenade (il suffit d'une procédure récursive qui prend en argument un point de départ et un point d'arrivée et retourne 1 ou 0 selon qu'on peut ou non atteindre l'arrivée).

On peut noter que cet algorithme est particulièrement inefficace quand le labyrinthe n'a pas de sortie. Ce n'est d'ailleurs pas la seule situation où cet algorithme est lent. Essayez d'évaluer sa complexité.

3  Deuxième promenade : le visiteur pressé

Écrire la structure de données dans laquelle on range les noeuds à visiter. Chaque élément de la liste doit contenir un noeud de départ et un noeud d'arrivée qui doit être celui à visiter. Écrire aussi les procédures d'insertion d'un couple (départ, arrivée) dans la file, de lecture et suppression en tête dans la file et de libération de mémoire.

L'arbre des plus courts chemins sera représenté par un tableau dont les éléments sont au départ 0, puis si le noeud est dans l'arbre, le numéro de son père (ou lui-même, si le noeud est la racine).

Écrire la recherche du plus court chemin pour les labyrinthes.

4  Troisième promenade : le touriste

4.1  Première solution : recherche exhaustive

Tester cette solution.

Cette solution est bien entendu très coûteuse. On peut l'améliorer en évitant une partie du travail inutile. Il suffit de reconnaître si une configuration donnée a une solution ou non. Pour cela, la recherche de chemin le plus court à partir de la configuration est assez efficace.

Modifier cette solution en cherchant à chaque noeud si il existe un chemin vers la sortie (et si non, ne pas faire les recherches dans cette configuration).

4.2  Peut-on faire mieux ?

Dans de tels cas, on peut trouver des heuristiques qui vont donner le bon résultat dans la plupart des cas, ou des solutions qui s'approchent du meilleur résultat.

Promenade heuristique

Si vous avez stocké le graphe sous forme de tableau de listes d'adjacence vous pouvez trier ces listes en fonction du point de sortie avant de faire le parcours en profondeur classique. Sinon, vous pouvez modifier l'ordre de parcours des arêtes selon la position du noeud courant par rapport à la sortie.

Écrire cette promenade et comparez avec les résultats obtenus avec la méthode précédente. Vous pouvez encore améliorer l'algorithme de la même façon que précédemment, en vérifiant avant de faire la recherche s'il existe un chemin vers la sortie. Testez la différence avec les très gros labyrinthes.

Faire des détours

Écrire un algorithme qui, partant d'un chemin (par exemple celui obtenu avec l'heuristique précédente), cherche à l'allonger en y rajoutant des détours. Faire cela de façon récursive jusqu'à ce qu'on ne puisse plus rajouter de détour.

Solution