June 12

Алгоритм Тремо: как французский математик XIX века изобрёл «нить Ариадны» для любых лабиринтов

Фреска «Нить Ариадны» в стиле древнегреческого мифа о Тесее, который успешно прошёл Кносский лабиринт и сразил Минотавра

В 1882 году французский математик Эдуард Люка в своей книге «Математические развлечения» (Récréations mathématiques) описал универсальный метод прохождения лабиринтов. Однако сам Люка уточнял: первенство принадлежит его соотечественнику Шарлю Пьеру Тремо (фр. Charles Pierre Trémaux). Так мир узнал об алгоритме Тремо — элегантном методе, решающем задачу нахождения пути в любом лабиринте.

Люка метко назвал этот метод «математической нитью» — аллюзией на легендарную «нить Ариадны» из греческого мифа.

Люка Э. «Математические развлечения» (1882).С.42, Некоторые страницы из книги Люка Э. «Математические развлечения» (1882). Почитать всю книгу можно на сайте: www.mathedu.ru/text/lyuka_matematicheskie_razvlecheniya_1883/p0/

С развитием компьютерных наук алгоритм Тремо получил второе дыхание — он лёг в основу одного из базовых методов обхода графов — DFS (Depth First Search, «поиск в глубину»), используемого в робототехнике, ИИ и навигации.

Алгоритмы прохождения лабиринтов

Среди известных методов:

  • Bruteforce / полный перебор,
  • Алгоритм Тремо (Trémaux Algorithm),
  • Random Mouse (случайное поведение мыши),
  • Wall-Follower (метод правой руки),
  • Dead-End Filling (метод вырезания тупиков).

В чём суть метода Тремо?

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

Суть метода — в систематической маркировке всех пройденных путей. Каждый коридор может быть пройден не более двух раз.

Правила алгоритма:

  1. Входя в коридор, поставьте одну метку (например, крестик).
  2. На развилке:
    • Если путь не размечен — идите по нему и поставьте первую метку.
    • Если уже есть одна метка — вернитесь, поставив вторую: это тупик или петля.
    • Если все пути помечены дважды — возвращайтесь к последней точке выбора.
  3. Выход найден, если вы достигли цели или полностью прошли все пути и вернулись к началу.
Анимация с демонстрацией работы алгоритма Тремо

Попробуйте сами

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

Попытайтесь обойти лабиринт по схеме, описанной выше

Миф о нити Ариадны

Идея маркировки путей напоминает «Нить Ариадны» из греческого мифа о Тесее, который успешно прошёл Кносский лабиринт и сразил Минотавра. Коротко напомним, о чём этот миф.

Фреска в стиле древнегреческих мифов о Тесее и нити Ариадны

Сюжет о «нити Ариадны» вдохновляет до сих пор. Согласно мифу, критский царь Минос заточил Минотавра в огромный лабиринт. Афиняне каждые девять лет были вынуждены отправлять на съедение чудовищу 14 юношей и девушек. Однажды с ними отплыл и Тесей, сын афинского царя. Дочь Миноса — Ариадна — влюбилась в Тесея и передала ему волшебный клубок, полученный от Дедала, архитектора лабиринта.

Тесей, разматывая нить, победил Минотавра и по той же нити вышел из лабиринта — спасая не только себя, но и всех остальных.

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

Историческая справка

Шарль Пьер Тремо (1818–1895)

Шарль Пьер Тремо (1818–1895) — французский инженер, архитектор, фотограф и путешественник. Автор научных и этнографических работ, воспитанник Политехнической школы, специалист по навигации и географии.

Метод, названный его именем, был позже использован Клодом Шенноном — основоположником теории информации — в механическом роботе «Тесей» (1950), который умел находить выход из любого лабиринта. Робот ставил метки, избегал повторений и в итоге выбирал кратчайший путь.

Алгоритм Тремо — это не просто метод решения задач, а мост между античной мифологией и современной информатикой. Он превратил хаос лабиринта в систему и стал основой для алгоритмов искусственного интеллекта. Как заметил Люка, «гений Тремо в том, что он превратил хаотичное блуждание в систему».