В МИРЕ НАУКИ Scientific American · Издание на русском языке № 2 · ФЕВРАЛЬ 1986 · С. 62–74

Как пройти через лабиринт не заблудившись

ДЖИРЛ УОЛКЕР

Как быстрее всего дойти до некоторой цели, находящейся внутри лабиринта? Можно ли добраться до этого места и вернуться ко входу так, чтобы не проходить по одному и тому же коридору дважды? Можно ли избежать бесконечного кружения по лабиринту? Предположим, вы заблудились. Как найти путь назад из лабиринта, не углубляясь в него всё дальше и дальше? Исследуя эти проблемы, мы познакомимся с некоторыми превосходными цветными лабиринтами, созданными английской фирмой Minotaur Designs («Игрушки Минотавра»).

Вначале определим некоторые понятия. Входом называется то место, откуда вы начинаете путь; обычно вход располагается на периферии лабиринта. Целью назовём точку, в которую нужно прийти. Цель может находиться в любом месте лабиринта, в том числе на выходе. Узлом будем считать вход, цель, а также всякую точку, где коридор разветвляется или оканчивается тупиком. Отрезок пути между соседними узлами назовём ветвью. Маршрут — это последовательность ветвей. Стенка — это одна из двух сторон пути. Что такое стенка в подземном лабиринте, понятно и без пояснений. В садовом лабиринте стенкой может служить живая изгородь или невысокая насыпь, которые ограничивают путь с боков.

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

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

Что делать, однако, если вы входите в лабиринт, не имея ни его схемы, ни средств для того, чтобы нарисовать её? Как вы должны поступать, проходя через узлы, если не хотите заблудиться?

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

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

Первый многосвязный садовый лабиринт был сооружён в 1820-е годы в Чевнинге в Великобритании. Он состоит из восьми сцепленных друг с другом островов.

Схема «зелёного» лабиринта в Чевнинге

Узлы пронумерованы от 1 (на входе) до 18 в точке-цели. Предположим, вы вошли в этот лабиринт, не имея схемы, и применяете правило правой руки, проходя через каждый узел. В этом случае вы пройдёте последовательно через узлы 1–2–3–4–14–13–9–11–8–10–2–1, не достигнув цели. У вас может даже появиться мысль, что вы увидели всю внутреннюю часть лабиринта, как это действительно было бы, если бы вы вернулись ко входу в односвязном лабиринте.

Проблема внутреннего острова

Сеть для лабиринта в Чевнинге

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

С лабиринтом гораздо легче разобраться, если его схему топологически преобразовать к простой структуре, называемой сетью. В этой структуре все узлы сохранены, но ветви выпрямлены. На сети чевнингского лабиринта легко увидеть прямой маршрут 1–2–3–4–5–12–18, ведущий к цели. Подходящим является и другой маршрут, а именно 1–2–3–6–7–12–18, содержащий такое же количество узлов.

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

Основные элементы сети

Правила Тремо для исследования лабиринтов

Итак, правило руки не гарантирует успеха в достижении цели. Как же в таком случае исследовать лабиринт? Существует несколько методов, однако Э. Люка в книге «Récréations matématiques», изданной в 1882 году, отдаёт первенство некоему М. Тремо. Как видно из рисунка слева, где иллюстрируется этот метод, термины «старый узел» и «новый узел» означают, что данный узел соответственно был или не был пройден раньше. Входя в ветвь или покидая её, сделайте отметку на стене или на полу. Дойдя до нового узла, сверните на любую ветвь. Если вы зашли в тупик, вернитесь к предыдущему узлу. Если вы двигаетесь по новому пути и встречаете старый узел (в этом месте метки должны быть по меньшей мере на двух ветвях), возвратитесь к тому узлу, через который вы только что прошли. Если вы находитесь на пути, по которому уже проходили, сверните на новую ветвь. Если же это невозможно, выберите ветвь, по которой проходили один раз. Эта утомительная процедура может направить вас по длинному маршруту, но она позволяет избежать многих ловушек.

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

Как вести счёт, чтобы выбраться из лабиринта

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

После этого пройдите по каждой незакрытой ветви дополнительно на один узел вперёд. Покидая точку x, отметьте единицей вход в ветвь. Когда вы покидаете эту ветвь в следующем узле (который вы посетили во время предыдущего поиска), пометьте единицей выходную узловую точку. (Теперь этот узел имеет две отметки.) Войдя в новую ветвь в этом узле, сделайте отметку 1 на входе. Если ветвь тупиковая, возвратитесь в узел, который вы только что покинули, и пометьте ветвь как закрытую. Если вы пришли в узел, который уже посещали, двигаясь по другой ветви, исходящей из точки x, пометьте каждый конец ветви, в которой находитесь, как закрытый. (Примером этого случая служит ветвь, соединяющая узлы a и b на рисунке.) Вернитесь в узел, который вы только что покинули.

Когда вы закончите изучение путей от точки x на расстояние двух узлов во всех возможных направлениях, вернитесь в x и начинайте изучать маршруты длиной три узла. Не забывайте отмечать единицей каждую ветвь, когда вы входите в неё или выходите. Заметьте, что, находясь в любом узле, вы всегда можете определить дорогу назад в точку x, сравнивая отметки на ветвях: ветвь, ведущая в точку x, имеет наибольшее число единиц. Рисунок иллюстрирует случай продвижения на расстояние трёх узлов. В данном случае вы натолкнётесь на вход, когда начнете продвигаться на расстояние четырёх узлов.

Фирма Minotaur Designs — это небольшое предприятие, строящее полномасштабные лабиринты в Англии и других странах. А. Фишер, один из владельцев фирмы, прислал мне чертежи трёх оригинальных цветных лабиринтов, выпускаемых фирмой. Первый лабиринт, названный «A*maze*ment» (игра слов: maze — лабиринт, amazement — развлечение. — Перев.), был первоначально построен в Эпсоме для выставки.

Лабиринт «A*maze*ment» фирмы Minotaur Designs

«Алфавитный суп»

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

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

Второй лабиринт имеет название «Алфавитный суп». Здесь также в каждом узле надо менять цвета ветвей. Каково здесь наименьшее число узлов, через которые надо пройти, чтобы достичь цели, расположенной в центре? Этот лабиринт устроен очень остроумно. Если вы попытаетесь определить путь, двигаясь от цели назад (обычный метод, применяемый любителями лабиринтов), то быстро потеряете дорогу. Из внутренней области лабиринта, представляющей квадрат, который обозначен буквами O, D, G и L, выбраться трудно. Многие пути, идущие от входа, образуют петли и возвращаются назад ко входу. После того как я обнаружил путь к внутренней области лабиринта, я нашёл несколько прямых маршрутов с 11 узлами (считая цель и рассматривая H в качестве первого узла). Гораздо больше времени потребовалось на то, чтобы обнаружить маршрут из 10 узлов. Я думаю, это минимальный маршрут.

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

«Мост гигантов»

В центре лабиринта находится «мост», под которым проложены ветви. Какое минимальное число узлов надо миновать, чтобы пройти от входа 1 до цели 9. Решение Фишера (в виде сети) приведено на рис. 10. Заметьте, что здесь, как и в других цветных лабиринтах, сеть содержит гораздо больше узлов, чем непосредственно видны в самом лабиринте.

Сеть лабиринта «Моста гигантов»

Изучение свойств сетей восходит к работам выдающегося математика XVIII века Леонарда Эйлера. Рассмотрим произвольную сеть. Узел называется чётным или нечётным в зависимости от того, сколько сходится в нём ветвей. Маршрут — это любая последовательность ветвей, в которой никакая из ветвей не повторяется. Замкнутый маршрут заканчивается в том же узле, где и начинается. Назовём маршрут объемлющим, если, следуя по нему, можно обойти всю сеть, не проходя дважды по одной ветви.

Эйлер установил четыре основных правила, которые применимы к сетям.

• Число нечётных узлов должно быть чётным или равным нулю.
• Если сеть не имеет нечётных узлов, её можно пройти по объемлющему маршруту, начав с любого узла, причём всякий такой маршрут является замкнутым.
• Если сеть содержит только два нечётных узла, её можно пройти по объемлющему маршруту, который начинается в одном из этих узлов, а заканчивается в другом. Маршрут, начинающийся в чётном узле, не может быть объемлющим.
• Сеть, которая содержит более двух нечётных узлов, не может быть пройдена по объемлющему маршруту. Её можно обойти по нескольким маршрутам так, что в каждом из них никакая ветвь не будет пройдена дважды. Если сеть содержит 2n нечётных узлов, она может быть целиком покрыта n маршрутами.

Эти правила иллюстрируются следующим рисунком.

Маршруты, которые целиком покрывают сеть

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

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

Исследование сетей, называемое сейчас теорией графов, имеет широкие приложения в математике, электротехнике, вычислительной математике, разработке транспортных маршрутов и многих других областях. Теория графов оперирует с сетями таких видов, которые приложимы к исследованию лабиринтов, за одним исключением: теория не разрешает иметь ветви, которые выходят из одного узла и, сделав петлю, возвращаются в этот же узел. Однако петли, встречающиеся в лабиринтах, можно видоизменить так, чтобы они удовлетворяли требованиям теории графов; для этого надо вставить в петлю один искусственный узел. В лабиринте этот узел не создаёт затруднений и предполагает одно решение: прекратить движение по ветви и вернуться к предыдущему узлу до того, как будет встречен следующий узел.

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

Ей соответствует квадратная матрица M с восемью элементами в каждой строке и в каждом столбце. Число соединений между соседними узлами является элементом матрицы. Приведем пример: от узла 1 к узлу 2 идёт одна ветвь, поэтому элемент (1,2) с координатами 1 (по вертикали) и 2 (по горизонтали) равен 1. Поскольку можно пройти также от узла 2 к узлу 1, элемент (2,1) также равен 1. Если бы два соседних узла были соединены двумя ветвями, соответствующий элемент был бы равен 2. Нуль ставится на место всех пустых элементов. Заметьте, что матрица M симметрична относительно диагонали, идущей от верхнего левого угла к нижнему правому. Симметрия является следствием того факта, что по любой ветви можно пройти в обоих направлениях.

Умножив матрицу M на саму себя, получим матрицу M²; с помощью неё можно определить, какие узлы соединены маршрутом, состоящим из двух ветвей. Вычисления производятся следующим образом. Умножьте первый элемент в первом столбце матрицы M на первый элемент в первой строке. Затем умножьте второй элемент в первом столбце на второй элемент во второй строке. Продолжайте умножать соответствующие элементы таким же способом. Закончив умножение, сложите все произведения. Это и будет элемент (1,1) матрицы M².

Теперь переходите к первому столбцу и второй строке. Перемножьте соответствующие элементы и сложите произведения. Это будет элемент (1,2) матрицы M². После этого перемножьте элементы первого столбца и третьей строки, результатом станет элемент (1,3) матрицы M². Закончив операции со строками, повторите всё сначала, взяв второй столбец. Перемножение элементов второго столбца и первой строки даст элемент (2,1) матрицы M². При перемножении элементов второго столбца и второй строки получим элемент (2,2) матрицы M². Продолжайте, пока не покончите со всеми строками, и переходите к третьему столбцу. Пройдясь по всем столбцам, вы получите матрицу M².

Элементы матрицы M², лежащие на линии симметрии (диагонали), указывают на число путей, по которым можно пройти от данного узла к каждому соседнему узлу и назад, проходя таким образом по одной ветви дважды. Остальные элементы отвечают путешествию от одного узла к другому по маршруту из двух ветвей. Элемент (2,4) равен 1 и указывает, что существует только один маршрут, соединяющий узлы 2 и 4 двумя ветвями. Элемент (2,5) равен 2 и указывает, что существует два маршрута, соединяющих узлы 2 и 5 и состоящих каждый из двух ветвей. Существует ли маршрут, который ведёт от входного узла 1 к узлу-цели 5 и состоит из двух ветвей? Нет, такого маршрута не существует, поскольку элемент (1,5) матрицы равен 0.

Умножив M² на M, получим матрицу M³; она позволяет определять число путей, по которым можно пройти от одного узла к другому и которые состоят из трёх ветвей. Например, элемент (1,4) равен 1 и указывает, что есть только один маршрут из трёх ветвей, связывающий узел 1 с узлом 4, а именно: 1–2–3–4. Некоторые маршруты вырождаются. Например, из шести маршрутов, соединяющих узлы 2 и 3 тремя ветвями, один — это 2–3–4–3. Существует ли маршрут из трёх ветвей, соединяющий узлы 1 и 5? Да, существует, поскольку элемент (1,5) не равен нулю. Его значение (2) указывает, что имеется два маршрута из трёх ветвей, по которым можно добраться до цели от входа.

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

Если по лабиринту разрешено проходить только в одном направлении, соответствующая ему матрица видоизменяется. Например, если можно двигаться от узла 4 к узлу 3, но не в обратном направлении, элемент (4,3) равен 1, но элемент (3,4) есть 0. Если вам понравился матричный способ исследования лабиринтов, проверьте, является ли маршрут, состоящий из 10 узлов, минимальным для лабиринта «Алфавитный суп», как я утверждал выше, и сколько существует таких маршрутов.