Question

Можно ли выйти из лабиринта постоянно придерживаясь рукой одной стены?

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

Так ли это на самом деле?

Работает ли данный способ?

Как быстро выйти из лабиринта (это уже отдельный необязательный вопрос)?

Answer 1

Вообще с теоретической и алгоритмической точки зрения нахождение выхода - это поиск ветвей графа.. Есть поиск в длину и ширину..

Но для этого нужно ставить метки, или пользуясь нитью как это сделала Ариадна..

Эти алгоритмы достаточно эффективны..

"Правило правой руки" (можно и левой, главное держаться одной стены лабиринта ) теоретически тоже может сработать и в конце концов..

Но здесь эффективность этого алгоритма будет низкая, если положить для простоты, что лабиринт делится на два коридора, то путей выйдет 2^n, это степенная зависимость и она быстро растёт! Например 10 делений дадут 1024 варианта, если разделений пути будет 100, то количество вариантов 10^30!

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

Answer 2

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

Answer 3

Все со школьных лет знают правило "правой руки" при выходе из лабиринта, которое применяют так же и во всех играх, связанных с фокусом лабиринта.

Я всегда применяла это правило, когда ищешь выход, рисуя стрелку в графических загадках.

Всё правильно. Действительно, сходится.

Answer 4

Да. В любом случае выйдешь. Но проблема в том, что на это иногда потребуется оооочень много времени. Думаю есть 100%-ые способы выхода из лабиринта попроще. Но я, к сожалению, таких не знаю. А про правило одной руки знаю точно. Оно, правда, не работает в лабиринтах, где есть ещё и 4-е измерение)) В фантастических)

Answer 5

Моё мнение,что можно.Как говорится,если идти все время прямо по железной дороге- когда-нибудь дойдешь до Китая.

Правда,время займёт значительное.

Answer 6

Да, это правда. При условии, разумеется, что у лабиринта в принципе есть вход и не совпадающий с ним выход. Потому что самый первый Лабиринт, тот самый, в котором Тесей умочил Минотавра, имел только вход. Выходом (хм...) был сам Минотавр. И нить Ариадны была нужна Тесею для того, чтоб вернуться на вход, а не чтоб найти (несуществующий) выход.

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

Разумеется, это не самый быстрый путь пройти лабиринт, зато стопудово надёжный. Чтоб найти самый быстрый, надо видеть весь лабиринт, целиком.

Answer 7

Смотря где начать держаться за эту правую стену.

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