Как выбраться из лабиринта правило
Одним из самых простых правил для прохождения является правило одной руки: двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута. Хотя у этого правила и есть один недостаток.
Если у лабиринта нет отдельно стоящих стенок, то есть нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт называют односвязным и его всегда можно обойти полностью, применив правило одной руки
Если же лабиринт содержит отдельно стоящие стенки, то, применяя правило одной, не всегда можно пройти все коридоры и тупики. Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами называются многосвязными.
Многосвязные лабиринты можно разделить на две группы: без петли вокруг цели (замкнутый маршрут не проходит вокруг цели) и с замкнутой петлей вокруг цели (цель можно обойти по замкнутому маршруту).
Универсальный алгоритм прохождения любых лабиринтов был описан в книге французского математика Э. Люка Recreations matematiques, изданной в 1882 году. Интересно, что Люка при описании алгоритма указал на первенство другого французского математика М. Тремо. Таким образом, алгоритм стал известен как алгоритм Люка–Тремо.
Тремо предлагает следующие правила: выйдя из любой точки лабиринта, надо сделать отметку на его стене (крест) и двигаться в произвольном направлении до тупика или перекрестка; в первом случае вернуться назад, поставить второй крест, свидетельствующий, что путь пройден дважды — туда и назад, и идти в направлении, не пройденном ни разу, или пройденном один раз; во втором — идти по произвольному направлению, отмечая каждый перекресток на входе и на выходе одним крестом; если на перекресте один крест уже имеется, то следует идти новым путем, если нет — то пройденным путем, отметив его вторым крестом.
Зная алгоритм Тремо, можно скорректировать поведение легендарного Тесея. Вдохновленный подарком любимой Ариадны, он уверенно идет по лабиринту. Вдруг перед ним возникает ход, по которому уже протянута нить… Что делать? Ни в коем случае не пересекать ее, а вернуться по уже известному пути, сдваивая нить, пока не найдется еще один непройденный ход.
Как найти выход из лабиринта
В создании этой статьи участвовала наша опытная команда редакторов и исследователей, которые проверили ее на точность и полноту.
Команда контент-менеджеров wikiHow тщательно следит за работой редакторов, чтобы гарантировать соответствие каждой статьи нашим высоким стандартам качества.
Искать выход из лабиринта очень весело, если только ваше умение ориентироваться не стремится к нулю. В таком случае вы можете почувствовать себя в тупике. Однако можно воспользоваться несколькими приемами, чтобы легко пройти через лабиринт. Правда, тогда вы лишите себя азарта от самостоятельного поиска выхода. В простых лабиринтах, где все стены соединены, можно воспользоваться правилом правой руки. А вот для любого другого лабиринта подойдет алгоритм Люка-Тремо.
Как выбраться из лабиринта
В легенде о минотавре Тезей смог выбраться из лабиринта с помощью клубка ниток. Но бывает так, что, попадая в лабиринт, вы забываете его захватить с собой. Тогда приходится надеяться только на собственную внимательность и некоторые правила.
- Как выбраться из лабиринта
- Как выбраться из лаборатории х-16
- Как выбраться из ментальных ловушек. Часть 1
Изучите карту или местность, прежде чем заходить в лабиринт. Смотря на карту, мысленно представьте, как будете проходить по этому пути, постарайтесь запомнить расположение основных развилок. Если есть возможность, возьмите карту лабиринта с собой, чтобы не заблудиться. Можно ориентироваться по местности, в которой располагается лабиринт, к примеру, если рядом с входом расположен водопад, вы сможете вернуться на шум воды.
Делайте пометки на стене, чтобы не заблудиться. Нарисуйте мелом на стене стрелочку, которая указывает направление, в котором вы шли. Если мела под рукой нет, используйте подручные материалы. Нацарапайте на стене стрелку камнем, нарисуйте веткой на земле или выложите на полу. Отмечайте крестом тупики, чтобы не заходить в них во второй раз. Во время блуждания вы можете наткнуть на свою отметку и поймете, что здесь уже были. Вы сможете выбрать другое направление, чтобы не ходить кругами.
Используйте правило левой руки. Держитесь возле левой стены лабиринта и на всех развилках поворачивайте налево. Если нужно будет вернуться назад, обернитесь и придерживайтесь правила наоборот – поворачивая направо. Применять его следует сразу от входа, чтобы обойти лабиринт по периметру.
Прислушайтесь к своим ощущениям. Движение ветра может подсказать нахождение выхода, но его не всегда можно почувствовать. Чтобы определить направление ветра, зажгите спичку и посмотрите, куда наклоняется огонь. Намочите палец и опустите к земле, ничем его не загораживая, это может помочь определить направление ветра без спички.
Как выбраться из лабиринта правило
К ак быстрее всего дойти до некоторой цели, находящейся внутри лабиринта? Можно ли добраться до этого места и вернуться ко входу так, чтобы не проходить по одному и тому же коридору дважды? Можно ли избежать бесконечного кружения по лабиринту? Предположим, вы заблудились. Как найти путь назад из лабиринта, не углубляясь в него всё дальше и дальше? Исследуя эти проблемы, мы познакомимся с некоторыми превосходными цветными лабиринтами, созданными английской фирмой Minotaur Designs («Игрушки Минотавра»).
Некоторые лабиринты имеют узлы только на входе и в и тогда вы следуете по извилистому маршруту до самого конца без опаски заблудиться. Лабиринты, имеющие дополнительные узлы, пройти сложнее, так как в каждом узле приходится выбирать, по какой из ветвей двигаться дальше. Если выбирать ветви произвольным образом, есть опасность долго кружить по лабиринту без надежды достигнуть цели или вернуться ко входу. В некоторых лабиринтах выбор может быть ограничен дополнительными условиями, например разрешением проходить по всякой ветви только один раз или только в одном направлении либо требованием пройти через определённые точки в определённом порядке. Если лабиринт имеет несколько возможных маршрутов, достигающих цели, от вас может потребоваться найти такой маршрут, который проходит через наименьшее число узлов. Назовём такой маршрут минимальным.
Имея схему лабиринта, всегда можно найти прямой маршрут от входа к цели методом проб. Задача облегчится, если закрасить тупиковые ответвления. По мере закрашивания прямой маршрут вырисовывается всё более явно.
Что делать, однако, если вы входите в лабиринт, не имея ни его схемы, ни средств для того, чтобы нарисовать её? Как вы должны поступать, проходя через узлы, если не хотите заблудиться?
Правило руки применимо только к так называемым односвязным лабиринтам. Этот термин означает, что лабиринт не содержит замкнутых маршрутов, т.е. таких, которые образуют замкнутую петлю. Замкнутый маршрут возникает в том случае, если существует ограниченный стенками «остров», который не соединяется с другими стенками лабиринта. Лабиринт с одним или более островами называется многосвязным.
Первый многосвязный садовый лабиринт был сооружён в годы в Чевнинге в Великобритании. Он состоит из восьми сцепленных друг с другом островов.
Схема «зелёного» лабиринта в Чевнинге
| Проблема | Сеть для лабиринта в Чевнинге |
В сети прямой маршрут от входа до цели образует прямую линию. Тупиковые ветви отходят от прямого маршрута и не возвращаются к нему. Остров у входа порождает маршрут, который окружает входной узел. Он может пересекать прямой маршрут в одном узле с четырьмя ветвями или в двух узлах. Для исследования лабиринта с таким замкнутым маршрутом правило руки не годится. Другая петля окружает цель; она также сводит на нет полезность правила руки. Маршрут, окружающий вход или цель, можно нарисовать проходящим под прямым маршрутом. Внутренние острова порождают петли, которые пересекают прямой маршрут в одном, или в двух узлах. Отметим, что, войдя в такую петлю, вы, пользуясь правилом руки, в конце концов выйдете из неё и продолжите путь по прямому маршруту к цели. Так же можно сойти и с более сложных петель, которые имеют дополнительные пересечения с прямым маршрутом.
| Основные | Правила Тремо для |
Предположим, вы вошли в лабиринт, прошли через ряд узлов, не делая никаких отметок, и обнаружили, что заблудились. Как быстрее всего вернуться ко входу, не углубляясь безнадёжно в лабиринт? В 1959 году О. Ор из Йельского университета изложил метод, позволяющий выпутаться из такой ситуации.
После этого пройдите по каждой незакрытой ветви дополнительно на один узел вперёд. Покидая точку x , отметьте единицей вход в ветвь. Когда вы покидаете эту ветвь в следующем узле (который вы посетили во время предыдущего поиска), пометьте единицей выходную узловую точку. (Теперь этот узел имеет две отметки.) Войдя в новую ветвь в этом узле, сделайте на входе. Если ветвь тупиковая, возвратитесь в узел, который вы только что покинули, и пометьте ветвь как закрытую. Если вы пришли в узел, который уже посещали, двигаясь по другой ветви, исходящей из точки x , пометьте каждый конец ветви, в которой находитесь, как закрытый. (Примером этого случая служит ветвь, соединяющая узлы a и b на рисунке.) Вернитесь в узел, который вы только что покинули.
Когда вы закончите изучение путей от точки x на расстояние двух узлов во всех возможных направлениях, вернитесь в x и начинайте изучать маршруты длиной три узла. Не забывайте отмечать единицей каждую ветвь, когда вы входите в неё или выходите. Заметьте, что, находясь в любом узле, вы всегда можете определить дорогу назад в точку x , сравнивая отметки на ветвях: ветвь, ведущая в точку x , имеет наибольшее число единиц. Рисунок иллюстрирует случай продвижения на расстояние трёх узлов. В данном случае вы натолкнётесь на вход, когда начнете продвигаться на расстояние четырёх узлов.
| Лабиринт «A*maze*ment» | «Алфавитный суп» |
Вы входите в лабиринт по красному пути, ведущему в узел R , и должны достичь цели, расположенной в центре, пройдя через минимальное число узлов. В каждом узле вы должны менять цвет ветви. Например, если вы вошли в узел по голубому пути, нельзя уйти из него по другому голубому пути.
Второй лабиринт имеет название «Алфавитный суп». Здесь также в каждом узле надо менять цвета ветвей. Каково здесь наименьшее число узлов, через которые надо пройти, чтобы достичь цели, расположенной в центре? Этот лабиринт устроен очень остроумно. Если вы попытаетесь определить путь, двигаясь от цели назад (обычный метод, применяемый любителями лабиринтов), то быстро потеряете дорогу. Из внутренней области лабиринта, представляющей квадрат, который обозначен буквами O , D , G и L , выбраться трудно. Многие пути, идущие от входа, образуют петли и возвращаются назад ко входу. После того как я обнаружил путь к внутренней области лабиринта, я нашёл несколько прямых маршрутов с 11 узлами (считая цель и рассматривая H в качестве первого узла). Гораздо больше времени потребовалось на то, чтобы обнаружить маршрут из 10 узлов. Я думаю, это минимальный маршрут.
В центре лабиринта находится «мост», под которым проложены ветви. Какое минимальное число узлов надо миновать, чтобы пройти от входа 1 до цели 9. Решение Фишера (в виде сети) приведено на рис. 10. Заметьте, что здесь, как и в других цветных лабиринтах, сеть содержит гораздо больше узлов, чем непосредственно видны в самом лабиринте.
Сеть лабиринта «Моста гигантов»
- Число нечётных узлов должно быть чётным или равным нулю.
- Если сеть не имеет нечётных узлов, её можно пройти по объемлющему маршруту, начав с любого узла, причём всякий такой маршрут является замкнутым.
- Если сеть содержит только два нечётных узла, её можно пройти по объемлющему маршруту, который начинается в одном из этих узлов, а заканчивается в другом. Маршрут, начинающийся в чётном узле, не может быть объемлющим.
- Сеть, которая содержит более двух нечётных узлов, не может быть пройдена по объемлющему маршруту. Её можно обойти по нескольким маршрутам так, что в каждом из них никакая ветвь не будет пройдена дважды. Если сеть содержит 2 n нечётных узлов, она может быть целиком покрыта n маршрутами.
Эти правила иллюстрируются следующим рисунком.
Маршруты, которые целиком покрывают сеть
В первой сети число нечётных узлов чётно. Начав с одного из двух нечётных узлов, можно пройти по объемлющему маршруту, закончив путь в другом нечётном узле. Если начать с единственного чётного узла, потребуется два маршрута, чтобы пройти всю сеть целиком. Вторая сеть имеет дополнительную ветвь. Здесь число нечётных узлов также чётно. Поскольку нечётных узлов здесь больше двух, пройти по сети по объемлющему маршруту невозможно. Исследование всей сети требует по меньшей мере двух маршрутов. Два примера показаны на рисунке.
Часто (но не всегда) лабиринт содержит один нечётный узел на входе, а другой в цели. Если все остальные узлы чётные, можно пройти по всему лабиринту от входа до цели, не заходя в один и тот же коридор два раза. Если же лабиринт содержит хотя бы ещё один нечётный узел, по крайней мере по одной ветви придётся пройти дважды.
Исследование сетей, называемое сейчас теорией графов, имеет широкие приложения в математике, электротехнике, вычислительной математике, разработке транспортных маршрутов и многих других областях. Теория графов оперирует с сетями таких видов, которые приложимы к исследованию лабиринтов, за одним исключением: теория не разрешает иметь ветви, которые выходят из одного узла и, сделав петлю, возвращаются в этот же узел. Однако петли, встречающиеся в лабиринтах, можно видоизменить так, чтобы они удовлетворяли требованиям теории графов; для этого надо вставить в петлю один искусственный узел. В лабиринте этот узел не создаёт затруднений и предполагает одно решение: прекратить движение по ветви и вернуться к предыдущему узлу до того, как будет встречен следующий узел.
Теория графов предлагает элегантный способ исследования лабиринта, в котором надо найти минимальный маршрут. Начать следует с составления матрицы соединений между соседними узлами. Сеть лабиринта, изображенная рисунке ниже, имеет восемь узлов.
|
|
| ||||||||||||
| Матрица, представляющая сеть лабиринта | ||||||||||||||
Ей соответствует квадратная матрица M с восемью элементами в каждой строке и в каждом столбце. Число соединений между соседними узлами является элементом матрицы. Приведем пример: от к идёт одна ветвь, поэтому с (по вертикали) (по горизонтали) Поскольку можно пройти также от к также Если бы два соседних узла были соединены двумя ветвями, соответствующий элемент был бы Нуль ставится на место всех пустых элементов. Заметьте, что матрица M симметрична относительно диагонали, идущей от верхнего левого угла к нижнему правому. Симметрия является следствием того факта, что по любой ветви можно пройти в обоих направлениях.
Умножив матрицу M на саму себя, получим матрицу M 2 ; с помощью неё можно определить, какие узлы соединены маршрутом, состоящим из двух ветвей. Вычисления производятся следующим образом. Умножьте первый элемент в первом столбце матрицы M на первый элемент в первой строке. Затем умножьте второй элемент в первом столбце на второй элемент во второй строке. Продолжайте умножать соответствующие элементы таким же способом. Закончив умножение, сложите все произведения. Это и будет
Теперь переходите к первому столбцу и второй строке. Перемножьте соответствующие элементы и сложите произведения. Это будет После этого перемножьте элементы первого столбца и третьей строки, результатом станет Закончив операции со строками, повторите всё сначала, взяв второй столбец. Перемножение элементов второго столбца и первой строки даст При перемножении элементов второго столбца и второй строки получим Продолжайте, пока не покончите со всеми строками, и переходите к третьему столбцу. Пройдясь по всем столбцам, вы получите
Элементы матрицы M 2 , лежащие на линии симметрии (диагонали), указывают на число путей, по которым можно пройти от данного узла к каждому соседнему узлу и назад, проходя таким образом по одной ветви дважды. Остальные элементы отвечают путешествию от одного узла к другому по маршруту из двух ветвей. и указывает, что существует только один маршрут, соединяющий двумя ветвями. и указывает, что существует два маршрута, соединяющих и состоящих каждый из двух ветвей. Существует ли маршрут, который ведёт от входного к и состоит из двух ветвей? Нет, такого маршрута не существует, поскольку матрицы
Если по лабиринту разрешено проходить только в одном направлении, соответствующая ему матрица видоизменяется. Например, если можно двигаться от к но не в обратном направлении, но Если вам понравился матричный способ исследования лабиринтов, проверьте, является ли маршрут, состоящий из минимальным для лабиринта «Алфавитный суп», как я утверждал выше, и сколько существует таких маршрутов.
Читайте также: