В 1882 году французский математик Эдуард Люка в своей книге «Математические развлечения» (Récréations mathématiques) описал универсальный метод прохождения лабиринтов. Однако сам Люка уточнял: первенство принадлежит его соотечественнику Шарлю Пьеру Тремо (фр. Charles Pierre Trémaux). Так мир узнал об алгоритме Тремо — элегантном методе, решающем задачу нахождения пути в любом лабиринте.
Люка метко назвал этот метод «математической нитью» — аллюзией на легендарную «нить Ариадны» из греческого мифа.
С развитием компьютерных наук алгоритм Тремо получил второе дыхание — он лёг в основу одного из базовых методов обхода графов — DFS (Depth First Search, «поиск в глубину»), используемого в робототехнике, ИИ и навигации.
Алгоритмы прохождения лабиринтов
Среди известных методов:
- Bruteforce / полный перебор,
- Алгоритм Тремо (Trémaux Algorithm),
- Random Mouse (случайное поведение мыши),
- Wall-Follower (метод правой руки),
- Dead-End Filling (метод вырезания тупиков).
В чём суть метода Тремо?
В отличие от «правила правой руки», работающего только в односвязных (простейших) лабиринтах, метод Тремо применим к любым схемам, включая те, что содержат петли, развилки и тупики. В отличие от случайного блуждания, он всегда находит выход, если таковой существует.
Суть метода — в систематической маркировке всех пройденных путей. Каждый коридор может быть пройден не более двух раз.
Правила алгоритма:
- Входя в коридор, поставьте одну метку (например, крестик).
- На развилке:
- Если путь не размечен — идите по нему и поставьте первую метку.
- Если уже есть одна метка — вернитесь, поставив вторую: это тупик или петля.
- Если все пути помечены дважды — возвращайтесь к последней точке выбора.
- Выход найден, если вы достигли цели или полностью прошли все пути и вернулись к началу.
Попробуйте сами
Мы предлагаем вам изучить алгоритм Тремо и пройти по приведённому ниже лабиринту — от входа до выхода, строго следуя правилам маркировки.
Миф о нити Ариадны
Идея маркировки путей напоминает «Нить Ариадны» из греческого мифа о Тесее, который успешно прошёл Кносский лабиринт и сразил Минотавра. Коротко напомним, о чём этот миф.
Сюжет о «нити Ариадны» вдохновляет до сих пор. Согласно мифу, критский царь Минос заточил Минотавра в огромный лабиринт. Афиняне каждые девять лет были вынуждены отправлять на съедение чудовищу 14 юношей и девушек. Однажды с ними отплыл и Тесей, сын афинского царя. Дочь Миноса — Ариадна — влюбилась в Тесея и передала ему волшебный клубок, полученный от Дедала, архитектора лабиринта.
Тесей, разматывая нить, победил Минотавра и по той же нити вышел из лабиринта — спасая не только себя, но и всех остальных.
Узнав о роли Дедала в победе Тесея, Минос заключил художника вместе с сыном Икаром в лабиринт. Они были освобождены женой Миноса. Сделав крылья из скреплённых воском перьев, Дедал вместе с Икаром улетели с острова. В пути Икар поднялся слишком высоко, солнце растопило воск, и юноша упал в море, которое впоследствии назвали Икарийским.
Историческая справка
Шарль Пьер Тремо (1818–1895) — французский инженер, архитектор, фотограф и путешественник. Автор научных и этнографических работ, воспитанник Политехнической школы, специалист по навигации и географии.
Метод, названный его именем, был позже использован Клодом Шенноном — основоположником теории информации — в механическом роботе «Тесей» (1950), который умел находить выход из любого лабиринта. Робот ставил метки, избегал повторений и в итоге выбирал кратчайший путь.
Алгоритм Тремо — это не просто метод решения задач, а мост между античной мифологией и современной информатикой. Он превратил хаос лабиринта в систему и стал основой для алгоритмов искусственного интеллекта. Как заметил Люка, «гений Тремо в том, что он превратил хаотичное блуждание в систему».