Démonstration stratégie du labyrinthe

adrien2019 · April 2021

Bonjour à tous
Je me pose une question que je poste dans le forum algèbre, même si je ne sais pas vraiment de quelle théorie elle relève.

Considérons un labyrinthe dessiné dans le plan, avec exactement deux "entrées" (une par laquelle on entre, l'autre par laquelle on sort). Il est connu qu'une stratégie pour trouver la sortie est de poser sa main sur le mur dès l'entrée, et de suivre ce mur: on tombera alors fatalement à un moment sur la sortie (càd l'autre "entrée").

Je cherche une démonstration rigoureuse de ce résultat, et je pense aussi une formulation plus "mathématique" de l'énoncé de la question (j'ai décrit "avec les mains" ce que j'ai en tête, mais par exemple je ne sais pas comment définir un "labyrinthe" mathématiquement, et encore moins ce que j'appelle "entrées", même si on voit bien à quoi ça correspond sur un dessin).

Je vous remercie d'avance pour votre aide !

MrJ · April 2021

Une idée : ce que tu décris reviens à parcourir en profondeur le graphe associé au labyrinthe jusqu'à tomber sur le noeud correspondant à ma sortie.

Avec cet algorithme, tu vas visiter l'ensemble de la composante connexe du noeud de départ.

adrien2019 · April 2021

@MrJ merci pour votre réponse, mais pourriez-vous préciser un peu plus votre raisonnement? Par exemple, j’ai du mal à voir le lien entre le labyrinthe et un graphe.

soland · April 2021

Oh!

Dreamer · April 2021

Bonsoir.

Dans le cas envisagé par Soland, l'entrée est aussi la sortie et la sortie est aussi l'entrée.

Du reste, la procédure appliquée permet de parcourir l'entièreté du "labyrinthe", en y entrant et en sortant deux fois avant de revenir à n'importe quel point de départ.

À bientôt.

adrien2019 · April 2021

Bonsoir,

Effectivement, le dessin de soland montre qu'on peut ressortir par la première entrée (et pas nécessairement par la seconde entrée).

J'ai de plus réfléchi et je ne suis pas certain qu'un graphe soit le bon objet mathématique pour un labyrinthe... quelqu'un pourrait-il par exemple me montrer quel graphe est associé au schéma de soland (nœuds et arrêtes)?

Dans tous les cas je pense qu'il faudrait préciser l'énoncé en termes mathématiques, mais je n'ai aucune idée... quelqu'un aurait-il une idée d'une définition mathématique d'un graphe, et de la notion d'entrée?

bisam · April 2021

A chaque labyrinthe, tu peux associer un graphe en faisant de chaque "pièce" un noeud et de chaque "porte" une arête.
Pour finir, tu ajoutes un noeud pour l'extérieur du labyrinthe.

Donc, pour le dessin de soland, tu obtiens un graphe à 3 noeuds (les deux pièces Gauche, Droite et l'Extérieur) et deux arêtes (G-E et D-E).

christophe c · April 2021

mais pourriez-vous préciser un peu plus votre raisonnement?

Pour accepter ce que te dit MrJ, il suffit de mettre un ordre sur les voisins (on visite le 1, puis le 2, ..) et ce pour chaque sommet.

MrJ · April 2021

Désolé, j'avais oublié ce fil.

Je pense que ce que j'ai dit est juste, mais j'avoue que je pensais à un gentil labyrinthe quand j'ai posté mon premier message (comme celui-là par exemple).

Si tu pars d'un labyrinthe "quelconque" (mais formellement, comment le définir ?), je pense que passer totalement rigoureusement de la vision géométrique à l'approche avec un graphe est plutôt difficile. Après pour les labyrinthes "classiques", çà se voit assez facilement, au moins de manière intuitive. 126242

gerard0 · April 2021

Bonjour.

Une heuristique :
A partir de l'entrée, tu traces au milieu du couloir un trait, en rajoutant des traits liés pour chaque nouveau couloir, jusqu'à avoir rempli la partie accessible du labyrinthe (il peut y avoir des parties fermées). Tu as obtenu le tracé des chemins possibles (TCP). En négligeant les parties inaccessibles, la situation géométrique (topographique) est celle-ci : le labyrinthe est un ensemble de murs situés (en gros) à une demi largeur de couloir du TCP. En suivant le mur à main droite, tu te places à gauche du TCP (dans le sens de ta progression). Si tu reviens à un endroit où tu es déjà passé, tu es dans le sens contraire, donc tu es de l'autre côté du TCP, tu ne boucles pas. La longueur de murs étant finie, au bout d'un certain temps (ou souvent un temps certain !) tu auras fait au plus le double de la longueur des murs et tu ressortiras; par l'entrée (Pas de sortie autre que l'entrée, cas de Thésée) ou une sortie.

Cette heuristique coince si la sortie est dans une partie dont on fait le tour : On sort par un niveau inférieur ou supérieur. Elle ne fonctionne qu'avec un labyrinthe plan.

Cordialement.

AlainLyon · August 2021

adrien2019 a écrit:

http://www.les-mathematiques.net/phorum/read.php?34,2218796,2218990#msg-2218990 quelqu'un pourrait-il par exemple me montrer quel graphe est associé au schéma de soland (nœuds et arrêtes) ?

Deux nœuds disjoints $A$ et $B$ avec sur chaque nœud un arc réflexif.
Mais je pense que c'est une erreur de considérer la notion topologique de graphe qui est trop générale. Par analogie, topologiquement un cerveau est une sphère, mais la médecine peut s'intéresser aux plis de la membrane externe qui donnent un réseau de sillons et ce n'est pas facile de définir mathématiquement une surface plissée avec un réseau de sillons.
À mon humble avis il faut utiliser des notions plus métriques que topologiques comme tente de le faire gerard0 parce que topologiquement un labyrinthe de foire c'est peu ou prou un nœud pour l'entrée un pour la sortie et un arc de l'entrée à la sortie, alors que nous en percevons des couloirs avec des changements de direction.

Fuegocello · August 2021

Bonsoir.

Je lance une idée, d’avance pardon, car très incomplète.

-Modéliser le labyrinthe comme une matrice de quadruplés (n,o,s,e) ou n,o,s et e représentent les bords ouverts (0) ou fermés du labyrinthe. En particulier ces bords pour les éléments du bord de la matrice valent tous 1, sauf en pour deux cas.

-Définir convenablement qu’un labyrinthe est soluble (il existe un « bon » chemin qui relie l’entrée et la sortie)

-Finir la démonstration…!

AlainLyon · August 2021

Fuegocello
Les bords ouverts ou fermés d'un labyrinthe ?
Prends le dessin de MrJ : où sont les bords ?

[Inutile de reproduire le message précédent. AD]

AlainLyon · August 2021

A mon avis la solution n'est pas du domaine des mathématiques mais de l'informatique ( réseaux de neurones) à la manière dont procède le blob pour trouver son chemin dans un labyrinthe.

[Utilisateur supprimé] · August 2021

Je me permets de mentionner des versions numériques très sympathiques dans le cas où l'on a maillé le labyrinthe, et où l'on a déjà identifié la sortie et l'entrée (je ne parle pas de solutions optimales, simplement très jolies): on peut chercher les plus courts chemins, par exemple en regardant la propagation de fronts d'onde (fast-marching) ou bien en calculant des laplaciens (on approche des distances géodésiques par une équation de la chaleur, si j'ai bien compris, cf ce papier).

J'ai découvert tout cela en lisant un thread twitter, auquel répond notamment un chercheur que j'aime beaucoup et qui partage énormément de petites pratiques numériques (Gabriel Peyré). Voilà, je pense que ça peut être rigolo de savoir que ça existe, quand bien même ce ne sont absolument pas des solutions optimales pour plein de raisons ! 126244

AlainLyon · August 2021

Va pour une EDP avec des conditions de Dirichlet mais il faut trouver des solutions approchées à cette équation en maillant le labyrinthe et comment va s'y prendre un mailleur (le programme qui calcule les mailles pour du calcul scientifique avec des éléments ou des différences finies) pour trouver automatiquement les contours du labyrinthe. C'est à mon avis là que peuvent se nicher
des réseaux de neurones. Le sujet me parait donc idéal pour un travail à l'INRIA.

(à propos du blob : c'est un être unicellulaire -une cellule géante- très ancien dans l'évolution qui ressemble à du lichen jaune et dont on ne sait pas si c'est un champignon, une plante ou une bactérie (un peu des trois) il n'a pas de cerveau et pas de noyau avec des gènes, mais.Il "sait" se déplacer pour trouver son alimentation. Les chercheurs en biologie ont même prouvé que c'est un génie de l'alimentation puisqu'il "sait" trouver son chemin à travers un labyrinthe pour trouver la nourriture qui lui convient quand on la place à la sortie et le blob à l'entrée).

[Utilisateur supprimé] · August 2021

Je ne suis pas certain de comprendre la nécessité d'utiliser du deep learning, ni pour mailler, ni pour approcher les solutions sur un maillage. Mais c'est un point de vue très général sur la sur-exposition relativement "récente" de ces techniques appliquées à tous les domaines, c'est donc mon simple avis (je sais qu'on espère y gagner en temps / en coût de calcul).

Non, mon propos était simplement de montrer ces solutions, versions continues de problèmes discrets, que personnellement je trouve belles.

PS: Je suis en fait presque certain que tous les papiers de réseaux de neurones qui s'intéressent à ces problèmes le font en mimant au plus proche les techniques des résolutions existantes ou heuristiques s'en approchant (laplaciens et différences finies, solutions d'équations différentielles type eikonales, etc ...).