Consulter le cours sur la theorie des graphes dans la section langage C avant de s'interesser à ce projet

Le programme codé permet de construire des labyrinthes et de les résoudre grâce à l' algorithme BFS et à une recherche heuristique. Ce programme a été réalisé en C avec la librairie GTK. Celle-ci démontre dans cette application une partie de son potentiel.

La sortie d'un labyrinthe est une illustration très parlante du parcours de graphe. Un labyrinthe, composé de n × m cases numérotées par des couples ( i , j ), est représenté en machine par un graphe non orienté dont les sommets sont étiquetés par des couples ( i , j ). Lorsqu'une case ( i 0 , j 0 ) communique avec une autre case ( i 1 , j 1 ), alors il existe un arc entre les nœuds ( i 0 , j 0 ) et ( i 1 , j 1 ) du graphe. En outre, deux cases (nœuds) sont particuliers, ce sont l'entrée et la sortie du labyrinthe.

Soit le labyrinthe suivant :

Son espace d'états sera représenté par le graphe non orienté :

Un état sera décrit par un nœud de coordonnées(i, j), i étant le numéro de ligne (ou ordonnée) et j le numéro de colonne (ou abscisse) d'une case.

L` état initial est E 0 = (0,0) et l' état solution est (3,7)

Aller de l'entrée E 0 vers la sortie du labyrinthe revient donc à trouver un chemin dans le graphe d'un sommet vers un autre. On commencera pour cela un parcours exhaustif du graphe à partir du sommet entrée, parcours que l'on arrêtera dès que la sortie sera atteinte.

Une solution est un chemin menant à l`état solution. Plus concrètement, une solution sera une suite d'opérateurs qui étant appliqués successivement, en partant de l`état initial, conduit à l`état solution.

L` ensemble d `opérateurs sont tous les liens qui permettent de passer d'une case à toutes les cases adjacentes.

Un chemin peut être construit en insérant pour chaque état visité son prédécesseur. Il peut être alors parcouru à chaque instant en partant du dernier état inséré vers le premier.

Ce graphe peut être représenté par un tableau à 2 dimensions dont chaque case pointe vers la liste de ses voisins :