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

Внешние видео
Внешние видео
	Стратегия лабиринта: заполнение тупика
	Алгоритм решения лабиринта

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

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

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

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

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

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

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

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

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

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

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

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

Непересекающиеся (где стены не соединены с внешней границей/граница не замкнута) лабиринты можно решить методом следования за стеной, при условии, что вход и выход в лабиринт находятся на внешних стенах лабиринта. Однако если решатель начинает работу внутри лабиринта, он может находиться на участке, не пересекающемся с выходом, и последователи стены будут постоянно обходить свое кольцо. Алгоритм Pledge (названный в честь Джона Пледжа из Эксетера) может решить эту проблему. ^[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]; // The mazeboolean[][] wasHere = new boolean[width][height];boolean[][] correctPath = new boolean[width][height]; // The solution to the mazeint startX, startY; // Starting X and Y values of mazeint endX, endY;     // Ending X and Y values of mazepublic void solveMaze() {    maze = generateMaze(); // Create Maze (false = path, true = wall)    // Below assignment to false is redundant as Java assigns array elements to false by default     for (int row = 0; row < maze.length; row++)          // Sets boolean Arrays to default values        for (int col = 0; col < maze[row].length; col++){            wasHere[row][col] = false;            correctPath[row][col] = false;        }    boolean b = recursiveSolve(startX, startY);    // Will leave you with a boolean array (correctPath)     // with the path indicated by true values.    // If b is false, there is no solution to the maze}public boolean recursiveSolve(int x, int y) {    if (x == endX && y == endY) return true; // If you reached the end    if (maze[x][y] || wasHere[x][y]) return false;    // If you are on a wall or already were here    wasHere[x][y] = true;    if (x != 0) // Checks if not on left edge        if (recursiveSolve(x-1, y)) { // Recalls method one to the left            correctPath[x][y] = true; // Sets that path value to true;            return true;        }    if (x != width - 1) // Checks if not on right edge        if (recursiveSolve(x+1, y)) { // Recalls method one to the right            correctPath[x][y] = true;            return true;        }    if (y != 0)  // Checks if not on top edge        if (recursiveSolve(x, y-1)) { // Recalls method one up            correctPath[x][y] = true;            return true;        }    if (y != height - 1) // Checks if not on bottom edge        if (recursiveSolve(x, y+1)) { // Recalls method one down            correctPath[x][y] = true;            return true;        }    return false;}

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

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

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

Point src, dst;// Source and destination coordinates// cur also indicates the coordinates of the current locationint MD_best = MD(src, dst);// It stores the closest MD we ever had to dst// A productive path is the one that makes our MD to dst smallerwhile (cur != dst) {    if (there exists a productive path) {        Take the productive path;    } else {        MD_best = MD(cur, dst);        Imagine a line between cur and dst;        Take the first path in the left/right of the line; // The left/right selection affects the following hand rule        while (MD(cur, dst) != MD_best || there does not exist a productive path) {            Follow the right-hand/left-hand rule; // The opposite of the selected side of the line    }}

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

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

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

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

См. также

Ссылки

^ Лабиринт к дереву на YouTube
^ Алелиюнас, Ромас; Карп, Ричард М; Липтон, Ричард Дж; Ловас, Ласло; Ракофф, Чарльз (1979). «Случайные блуждания, универсальные последовательности обхода и сложность задач лабиринта». 20-й ежегодный симпозиум по основам информатики (SFC, 1979) . Компьютерное общество IEEE. стр. 218–223.
^ Преобразованный лабиринт на YouTube
^ Абельсон; диСесса (1980), Геометрия черепахи: компьютер как средство изучения математики , MIT Press, ISBN 9780262510370
^ Сеймур Пейперт, «Использование технологий для улучшения образования» , Памятка Массачусетского технологического института по искусственному интеллекту № 298 , июнь 1973 г.
^ Публичная конференция, 2 декабря 2010 г. - профессор Жан Пеллетье-Тиберт в Академии Макона (Бургундия, Франция) - (Тезисы опубликованы в журнале Annals Academic, март 2011 г. - ISSN 0980-6032 )
Шарль Тремо (° 1859 - † 1882) Парижская политехническая школа (X: 1876), французский инженер телеграфа.
^ Эдуард Лукас: Математическое воссоздание , том I, 1882.
^ Х. Флейшнер: Графы Эйлера и связанные с ними темы. В: Анналы дискретной математики № 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 сентября 2015 г.). «Алгоритм маршрутизации с низкими издержками, полностью распределенный и гарантированной доставки для неисправной сети на кристалле» . Материалы 9-го Международного симпозиума по сетям на кристалле . Нокс '15. стр. 1–8. дои : 10.1145/2786572.2786591 . ISBN 9781450333962 . S2CID 17741498 .
^ Перейти обратно: ^а ^б Френьио, Пьер; Гасенец, Лешек; Ковальский, Дариуш Р; Пелц, Анджей (2006). «Коллективное исследование деревьев». Сети . 48 (3). Интернет-библиотека Wiley: 166–177. дои : 10.1002/net.20127 .

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

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

[1] Лабиринт к дереву на YouTube

[Aleliunas1979-2] Алелиюнас, Ромас; Карп, Ричард М; Липтон, Ричард Дж; Ловас, Ласло; Ракофф, Чарльз (1979). «Случайные блуждания, универсальные последовательности обхода и сложность задач лабиринта». 20-й ежегодный симпозиум по основам информатики (SFC, 1979) . Компьютерное общество IEEE. стр. 218–223.

[3] Преобразованный лабиринт на YouTube

[4] Абельсон; диСесса (1980), Геометрия черепахи: компьютер как средство изучения математики , MIT Press, ISBN 9780262510370

[5] Сеймур Пейперт, «Использование технологий для улучшения образования» , Памятка Массачусетского технологического института по искусственному интеллекту № 298 , июнь 1973 г.

[6] Публичная конференция, 2 декабря 2010 г. - профессор Жан Пеллетье-Тиберт в Академии Макона (Бургундия, Франция) - (Тезисы опубликованы в журнале Annals Academic, март 2011 г. - ISSN 0980-6032 )
Шарль Тремо (° 1859 - † 1882) Парижская политехническая школа (X: 1876), французский инженер телеграфа.

[Récréations_Mathématiques-7] Эдуард Лукас: Математическое воссоздание , том I, 1882.

[Eulerian_Graphs_and_related_Topics-8] Х. Флейшнер: Графы Эйлера и связанные с ними темы. В: Анналы дискретной математики № 50, часть 1, том 2, 1991, страница X20.

[9] Эвен, Шимон (2011), Графовые алгоритмы (2-е изд.), Cambridge University Press, стр. 46–48, ISBN 978-0-521-73653-4 .

[10] Седжвик, Роберт (2002), Алгоритмы на C++: алгоритмы графов (3-е изд.), Pearson Education, ISBN 978-0-201-36118-6 .

[11] Фаттах, Мохаммед; и др. (28 сентября 2015 г.). «Алгоритм маршрутизации с низкими издержками, полностью распределенный и гарантированной доставки для неисправной сети на кристалле» . Материалы 9-го Международного симпозиума по сетям на кристалле . Нокс '15. стр. 1–8. дои : 10.1145/2786572.2786591 . ISBN 9781450333962 . S2CID 17741498 .

[Fraigniaud2006-12] Перейти обратно: ^а ^б Френьио, Пьер; Гасенец, Лешек; Ковальский, Дариуш Р; Пелц, Анджей (2006). «Коллективное исследование деревьев». Сети . 48 (3). Интернет-библиотека Wiley: 166–177. дои : 10.1002/net.20127 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]