Алгоритм решения лабиринта
Алгоритм решения лабиринта — это автоматизированный метод решения лабиринта . Алгоритмы случайной мыши, следования за стеной, залога и Тремо предназначены для использования внутри лабиринта путешественником, не знающим заранее о лабиринте, тогда как алгоритмы заполнения тупика и кратчайшего пути предназначены для использования человеком или человеком. компьютерная программа, которая может видеть весь лабиринт сразу.
Лабиринты, не содержащие петель, известны как «односвязные» или «идеальные» лабиринты и эквивалентны дереву в теории графов. Алгоритмы решения лабиринтов тесно связаны с теорией графов . Интуитивно понятно, что если правильно вытянуть и растянуть дорожки в лабиринте, результат можно будет сделать похожим на дерево. [1]
Это тривиальный метод, который может быть реализован очень неразумным роботом или, возможно, мышью. Это просто идти по текущему проходу до тех пор, пока не будет достигнут перекресток, а затем принять случайное решение о следующем направлении. Хотя такой метод всегда в конечном итоге находил правильное решение , этот алгоритм может быть чрезвычайно медленным.
Самым известным правилом обхода лабиринтов является правило следования за стеной , также известное как правило левой или правой руки . Если лабиринт просто связан , то есть все его стены соединены между собой или с внешней границей лабиринта, то удерживая одну руку в контакте с одной стенкой лабиринта решатель гарантированно не потеряется и дойдет до другого выхода если он есть; в противном случае алгоритм вернется к входу, пройдя каждый коридор рядом с этим соединенным участком стен хотя бы один раз. Алгоритм представляет собой обход дерева в глубину по порядку .
Другой взгляд на то, почему работает следование за стеной, является топологическим. Если стены соединены, то они могут деформироваться в петлю или круг. [2] Затем следование вдоль стены сводится к хождению по кругу от начала до конца. Чтобы продвинуть эту идею, обратите внимание, что при группировании соединенных компонентов стен лабиринта границы между ними являются в точности решениями, даже если существует более одного решения (см. рисунки справа).
Если лабиринт не является односвязным (т. е. если начальная или конечная точки находятся в центре структуры, окруженной проходными петлями, или пути пересекаются друг под другом и такие части пути решения окружены проходными петлями), этот метод не обязательно достигнет цели.
Обратите внимание, что две метки размещаются одновременно каждый раз, когда зеленая точка достигает перекрестка. Это особенность иллюстрации; на самом деле каждая отметка должна быть размещена всякий раз, когда зеленая точка проходит через место отметки.
