Как не заблудиться в лабиринте: алгоритмы поиска пути

Правило одной руки — самый простой способ выйти

Заходишь в лабиринт, кладёшь ладонь на стену справа (или слева — важно выбрать одну сторону и не менять её) и идёшь вперёд, всё время держа руку на этой стене. Коридор поворачивает — рука поворачивает вместе с ним. Появился тупик — разворачиваешься и продолжаешь вести рукой по той же стене. Рано или поздно этот путь приводит к выходу, причём без единой пометки на бумаге и без счёта шагов.

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

Когда правило руки подводит — лабиринты с петлями

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

Обход в глубину на пальцах

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

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

Обход в ширину на пальцах

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

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

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

Метод Тремо — правило с пометками

Французский инженер Шарль Пьер Тремо придумал способ, который работает в любом лабиринте, включая те, где правило одной руки застревает в петле. Идея в том, чтобы отмечать пройденные коридоры прямо на месте — мелом на стене, камешком на полу, любой заметной меткой — и решать дальнейший путь по числу пометок, а не по памяти.

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

Чем метод Тремо отличается в лабиринте с петлями

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

Где эти правила пригождаются за пределами школьных лабиринтов

Ровно те же идеи обхода в глубину и в ширину лежат в основе того, как компьютерная игра ищет путь для персонажа, а робот-пылесос строит маршрут по квартире. Когда нужно добраться до цели самым дешёвым способом при разной стоимости шагов — например, объезжать пробки на карте, — на сцену выходит более сложный алгоритм Дейкстры. Для простого лабиринта без разной цены шагов хватает обычного обхода в ширину.