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

17

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

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

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

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

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

Ник Алджер
источник
После прочтения FAQ я не верю, что это принадлежит. Вероятно, это не теоретический вопрос информатики на уровне научных исследований. Извините, что опубликовал в неправильном месте. Может ли кто-нибудь порекомендовать подходящий форум, чтобы задать этот вопрос и / или перенести его туда?
Ник Алджер
Я подумывал о публикации на math.stackexchange, так как я там участвую, но мне показалось, что это слишком сложно. Я не знал, что есть обмен стека информатики. Если модераторы захотят перенести его в одно из тех мест, я бы не возражал.
Ник Алджер
3
Для меня не очевидно, что это не по теме ... очевидно, вопросы не по теме обычно получают больше отрицательных голосов, чем положительных
Джо
7
Разве вы не можете представить какой-либо фрактальный лабиринт как автомат с выталкиванием, где стек соответствует последовательности субмаз, в которых вы находитесь? Тогда вопрос о растворимости превратится в проблему пустоты для контекстно-свободных языков, которая разрешима.
Питер Шор

Ответы:

8

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

  • Предположим , что существует входов / выходов I 1 , . , ,n ;I1,...In
  • построить график , где каждый я я , то М Я Н 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 IGIiMINUSPLUSMjKnIi,MINUS,PLUS,MjIk ребер, отличных от соответствующих «внутренних» реберIiIkвMjкак полный подграф;MjIiMjIkIiIkMj
  • перечислить все пути от МИНУС до ПЛЮС в (избегая циклов);G
  • если вы найдете путь, который не пересекает вложенную копию, то это решение; в противном случае разверните каждый «внутренний» обход вложенных лабиринтов каждого пути:Mj

Предположим, что путь в первом перечислении имеет вид , тогда путь является правильным решением, если существует путь из I iI j и от I kI h в исходном лабиринте (графикMINUSAIiAIjBIkBIhPLUSIiIjIkIh ).G

Таким образом , мы должны расширить на и B I KB I ч обходов перечисляющих все пути от I я до I K и от I K до I ч в G .AIiAIjBIkBIhIiIkIkIhG

Бесконечные циклы обнаруживаются, когда мы перечисляем все пути от до I k в расширении пути, который на предыдущем этапе уже содержался . , , M I iM I k. , , для некоторого подмаза M (есть только n 2 возможных расширений).IiIk...MIiMIk...Mn2

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

Марцио де Биаси
источник
Вот это да! Какая умная идея. Я думаю, что это работает, но это все еще немного нечетко, так что я собираюсь потратить немного времени, чтобы обдумать это, прежде чем принять.
Ник Алджер
Хорошо, да, я уверен, что этот алгоритм правильный. Принимая во внимание приведенный выше комментарий Питера Шора, я хотел бы знать, не могли бы вы изменить это, чтобы предоставить доказательство проблемы разрешаемости пустотности, не связанной с контекстом? ..? Для заданной проблемы пустоты языка без контекста создайте эквивалентный фрактальный лабиринт, а затем примените этот алгоритм.
Ник Алджер
@Nick: фрактальный лабиринт соответствует обратимому автомату, в котором вы можете сделать переход из состояния S в состояние T, вы также можете сделать переход из T в S. Это должно быть просто показать, что фрактальные лабиринты фактически эквивалентен обратимым автоматам. Существует теорема о том, что (с точностью до полинома) реверсивные машины Тьюринга имеют ту же мощность, что и обычные машины Тьюринга. Я не знаю, смотрел ли кто-нибудь ранее на обратимые автоматы, и я не знаю, известно ли о них что-нибудь.
Питер Шор
@Peter: Я нашел этот Реверсивные Автоматы Пушдауна , но определение "реверсивный" кажется другим. (PS поздравляю за простую и понятную интерпретацию фрактального лабиринта как КПК !!!)
Марцио Де Биаси
1
Приведенный выше алгоритм может быть распространен на ориентированные графы (необратимые фрактальные лабиринты), вам нужно просто рассмотреть возможных расширений ( I kI j и I jI k ). 2n2IkIj IjIk
Ник Алджер
1

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

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

Определение: лабиринт представляет собой компактное подмножество плоскости М R 2 , содержащий начальную точку и конечную точку с , е М , соответственно. Решение является непрерывной функцией F : [ 0 , T ] M такая , что F ( 0 ) = s и е ( Т ) = е .MMR2s,eMf:[0,T]Mf(0)=sf(T)=e

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

Гифка кривой Гильберта из Википедии

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

P

P=APA1BPB1CPC1DPD1

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

введите описание изображения здесь

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

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

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

Ник Алджер
источник
Наивный комментарий: «субмазы» кривой Гильберта меньше, поэтому в «непрерывном мире» это работает; в «дискретном мире» вы никогда не сделаете «выход», потому что продолжаете вводить первый субмаз (как бесконечный зум в нижнем левом углу кривой Гильберта). Это напоминает парадоксы Зенона
Марцио Де Биаси
2
PS Я думаю, что нет необходимости в фрактальной кривой: простая горизонтальная линия от s до f с одним центральным подмазы (которая имеет одну горизонтальную линию с суб-субмазиной и т. Д.) Приводит к тем же соображениям.
Марцио Де Биаси,
Хорошая точка зрения. Если вы сделаете это с вложенной коробкой шириной 1/2, расположенной справа, это не просто парадокс Зенона, вы получите именно парадокс Зенона. После дальнейшего рассмотрения кажется, что непрерывное определение не очень подходит для фрактальных лабиринтов, так как делает практически каждый фрактальный лабиринт разрешимым.
Ник Алджер
но он хорошо подходит для медитации в дзен-лабиринте (Google ищет разницу между лабиринтом и лабиринтом в контексте медитации) :-)
Марцио Де Биаси