Promenades dans un labyrinthe

Cette semaine, au lieu de chercher le plus cours chemin dans un graphe, nous allons nous intéresser au plus long chemin. Indépendamment de l'aspect ludique, c'est en fait un problème difficile qu'on aurait bien du mal à résoudre de façon raisonnable sur un gros graphe comme celui du métro. Pour simplifier, nous allons donc considérer des labyrinthes.

Les labyrinthes

On considère des labyrinthes rectangulaires de taille hauteur x largeur. L'entrée du labyrinthe est en haut à gauche, la sortie en bas à droite. Un labyrinthe n'est rien d'autre qu'un graphe. Par exemple, le labyrinthe

correspond au graphe suivant :

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

Labyrinthes	taille	Plus court chemin	Plus long chemin
petit	4 x 8	12	18
grand	16 x 27	41	>=337
a	20 x 25	43	>=391
b	10 x 12	28	82
c	50 x 50	98	>=2036
d	60 x 60	118	>=1944
zoo	7 x 22	27	107
foo	7 x 22	27	153
bar	7 x 22	27	153

Il n'est pas très difficile de convertir ces fichiers textes en représentation interne. L'opération inverse peut permettre de visualiser des solutions.

Si ces opérations vous semblent trop fastidieuses, vous pouvez utiliser une solution toute faite. Attention, cette solution n'utilise pas exactement les mêmes structures de données qu'au dernier TP, et il est tout à fait possible qu'elle ne vous convienne pas. N'hésitez pas à la modifier pour manipuler les structures qui vous plaisent.

Première promenade : chercher la sortie

La première fois qu'on visite un labyrinthe, c'est souvent pour s'amuser à trouver la sortie. Quand on le fait de façon systématique (méthode de la main gauche, qui consiste à toujours tourner à gauche sans revenir sur ses pas), on visite en fait le labyrinthe par un parcours en profondeur.

Écrire cette première promenade.

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é.

Deuxième promenade : le visiteur pressé

Cette fois, on essaye de sortir du labyrinthe le plus vite possible. L'algorithme le plus efficace est très similaire à celui vu au TP précédent. La seule différence est la file utilisée lors du parcours qui n'a plus besoin d'être une file de priorité. On peut se contenter d'une file ordinaire (implémentée par un pointeur sur le début d'une liste et un pointeur sur la fin) dans laquelle on ajoute toujours les éléments en queue.

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

Troisième promenade : le touriste

Les vraies promenades, ça prend du temps. Dans cet esprit, nous allons chercher le plus long chemin possible (sans cycle, évidemment) entre l'entrée et la sortie.

Première solution : recherche exhaustive

Le parcours en profondeur explore tous les chemins possibles jusqu'à en trouver un qui arrive à la sortie. Il est facile de le modifier pour qu'il ne s'arrête pas à la première solution mais continue en gardant la solution la plus longue en mémoire.

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).

Peut-on faire mieux ?

Puisqu'il existe un algorithme pour trouver le chemin le plus court en un temps raisonnable, on peut se demander si un tel algorithme existe pour le chemin le plus long. En fait, la réponse reste ouverte. Ce problème appartient à la classe des problèmes NP-complets. C'est à dire que si il existe un algorithme pour le résoudre en temps polynomial dans le cas le pire, alors il en existe un aussi pour une série de problèmes classiques (satisfiabilité des formules booléennes, voyageur de commerce...) qu'on ne sait pas à l'heure actuelle résoudre en temps polynomial (notez qu'on ne sait pas non plus si c'est impossible).

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

On peut obtenir de bons résultats approchés tout simplement en orientant la recherche en profondeur. L'orientation consiste à choisir l'ordre dans lequel on parcourt les arêtes d'un noeud donné. L'idée est de choisir en premier celles qui éloignent de la sortie (selon une distance à préciser : euclidienne, Max, Manhattan...).

Si vous avez stocké le graphe sous forme de tableau de listes d'adjacence (comme pour le précédent TP), 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

Le résultat de l'algorithme précédent donne la solution suivante sur le grand labyrinthe :

Un être humain moyennement constitué voit facilement comment améliorer ce chemin. Par exemple, on peut dès le début faire un petit détour qui rajoute 9 cases.

É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