Лабиринт как пройти
Автор Flying teapot задал вопрос в разделе Естественные науки
Как пройти объёмный лабиринт? и получил лучший ответ
Ответ от Булат 1[гуру]
Полагаю, в математическом плане всё упирается в понятие "планарный граф", см. Википедию. Ведь не всякий граф планарный (т. е. не всякий лабиринт можно представить в плоскости без пересечения коридоров) . Для планарного графа будет работать алгоритм левой стенки. Для остальных - вряд ли существует похожий алгоритм.
Но это не значит, что алгоритма нет вообще.
Универсальный алгоритм, годящийся для любого графа, придумать совершенно несложно.
1) При прохождении каждой вершины (т. е. каждой развязки коридоров) запоминаем, что мы эту вершину проходили, и запоминаем, в какой коридор свернули.
2) При попадании в вершину проверяем, были ли мы уже в этой вершине. Если были, то теперь уже сворачиваем в другой коридор. (А если возможные коридоры кончились, то лабиринт непроходим - граф не связный, см. Википедию) .
3) Если перед нами задача не просто пройти лабиринт, но и "запомнить" путь, то запоминать нужно все ациклические ветки, которые мы проходили, т. е. те моменты, когда мы по кругу пришли в ту же точку, запоминать нет смысла.
И этот алгоритм можно упрощать. Например, придумать какой-то принцип, по которому мы нумеруем коридоры. Тогда на каждом зацикливании можно вырезать сам цикл и запоминать только то, что мы проходили по коридору № такому-то.
Flying teapot
Просветленный
(39950)
Я просто интересовался, есть ли теоретическое решение. Так как слышал от кого-то об отсутствии решения, и, вот, хотел узнать, так ли это.
аналогично
просто заводится правило
к примеру: на развилке если возможно делать повороты в следующем порядке налево прямо направо вверх вниз
Давай разбираться.
В двухмерном пространстве есть 4 линейных степени свободы, в трёхмерном - 6.
Если следовать вашей логике, то для трёхмерного лабиринта будет всё аналогично - можно просто выбрать левую сторону - левая сторона будет тоже одной из степеней свободы.
Другое дело, что не каждый плоский лабиринт можно пройти только по левой стороне (на самом деле "левые лабиринты" часто создают в садах, чтобы туристы особо не путались) . Но если следовать методом проб и ошибок, то сперва можно, конечно, выбрать левую - потом, если ошибся, вернуться, и выбрать правую. И так дальше. Логика проста.
А в трёхмерном лабиринте получиться на порядок сложнее. Я бы расписал такую логику. Не знаю, правильная она или нет, я её на ходу придумал.
1. Выбрать 2 постоянных направления (вперёд-назад) - это для того, чтобы можно было вернуться
2. Остальные направления оставить как меняющиеся - вперёд, вниз, влево, вправо
3. Выбрать контрольное направление из меняющихся. Выберем левое.
4. Идти вперёд до первого тупика
5. При тупики вернуться на ближайшую развилку (развилка это там, где нужно выбрать два и больше направления) и выбрать другое направление - к примеру, правое (если оно там есть)
Итак дальше - т. е. попал в тупик на правом, вернулся - пошёл вниз, снова тупик - наверх и т. д.
... а Пифагор на что?
:))