Разрешимость фрактального лабиринта

Фрактальный лабиринт - это лабиринт, который содержит копии самого себя. Например, следующий от Mark JP Wolf из этой статьи :

Начните с МИНУС и пройдите в ПЛЮС. Когда вы вводите уменьшенную копию лабиринта, обязательно запишите название буквы этой копии, так как вам придется оставить эту копию на выходе. Вы должны выйти из каждой вложенной копии лабиринта, в который вы вошли, оставив в обратном порядке, в котором вы их ввели (например: введите A, введите B, введите C, выход C, выход B, выход A). Думайте об этом как о серии вложенных блоков. Если нет выходного пути, оставляющего вложенную копию, вы попали в тупик. Цвет был добавлен, чтобы сделать дорожки более четкими, но он только декоративный.

Если решение существует, поиск в ширину должен найти решение. Однако, предположим, что в лабиринте нет решения - тогда наша программа поиска будет работать все глубже и глубже.

Мой вопрос: учитывая фрактальный лабиринт, как мы можем определить, есть ли у него решение или нет?

Или, в качестве альтернативы, для фрактального лабиринта заданного размера (количества входов / выходов на копию) существует ли предел длины кратчайшего решения? (если бы была такая граница, мы могли бы искать только этот глубокий поиск)

Быстрый неформальный алгоритм, чтобы доказать, что проблема разрешима:

• Предположим , что существует входов / выходов I 1 , . , $n$ ;$I_1,...I_n$
• построить график , где каждый я я , то М Я Н U S и P L U S является узлами, и заменить каждый вложенный лабиринт M J с K п подграфа (полный граф); добавить ребра между I i , M I N U S , P L U S , M j I k в соответствии с лабиринтом; сохранить "внешний" M J I $G$$I_i$$MINUS$$PLUS$$Mj$$K_n$$I_i, MINUS, PLUS, Mj_{I_k}$ ребер, отличных от соответствующих «внутренних» реберIi→IkвMjкак полный подграф;$Mj_{I_i} \rightarrow Mj_{I_k}$$I_i \rightarrow I_k$$Mj$
• перечислить все пути от МИНУС до ПЛЮС в (избегая циклов);$G$
• если вы найдете путь, который не пересекает вложенную копию, то это решение; в противном случае разверните каждый «внутренний» обход вложенных лабиринтов каждого пути:$Mj$

Предположим, что путь в первом перечислении имеет вид , тогда путь является правильным решением, если существует путь из I i → I j и от I k → I h в исходном лабиринте (график$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$

Таким образом , мы должны расширить на и B I K → B I ч обходов перечисляющих все пути от I я до I K и от I K до I ч в G .$A_{I_i} \rightarrow A_{I_j}$$B_{I_k} \rightarrow B_{I_h}$$I_i$$I_k$$I_k$$I_h$$G$

Бесконечные циклы обнаруживаются, когда мы перечисляем все пути от до I k в расширении пути, который на предыдущем этапе уже содержался . , , → M I i → M I k → . , , для некоторого подмаза M (есть только n 2 возможных расширений).$I_i$$I_k$$... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$$M$$n^2$

Решение будет найдено, если мы найдем расширение пути, которое содержит только входы / выходы ; лабиринт не имеет решения, если мы не сможем расширить пути без петель.$I_i$

Это не «ответ» на мой вопрос, а скорее расширенный комментарий, который люди здесь могут найти интересным.

Я утверждаю, что существует естественное определение типа анализа и лабиринта и решения, и оно отличается от определения информатики / теории теорий графов, которое мы использовали здесь. В частности, у вас может быть фрактальный лабиринт, который имеет «решение» согласно определению анализа, но будет объявлен неразрешимым алгоритмом Маризио Де Биаси и техникой автоматов Питера Шора.

Определение: лабиринт представляет собой компактное подмножество плоскости М ⊂ R 2 , содержащий начальную точку и конечную точку с , е ∈ М , соответственно. Решение является непрерывной функцией F : [ 0 , T ] → M такая , что F ( 0 ) = s и е ( Т ) = е .$M$$M \subset \mathbb{R}^2$$s,e \in M$$f:[0,T] \rightarrow M$$f(0)=s$$f(T)=e$

Теперь рассмотрим кривую Гильберта :

Эту кривую можно интерпретировать как «фрактальный лабиринт» со следующей диаграммой:

$P$

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

Теперь вы можете утверждать, что это не в духе фрактальных лабиринтов, поскольку кривая Гильберта заполняет весь квадрат, и поэтому вы можете просто нарисовать отрезок прямой линии от начала до конца. Это возражение легко может быть отменено - просто используйте прямое вложение диаграммы Гильберта, как показано здесь:

Это также содержит последовательность равномерно сходящихся непрерывных путей, идущих от начала до конца, по тому же аргументу, который используется для демонстрации равномерной сходимости кривой Гильберта. Однако это настоящий «фрактальный лабиринт» в том смысле, что он не заполняет все пространство.

Таким образом, у нас есть фрактальный лабиринт, который разрешается аналитическим определением, но не решается теоретическим определением графа ..!?

В любом случае, я почти уверен, что моя логика верна, но это кажется нелогичным, поэтому, если кто-то сможет пролить свет на это, я был бы признателен.