Правило "правой руки"С глубокой древности лабиринты несли ощущение тайны и загадки.
Один из первых лабиринтов, известных человечеству, описывает Геродот
- это был египетский Лабиринт, в котором было 5000 комнат.
Со временем лабиринты утратили свое религиозно-мистическое значение и стали объектами
развлечений, превратившись в сады и парки в виде зеленых изгородей сложной конфигурации.
Разгадывание лабиринтов всегда являлось увлекательнейшим занятием,
но еще более увлекательным является создание машин, способных пройти Лабиринт.
Одним из самых простых правил для прохождения лабиринта является правило "одной руки":
двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены.
Этот алгоритм, вероятно, был известен еще древним грекам.
Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута.
Хотя у этого правила и есть один недостаток, но о нем мы поговорим позже.
Действия робота в соответствии с правилом "правой руки"
В начале своей работы робот должен найти стену, по которой он будет следовать.
Для этого он может просто двигаться вперед, пока не упрется в преграду.
После того как робот наткнулся на препятствие,
он начинает передвигаться в соответствии с правилом "правой руки".
Двигаясь вдоль стены, робот следит, есть ли проход справа.
Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа.
Если прохода нет - впереди стена - робот поворачивает налево.
Если прохода снова нет, он еще раз поворачивает налево, таким образом,
разворачиваясь на 180 градусов, и идет в обратном направлении.
Блок-схема алгоритма для робота, работающего по правилу "правой руки"Если известно, что у лабиринта нет отдельно стоящих стенок, то есть, нет замкнутых маршрутов,
по которым можно возвращаться в исходную точку, то такой
лабиринт называют односвязным
и его всегда можно обойти полностью,
применив правило "одной руки".
Если же лабиринт содержит отдельно стоящие стенки, то, применяя правило "одной руки",
не всегда можно пройти все коридоры и тупики.
Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами
называются многосвязными.
При этом многосвязные лабиринты можно разделить на две группы:
без "петли" вокруг цели (замкнутый маршрут не проходит вокруг цели)
и с замкнутой "петлей" вокруг цели (цель можно обойти по замкнутому маршруту).
Робот для прохождения лабиринта на базе ATmega8 (соревнования Micromouse competition)
Алгоритм Люка-ТремоВ многосвязных лабиринтах второй группы правило "одной руки" не работает
и, применяя его, достичь цели невозможно.
Но и эти лабиринты можно пройти, полагаясь на точный алгоритм.
Решение задачи о таких лабиринтах принадлежит сравнительно позднему времени,
и начало ему положено Леонардом Эйлером.
Эйлер не без оснований полагал, что выход из любого лабиринта может быть найден,
и притом сравнительно простым путем.
Универсальный алгоритм прохождения любых лабиринтов был описан только через столетие
в книге французского математика Э. Люка "Recreations matematiques", изданной в 1882 году.
Интересно, что Люка при описании алгоритма указал
на первенство другого французского математика М. Тремо.
Таким образом, алгоритм стал известен как
алгоритм Люка-Тремо.
Тремо предлагает следующие правила: выйдя из любой точки лабиринта,
надо сделать отметку на его стене (крест) и двигаться в произвольном направлении до тупика
или перекрестка; в первом случае вернуться назад, поставить второй крест,
свидетельствующий, что путь пройден дважды - туда и назад, и идти в направлении,
не пройденном ни разу, или пройденном один раз;
во втором - идти по произвольному направлению,
отмечая каждый перекресток на входе и на выходе одним крестом;
если на перекресте один крест уже имеется, то следует идти новым путем,
если нет - то пройденным путем, отметив его вторым крестом.
Клод ШеннонЗная алгоритм Тремо, можно скорректировать поведение легендарного Тесея.
Вдохновленный подарком любимой Ариадны, он уверенно идет по лабиринту.
Вдруг перед ним возникает ход, по которому уже протянута нить...
Что делать? Ни в коем случае не пересекать ее, а вернуться по уже известному пути,
сдваивая нить, пока не найдется еще один не пройденный ход.
Применив вариант алгоритма Тремо, отец теории информации Клод Шеннон (Claude Elwood Shannon)
построил одного из первых самообучающихся роботов.
Шеннон дал ему звучное имя "Тесей",
но в истории "Тесей" стал больше известен как "мышь" Шеннона.
"Мышь" сначала обследовала весь лабиринт, а затем (во второй раз) проходила
весь путь значительно быстрее, избегая участков, пройденных дважды.
Лабиринт на соревнованиях Micromouse competitionВ наши дни роботы, проходящие лабиринт, являются участниками одного из самых
интересных состязаний думающих машинок, которые проходят в нескольких странах мира.
Эти соревнования носят общее название
Micromouse competition и по своим техническим новациям относятся к лидерам робототехнического спорта.
На первой Российской Олимпиаде Роботов проводились соревнования,
целью, которого было прохождение своеобразного лабиринта:
за наиболее короткое время, двигаясь через "открытые двери" в стенках,
робот должен был добраться от места старта до места финиша.
Контролировать свое движение робот мог по черным линиям, нанесенным на пол лабиринта.
[свернуть]
Ответить с цитированием
метод правой ноги?
