Алгоритм решения лабиринта

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

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

Алгоритм случайной мыши

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

Правило «рука на стене»

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

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

Другая точка зрения на то, почему работает следование вдоль стен, — топологическая. Если стены соединены, то они могут деформироваться в петлю или круг. ^[3] Тогда следование вдоль стен сводится к обходу круга от начала до конца. Чтобы развить эту идею, обратите внимание, что при группировке связанных компонентов стен лабиринта границы между ними являются именно решениями, даже если существует более одного решения.

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

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

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

Моделирование работы этого алгоритма можно найти здесь.

Алгоритм залога

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

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

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

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

Алгоритм Тремо

Алгоритм Тремо , изобретенный Шарлем Пьером Тремо ^[6], является эффективным методом поиска выхода из лабиринта, требующим рисования линий на полу для обозначения пути, и гарантированно работает для всех лабиринтов с четко определенными проходами ^[7], но он не гарантирует нахождения кратчайшего маршрута.

Вход в проход либо не посещается, либо отмечен один раз или отмечен дважды. Обратите внимание, что маркировка входа не то же самое, что маркировка перекрестка или прохода, потому что перекресток может иметь несколько входов, а проход имеет вход с обоих концов. Тупики можно рассматривать как перекрестки с одним входом (представьте, что в каждом тупике есть комната).

Алгоритм работает по следующим правилам:

Всякий раз, когда вы проходите через вход в проход, независимо от того, въезжаете ли вы на перекресток или выезжаете с него, оставляйте отметку у входа, когда вы проходите.
Находясь на перекрестке, используйте первое применимое правило ниже, чтобы выбрать въезд для выезда:
1. Если отмечен только тот вход, из которого вы только что пришли, выберите произвольный неотмеченный вход, если таковой имеется. Это правило также применимо, если вы только начинаете с середины лабиринта и нет отмеченных входов вообще.
2. Выберите вход, из которого вы только что пришли, если он не отмечен дважды. Это правило будет применяться всякий раз, когда вы достигнете тупика.
3. Выберите любой вход с наименьшим количеством баллов (если возможно, ноль, в противном случае один).

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

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

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

Заполнение тупика

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

найдите все тупики в лабиринте, а затем
«заполните» путь от каждого тупика до первого перекрестка.

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

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

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

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

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

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

Алгоритм маршрутизации лабиринта

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

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

Point src , dst ; // Координаты источника и назначения // cur также указывает координаты текущего местоположения int MD_best = MD ( src , dst ); // Он хранит ближайший MD, который у нас когда-либо был к dst // Продуктивный путь — это тот, который делает наше MD к dst меньше while ( cur ! = dst ) { if ( there exist a produce path ) { Выбираем продуктивный путь ; } else { MD_best = MD ( cur , dst ) ; Представьте себе линию между cur и dst ; Выбираем первый путь слева / справа от линии ; // Выбор слева / справа влияет на следующее правило руки while ( MD ( cur , dst ) ! = MD_best || продуктивного пути не существует ) { Следуем правилу справа / слева ; // Противоположность выбранной стороне линии } }

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

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

Многоагентное решение лабиринта

Коллективное исследование относится к исследованию неизвестной среды несколькими мобильными агентами, которые движутся с одинаковой скоростью. Эта модель была введена для изучения параллелизуемости решения лабиринтов, ^[12] особенно в случае деревьев . Исследование зависит от модели коммуникации между агентами. В централизованной модели коммуникации агентам разрешено общаться друг с другом в любое время. В распределенной модели коммуникации агенты могут общаться только путем чтения и записи на стенах лабиринта. Для деревьев с узлами и глубиной , с роботами, лучшим на данный момент алгоритмом является в централизованной модели коммуникации и в в распределенной модели коммуникации. ^[12] $n$ $D$ $к$ $O\left({\frac {n}{k}}+kD\right)$ $O\left({\frac {n}{\log k}}+D\right)$

Смотрите также

Ссылки

^ Лабиринт к дереву на YouTube
^ Алелиунас, Ромас; Карп, Ричард М; Липтон, Ричард Дж; Ловас, Ласло; Ракофф, Чарльз (1979). «Случайные блуждания, универсальные последовательности обхода и сложность задач лабиринта». 20-й ежегодный симпозиум по основам компьютерной науки (sfcs 1979) . IEEE Computer Society. стр. 218–223.
^ Maze Transformed на YouTube
^ Абельсон; диСесса (1980), Геометрия черепахи: компьютер как средство для исследования математики, MIT Press, ISBN 9780262510370
↑ Сеймур Паперт, «Использование технологий для улучшения образования», Меморандум по искусственному интеллекту Массачусетского технологического института № 298 , июнь 1973 г.
↑ Публичная конференция, 2 декабря 2010 г. – профессор Жан Пеллетье-Тибер в Академии Макона (Бургундия – Франция) – (Реферат опубликован в Annals academic, март 2011 г. – ISSN 0980-6032) Шарль Тремо (° 1859 – † 1882) Парижская политехническая школа (X:1876), французский инженер телеграфа
^ Эдуард Лукас: Récréations Mathématiques, том I, 1882.
^ Х. Флейшнер: Эйлеровы графы и связанные с ними темы. В: Annals of Discrete Mathematics № 50 Часть 1 Том 2, 1991, стр. X20.
^ Эвен, Шимон (2011), Графовые алгоритмы (2-е изд.), Cambridge University Press, стр. 46–48, ISBN 978-0-521-73653-4.
^ Седжвик, Роберт (2002), Алгоритмы в C++: Графовые алгоритмы (3-е изд.), Pearson Education, ISBN 978-0-201-36118-6.
^ Фаттах, Мохаммад и др. (28.09.2015). «Малозатратный, полностью распределенный, гарантированно доставляемый алгоритм маршрутизации для неисправных сетей на кристаллах». Труды 9-го Международного симпозиума по сетям на кристаллах . Nocs '15. стр. 1–8. doi :10.1145/2786572.2786591. ISBN 9781450333962. S2CID 17741498.
^ аб Фрагнио, Пьер; Гасенец, Лешек; Ковальский, Дариуш Р; Пелц, Анджей (2006). «Коллективное исследование деревьев». Сети . 48 (3). Интернет-библиотека Wiley: 166–177. дои : 10.1002/net.20127.

Внешние ссылки

Think Labyrinth: алгоритмы лабиринтов (подробности об этих и других алгоритмах решения лабиринтов)
MazeBlog: Решение лабиринтов с помощью анализа изображений
Видео: Моделирование решения лабиринта