Из Википедии, бесплатной энциклопедии
  (Перенаправлено от приверженца стены )
Перейти к навигации Перейти к поиску
Робот в деревянном лабиринте

Существует ряд различных алгоритмов решения лабиринтов , то есть автоматизированных методов решения лабиринтов . Алгоритмы случайной мыши, следящего за стеной, залога и Тремо предназначены для использования внутри лабиринта путешественником, не имеющим предварительных знаний о лабиринте, тогда как алгоритмы тупикового заполнения и кратчайшего пути предназначены для использования человеком или компьютерная программа, которая может увидеть весь лабиринт сразу.

Лабиринты, не содержащие петель, известны как «односвязные» или «совершенные» лабиринты и эквивалентны дереву в теории графов. Таким образом, многие алгоритмы решения лабиринтов тесно связаны с теорией графов . Интуитивно понятно, что если правильно растянуть и растянуть дорожки в лабиринте, результат можно будет сделать похожим на дерево. [1]

Алгоритм случайной мыши [ править ]

Это тривиальный метод, который может быть реализован очень неразумным роботом или, возможно, мышью. Просто двигаться по текущему проходу до тех пор, пока не будет достигнут перекресток, а затем принять случайное решение о следующем направлении движения. Хотя такой метод в конечном итоге всегда найдет правильное решение , этот алгоритм может быть чрезвычайно медленным.

Последователь стены [ править ]

Обход с использованием правила правой руки

Самым известным правилом прохождения лабиринта является следование за стеной , также известное как правило левой или правой руки . Если лабиринт просто связан , то есть все его стены соединены вместе или с внешней границей лабиринта, то, удерживая одну руку в контакте с одной стенкой лабиринта, решатель гарантированно не заблудится и достигнет другого выхода. если есть; в противном случае алгоритм вернется к входу, пройдя каждый коридор рядом с этим соединенным участком стен хотя бы один раз. Алгоритм представляет собой обход дерева по порядку в глубину .

Еще одна точка зрения на то, почему работает отслеживание стены, - топологическая. Если стены соединить, то они могут деформироваться в петлю или круг. [2] Затем движение по стене сводится к хождению по кругу от начала до конца. Чтобы развить эту идею, обратите внимание, что при объединении связанных компонентов стенок лабиринта границы между ними и есть решения, даже если существует более одного решения (см. Рисунки справа).

Если лабиринт не является односвязным (т. Е. Если начальная или конечная точки находятся в центре конструкции, окруженной петлями прохода, или пути пересекаются и друг под другом, и такие части пути решения окружены петлями прохода), этот метод не достигнет цели.

Еще одна проблема заключается в том, чтобы начать движение по стене у входа в лабиринт. Если лабиринт не является односвязным и кто-то начинает следовать по стене в произвольной точке внутри лабиринта, он может оказаться в ловушке вдоль отдельной стены, которая петляет вокруг себя и не содержит входов или выходов. В случае, если следование за стеной начинается поздно, попытайтесь отметить позицию, в которой началось следование за стеной. Поскольку следование за стеной всегда приведет вас обратно к тому месту, где вы начали, если вы встретите начальную точку во второй раз, вы можете сделать вывод, что лабиринт не является простым, и вам следует переключиться на альтернативную стену, по которой вы еще не прошли. См. Альтернативную методологию в Алгоритме залога ниже.

Следование за стеной может быть выполнено в трехмерном лабиринте или лабиринте более высокого измерения, если его проходы более высокого измерения можно детерминированно спроецировать на двумерную плоскость. Например, если в трехмерном лабиринте можно предположить, что «верхние» проходы ведут на северо-запад, а «нижние» проходы - на юго-восток, тогда могут применяться стандартные правила следования стенам. Однако, в отличие от 2D, для этого требуется известная текущая ориентация, чтобы определить, какое направление будет первым слева или справа.

Алгоритм залога [ править ]

Слева: решатель с левым поворотом в ловушке
Справа: решение алгоритма залога

Непересекающиеся [ требуется пояснение ] лабиринты могут быть решены с помощью метода следования по стенам, если вход и выход в лабиринт находятся на внешних стенах лабиринта. Однако, если решающая программа запускается внутри лабиринта, она может быть на участке, не пересекающем выход, и сторонники стены будут постоянно ходить по своему кольцу. Алгоритм Pledge (названный в честь Джона Залога из Эксетера ) может решить эту проблему. [3] [4]

Алгоритм Pledge, разработанный для обхода препятствий, требует произвольно выбранного направления движения, которое будет предпочтительным. Когда встречается препятствие, одна рука (скажем, правая рука) удерживается вдоль препятствия, в то время как углы поворота подсчитываются (поворот по часовой стрелке положительный, поворот против часовой стрелки отрицательный). Когда решающая программа снова смотрит в исходное предпочтительное направление и угловая сумма сделанных поворотов равна 0, решающая программа покидает препятствие и продолжает движение в исходном направлении.

Рука снимается со стены только тогда, когда и «сумма сделанных поворотов», и «текущий курс» равны нулю. Это позволяет алгоритму избегать ловушек в виде буквы «G» в верхнем регистре. Предполагая, что алгоритм поворачивает налево у первой стены, стены поворачивают на полные 360 градусов . Алгоритм, который отслеживает только «текущий курс», ведет к бесконечному циклу, поскольку он покидает крайнюю правую нижнюю стену и снова попадает в изогнутую секцию с левой стороны. Алгоритм Pledge не покидает крайнюю правую стену из-за того, что «сумма сделанных поворотов» не равна нулю в этой точке (примечание 360 градусов не равно 0 градусам ). Он идет вдоль стены, наконец, оставив его заголовок слева снаружи и прямо под формой буквы.

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

Алгоритм Тремо [ править ]

Алгоритм Тремо. Большая зеленая точка показывает текущее положение, маленькие синие точки показывают одиночные отметки на путях, а красные кресты показывают двойные отметки. Как только выход будет найден, маршрут будет проходить по размеченным дорожкам.

Алгоритм Trémaux, в изобретен Чарльз Пирр Тремо , [5] является эффективным способом , чтобы найти выход из лабиринта , который требует рисования линий на полу , чтобы пометить путь, и гарантированно работать для всех лабиринтов , которые имеют четко определенные места , [6], но найти кратчайший маршрут не гарантируется.

Путь от перекрестка либо не посещается, либо отмечается один раз, либо дважды. Алгоритм работает по следующим правилам:

  • Отметьте каждый путь один раз, когда будете следовать по нему. Отметки должны быть видны на обоих концах пути. Следовательно, если они делаются как физические отметки, а не хранятся как часть компьютерного алгоритма, одинаковые отметки должны быть сделаны на обоих концах пути.
  • Никогда не входите на тропу, на которой есть две отметки.
  • Если вы дойдете до перекрестка, на котором нет отметок (кроме, возможно, той на пути, по которому вы вошли), выберите произвольный немаркированный путь, следуйте по нему и отметьте его.
  • Иначе:
    • Если на пути, по которому вы пришли, есть только одна отметка, развернитесь и вернитесь по этому пути, отметив его снова. В частности, этот случай должен происходить всякий раз, когда вы заходите в тупик.
    • Если нет, выберите произвольно один из оставшихся путей с наименьшим количеством отметок (ноль, если возможно, иначе один), следуйте по этому пути и отметьте его.

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

Когда вы, наконец, достигнете решения, пути, отмеченные ровно один раз, укажут путь назад к началу. Если выхода нет, этот метод вернет вас к началу, где все пути отмечены дважды. В этом случае каждый путь проходит ровно дважды, по одному разу в каждом направлении. Результирующий обход называется двунаправленной двойной трассировкой. [7]

По сути, этот алгоритм, который был открыт в 19 веке, использовался примерно сто лет спустя как поиск в глубину . [8] [9]

Тупиковая засыпка [ править ]

Заполнение тупика - это алгоритм решения лабиринтов, который заполняет все тупики, оставляя незаполненными только правильные пути. Его можно использовать для решения лабиринтов на бумаге или с помощью компьютерной программы, но он бесполезен для человека внутри неизвестного лабиринта, поскольку этот метод рассматривает весь лабиринт сразу. Метод состоит в том, чтобы 1) найти все тупики в лабиринте, а затем 2) "заполнить" путь от каждого тупика до первого пересечения. Обратите внимание, что некоторые проходы не станут частью тупиковых переходов, пока сначала не будут удалены другие тупики. Видео с заполнением тупика в действии можно посмотреть здесь: [1] [2] .

Заполнение тупика не может случайно «отрезать» начало от финиша, так как на каждом этапе процесса сохраняется топология лабиринта. Кроме того, процесс не остановится «слишком рано», поскольку конечный результат не может содержать тупиков. Таким образом, если тупиковое заполнение выполняется в идеальном лабиринте (лабиринте без петель), то останется только решение. Если это сделать в частично заплетенном лабиринте (лабиринте с несколькими петлями), то останутся все возможные решения, но не более того. [3]

Рекурсивный алгоритм [ править ]

Если дать всеведущий вид лабиринта, простой рекурсивный алгоритм может сказать, как добраться до конца. Алгоритму будут присвоены начальные значения X и Y. Если значения X и Y не указаны на стене, метод вызовет себя со всеми соседними значениями X и Y, убедившись, что он еще не использовал эти значения X и Y раньше. Если значения X и Y соответствуют конечному местоположению, он сохранит все предыдущие экземпляры метода как правильный путь.

По сути, это поиск в глубину, выраженный в точках сетки. Всезнающий вид предотвращает ввод циклов посредством запоминания. Вот пример кода на Java :

логический [] []  лабиринт  =  новый  логический [ ширина ] [ высота ] ;  // Лабиринт логический [] []  wasHere  =  новый  логический [ ширина ] [ высота ] ; логический [] []  правильный путь  =  новый  логический [ ширина ] [ высота ] ;  // Решение лабиринта int  startX ,  startY ;  // Начальные значения X и Y лабиринта int  endX , endY ;  // Завершение значений X и Y лабиринтаобщедоступный  void  resolveMaze ()  {  лабиринт  =  generateMaze ();  // Создание лабиринта (false = path, true = wall)  for  ( int  row  =  0 ;  row  <  maze . Length ;  row ++ )  // Устанавливает логические массивы в значения по умолчанию  для  ( int  col  =  0 ;  col  <  maze [ row ] . length ;  col ++ ) {  wasHere [ row] [ col ]  =  ложь ;  correctPath [ строка ] [ столбец ]  =  ложь ;  }  логическое  b  =  recursiveSolve ( startX ,  startY );  // Оставит вас с логическим массивом (correPath)  // с путем, указанным истинными значениями.  // Если b ложно, решения лабиринта нет } public  boolean  recursiveSolve ( int  x ,  int  y )  {  if  ( x  == endX  &&  y  ==  endY )  return  true ;  // Если вы дошли до конца  if  ( maze [ x ] [ y ]  ||  wasHere [ x ] [ y ] )  return  false ;  // Если вы  стоите на стене или уже были здесь wasHere [ x ] [ y ]  =  true ;  if  ( x  ! =  0 )  // Проверяет, нет ли на левом краю  if  ( recursiveSolve (x - 1 ,  y ))  {  // Вызов первого метода слева  rightPath [ x ] [ y ]  =  true ;  // Устанавливает для этого пути значение true;  вернуть  истину ;  }  if  ( x  ! =  width  -  1 )  // Проверяет, находится ли он не на правом краю  if  ( recursiveSolve ( x + 1 ,  y ))  {  // Вызывает метод, первый справа  rightPath [ x ] [ y]  =  правда ;  вернуть  истину ;  }  if  ( y  ! =  0 )  // Проверяет, не находится ли он на верхнем краю  if  ( recursiveSolve ( x ,  y - 1 ))  {  // Вызывает метод один вверх  correPath [ x ] [ y ]  =  true ;  вернуть  истину ;  }  if  ( y  ! =  height  -  1 )  // Проверяет, не по нижнему краю  if  (recursiveSolve ( x ,  y + 1 ))  {  // Вызывает метод с первого по  нижнему значению rightPath [ x ] [ y ]  =  true ;  вернуть  истину ;  }  return  false ; }

Алгоритм лабиринта [ править ]

Алгоритм маршрутизации лабиринта [10] - это метод с низкими накладными расходами, позволяющий найти путь между любыми двумя точками лабиринта. Алгоритм изначально предлагается для области многопроцессорных чипов (CMP) и гарантирует работу для любого лабиринта на основе сетки. Помимо поиска путей между двумя точками сетки (лабиринта), алгоритм может обнаруживать отсутствие пути между источником и местом назначения. Кроме того, алгоритм должен использоваться внутренним путешественником, не имеющим предварительных знаний о лабиринте с фиксированной сложностью памяти, независимо от размера лабиринта; требуется всего 4 переменных для поиска пути и обнаружения недоступных мест. Тем не менее алгоритм не заключается в нахождении кратчайшего пути.

Алгоритм маршрутизации лабиринта использует понятие манхэттенского расстояния (MD) и полагается на свойство сеток, что MD увеличивается / уменьшается точно на 1 при перемещении из одного местоположения в любые 4 соседних местоположения. Вот псевдокод без возможности обнаружения недоступных мест.

Point  src ,  dst ; // Исходные и конечные координаты // cur также указывает координаты текущего местоположения int  MD_best  =  MD ( src ,  dst ); // Он хранит ближайший MD мы когда - либо приходилось целевой_адрес // Продуктивный путь тот , который делает нашу MD к Dst меньше то время как  ( CUR  =!  ДСТ )  {  если  ( там  существует  более  продуктивный  путь )  {  Возьмите  на  продуктивный  путь ;  }  еще {  MD_best  =  MD ( cur ,  dst );  Представьте  себе  линию  между  cur  и  dst ;  Возьмите  на  первый  путь  в  на  левом / правом  на  на  линии ;  // Левый / правый выбор влияет на следующее правило руки в  то время как  ( MD ( дворняжка ,  ДСТ )  ! =  MD_best  ||  там  же  не  существует  в  продуктивный  путь)  {  Следуйте  за  право - рука / влево - рука  правила ;  // Сторона, противоположная выбранной стороне линии  } }

Алгоритм кратчайшего пути [ править ]

Лабиринт с множеством решений и без тупиков, где может быть полезно найти кратчайший путь

Когда в лабиринте есть несколько решений, решатель может захотеть найти кратчайший путь от начала до конца. Существует несколько алгоритмов поиска кратчайших путей, большинство из которых основаны на теории графов . Один такой алгоритм находит кратчайший путь путем реализации поиска в ширину , а другой, алгоритм A * , использует эвристический метод. Алгоритм поиска в ширину использует очередьпосещать ячейки в порядке увеличения расстояния от начала до финиша. Каждая посещенная ячейка должна отслеживать свое расстояние от начала или то, какая соседняя ячейка ближе к началу вызвала ее добавление в очередь. Когда место финиша найдено, следуйте по пути ячеек назад к началу, который является кратчайшим путем. Поиск в ширину в своей простейшей форме имеет свои ограничения, такие как поиск кратчайшего пути в взвешенных графах.

См. Также [ править ]

  • Лабиринты
  • Алгоритм создания лабиринта

Ссылки [ править ]

  1. ^ Лабиринт к дереву на YouTube
  2. ^ Преобразование лабиринта на YouTube
  3. ^ Абельсон; diSessa (1980), Геометрия черепахи: компьютер как среда для изучения математики , ISBN 9780262510370
  4. ^ Сеймур Пейперт, «Использование технологий для улучшения образования» , MIT Artificial Intelligence Memo No. 298 , июнь 1973
  5. ^ Общественная конференция, 2 декабря 2010 - профессор Жан Пельтье-Thibert в Academie де Макон (Бургундия - Франция) - (Тезисы опубликованы в Annals академическими, март 2011 - ISSN 0980-6032 )Чарльз Tremaux (° 1859 - † 1882) Политехническая школа Парижа (X: 1876 г.), французский инженер телеграфа. 
  6. ^ Эдуард Лукас: Récréations Mathématiques Том I, 1882.
  7. ^ Even, Shimon (2011), Graph Algorithms (2-е изд.), Cambridge University Press, стр. 46–48, ISBN 978-0-521-73653-4.
  8. ^ Седжвик, Роберт (2002), Алгоритмы в C ++: Graph Algorithms (3-е изд.), Pearson Education, ISBN 978-0-201-36118-6.
  9. ^ Фаттах, Мохаммед; и другие. (2015-09-28). «Алгоритм маршрутизации с низкими накладными расходами, полностью распределенной и гарантированной доставкой для неисправной сети на кристалле» . NOCS '15 Материалы 9-го Международного симпозиума по сетям на кристалле : 1–8. DOI : 10.1145 / 2786572.2786591 . ISBN 9781450333962. S2CID  17741498 .

Внешние ссылки [ править ]

  • Думайте Лабиринт: алгоритмы лабиринта (подробности об этих и других алгоритмах решения лабиринта)
  • MazeBlog: решение лабиринтов с помощью анализа изображений
  • Видео: моделирование решения лабиринта
  • Саймон Айринхак, Электрический ток решает лабиринты , © 2014 IOP Publishing Ltd.