Алгоритм решения лабиринта - Maze solving algorithm

Робот в деревянном лабиринте

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

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

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

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

Последователь стены

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тупиковая заливка

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

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

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

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

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

логический[][] лабиринт = новый логический[ширина][высота]; // Лабиринтлогический[][] был здесь = новый логический[ширина][высота];логический[][] rightPath = новый логический[ширина][высота]; // Решение лабиринтаint startX, начало; // Запуск значений X и Y лабиринтаint конецX, конецY;     // Завершение значений X и Y лабиринтаобщественный пустота решить лабиринт() {    лабиринт = generateMaze(); // Создать лабиринт (false = путь, true = стена)    за (int ряд = 0; ряд < лабиринт.длина; ряд++)          // Устанавливает логические массивы в значения по умолчанию        за (int Col = 0; Col < лабиринт[ряд].длина; Col++){            был здесь[ряд][Col] = ложный;            rightPath[ряд][Col] = ложный;        }    логический б = recursiveSolve(startX, начало);    // Оставим вас с логическим массивом (correPath)     // с путем, указанным истинными значениями.    // Если b ложно, лабиринт не имеет решения}общественный логический recursiveSolve(int Икс, int у) {    если (Икс == конецX && у == конецY) возвращаться истинный; // Если вы дошли до конца    если (лабиринт[Икс][у] || был здесь[Икс][у]) возвращаться ложный;    // Если вы стоите на стене или уже были здесь    был здесь[Икс][у] = истинный;    если (Икс != 0) // Проверяет, нет ли на левом краю        если (recursiveSolve(Икс-1, у)) { // Вызывает метод один слева            rightPath[Икс][у] = истинный; // Устанавливает для этого пути значение true;            возвращаться истинный;        }    если (Икс != ширина - 1) // Проверяет, не по правому ли краю        если (recursiveSolve(Икс+1, у)) { // Вызывает метод один справа            rightPath[Икс][у] = истинный;            возвращаться истинный;        }    если (у != 0)  // Проверяет, не на лицевой стороне        если (recursiveSolve(Икс, у-1)) { // Вызывает первый метод            rightPath[Икс][у] = истинный;            возвращаться истинный;        }    если (у != высота - 1) // Проверяет, не по нижнему краю        если (recursiveSolve(Икс, у+1)) { // Вызывает метод один вниз            rightPath[Икс][у] = истинный;            возвращаться истинный;        }    возвращаться ложный;}

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

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

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

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

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

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

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

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

Рекомендации

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

внешняя ссылка