Décidabilité du labyrinthe fractal

Un labyrinthe fractal est un labyrinthe qui contient des copies de lui-même. Par exemple, le suivant par Mark JP Wolf de cet article :

Commencez au MOINS et dirigez-vous vers le PLUS. Lorsque vous entrez dans une petite copie du labyrinthe, assurez-vous d'enregistrer le nom de la lettre de cette copie, car vous devrez laisser cette copie à la sortie. Vous devez sortir de chaque copie imbriquée du labyrinthe dans lequel vous êtes entré, en laissant dans l'ordre inverse dans lequel vous les avez entrés (par exemple: entrez A, entrez B, entrez C, quittez C, quittez B, quittez A). Considérez-le comme une série de boîtes imbriquées. S'il n'y a pas de chemin de sortie quittant la copie imbriquée, vous avez atteint une impasse. De la couleur a été ajoutée pour rendre les voies plus claires, mais elle n'est que décorative.

Si une solution existe, la recherche en premier lieu devrait trouver une solution. Cependant, supposons qu'il n'y ait pas de solution au labyrinthe - alors notre programme de recherche fonctionnerait pour toujours de plus en plus profond.

Ma question est: étant donné un labyrinthe fractal, comment pouvons-nous déterminer s'il a une solution ou non?

Ou bien, pour un labyrinthe fractal d'une taille donnée (nombre d'entrées / sorties par copie), existe-t-il une limite sur la longueur de la solution la plus courte? (s'il y avait une telle limite, nous ne pourrions rechercher exaustivement que profondément)

Un algorithme informel rapide pour prouver que le problème est décidable:

• supposons qu'il y ait entrées / sorties I 1 , . . . I n ;$n$$I_1,...I_n$
• construire un graphe où chaque I i , les M I N U S et les P L U S sont des nœuds, et remplacer chaque labyrinthe imbriqué M j par un sous-graphe K n (graphe complet); ajouter les bords entre I i , M I N U S , P L U S , M j I k selon le labyrinthe; garder "externe" M j I i → M $G$$I_i$$MINUS$$PLUS$$Mj$$K_n$$I_i, MINUS, PLUS, Mj_{I_k}$ arêtes distinctes des arêtes "internes" correspondantesIi→IkdeMjcomme sous-graphe complet;$Mj_{I_i} \rightarrow Mj_{I_k}$$I_i \rightarrow I_k$$Mj$
• énumérer tous les chemins de MOINS à PLUS en (en évitant les cycles);$G$
• si vous trouvez un chemin qui ne traverse pas une copie imbriquée, alors c'est une solution; sinon élargir chaque parcours "interne" des labyrinthes imbriqués de chaque chemin:$Mj$

Supposons qu'un chemin dans la première énumération soit , alors le chemin est une solution valide si il y a un chemin de I i → I j et de I k → I h dans le labyrinthe d'origine (graphique G ).$MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$$I_i \rightarrow I_j$$I_k \rightarrow I_h$$G$

Nous devons donc développer l' et B I k → B I h traversals qui énumèrent tous les chemins de I i à I k et de I k à I h dans G .$A_{I_i} \rightarrow A_{I_j}$$B_{I_k} \rightarrow B_{I_h}$$I_i$$I_k$$I_k$$I_h$$G$

Des boucles infinies sont détectées lorsque nous énumérons tous les chemins de à I k dans une expansion d'un chemin qui, à une étape précédente, était déjà contenu . . . → M I i → M I k → . . . pour certains submaze M (il n'y a que n 2 extensions possibles).$I_i$$I_k$$... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$$M$$n^2$

Une solution est trouvée si nous trouvons une extension de chemin qui ne contient que des entrées / sorties ; le labyrinthe n'a pas de solution si nous ne pouvons pas élargir davantage les chemins sans boucles.$I_i$

Ce n'est pas une "réponse" à ma question, mais plutôt un commentaire étendu que les gens d'ici pourraient trouver intéressant.

Je prétends qu'il existe une définition naturelle "de type analyse" d'un labyrinthe et d'une solution, et qu'elle diffère de la définition informatique / graphique-théorique que nous avons utilisée ici. En particulier, vous pouvez avoir un labyrinthe fractal qui a une «solution» selon la définition de l'analyse, mais qui serait déclaré insoluble par l'algorithme de Marizio De Biasi et la technique d'automates à refoulement de Peter Shor.

Définition: Un labyrinthe est un sous - ensemble compact du plan M ⊂ R 2 contenant un point de départ et un point d'extrémité s , e ∈ M , respectivement. Une solution est une fonction continue f : [ 0 , T ] → M telle que f ( 0 ) = s et f ( T ) = e .$M$$M \subset \mathbb{R}^2$$s,e \in M$$f:[0,T] \rightarrow M$$f(0)=s$$f(T)=e$

Considérons maintenant la courbe de Hilbert :

On pourrait interpréter cette courbe comme un "labyrinthe fractal" avec le schéma suivant:

$P$

$P = APA^{-1}BPB^{-1}CPC^{-1}DPD^{-1}$

Maintenant, vous pourriez faire valoir que ce n'est pas dans l'esprit des labyrinthes fractals puisque la courbe de Hilbert remplit tout le carré et donc vous pouvez simplement dessiner un segment de ligne droite du début à la fin. Cependant, cette objection est facilement contournée - utilisez simplement le diagramme de courbe de Hilbert incorporant directement, comme indiqué ici:

Celui-ci contient également une séquence de chemins continus uniformément convergents allant du début à la fin, par le même argument utilisé pour montrer la convergence uniforme de la courbe de Hilbert. Mais c'est un véritable "labyrinthe fractal" dans le sens où il ne remplit pas tout l'espace.

Nous avons donc un labyrinthe fractal qui est résoluble par la définition analytique, mais insoluble par la définition théorique du graphe ..!?

Quoi qu'il en soit, je suis presque sûr que ma logique est correcte, mais cela semble contre-intuitif, donc si quelqu'un peut faire la lumière sur ce point, je l'apprécierais.