Выход из лабиринта правило правой руки. Правило одной руки

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

Избегайте троп, отмеченных дважды. Если вы вынуждены идти по тропе, которую вы уже отметили один раз, вам стоит отметить ее и во второй раз. Согласно алгоритму Люка-Тремо, тропа с двойной пометкой не приведет вас к выходу. Если вы нашли перекресток, где одна тропа отмечена дважды, всегда выбирайте другой путь, даже если это будет означать, что придется возвращаться назад.

Вернитесь назад, если наткнулись на тупик. Если вы зашли в тупик, вам нужно вернуться к последнему перекрестку, который вы пересекли. Не забудьте пометить тропу, чтобы помнить, что она ведет в тупик. Как только доберетесь до перекрестка, выберите среди оставшихся троп одну и продолжайте пересекать лабиринт.

Доброго времени суток, уважаемое сообщество.

Предыстория

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

Вот собственно и он:

Рабочий день был скучный, настроение было отличное. Цель, средства и желание имеются. Вывод очевиден, будем проходить.

История

Для удобного решения, необходимо имеющееся изображение лабиринта, привести к типу двумерного массива. Каждый элемент которого может принять одно из 3-ех значений:

Const WALL=-1; BLANK=-2; DEADBLOCK=-3;

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

Сканирование изображения:

Var N:integer=600; LABIRINT:array of integer; ... var bit:TBitmap; i,j:integer; begin bit:=TBitmap.Create; If OpenDialog1.Execute then begin bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels=clWhite then LABIRINT:=BLANK else LABIRINT:=WALL; bit.Free; ... end; end; ...

Генерация изображения:

Var N:integer=600; LABIRINT:array of integer; ... procedure genBitmap; var bit:TBitmap; i,j:Integer; begin bit:=TBitmap.Create; bit.Width:=N+1; bit.Height:=N+1; for i:=0 to N do for j:=0 to N do begin if LABIRINT=BLANK then bit.Canvas.Pixels:=clWhite // else if LABIRINT=WALL then bit.Canvas.Pixels:=clBlack else bit.Canvas.Pixels:=clRed; end; bit.SaveToFile("tmp.bmp"); bit.Free; end; ...

Для начала, необходимо пересохранить изображение, как монохромный bmp, для того, чтоб иметь 2 цвета белый или черный. Если присмотреться к лабиринту, то он имеет стенку толщиной в 2 пикселя, а дорогу толщиной в 4 пикселя. Идеально было бы сделать, чтоб толщина стенки и дороги была 1 пиксель. Для этого необходимо перестроить изображение, разделить изображение на 3, то есть удалить каждый 2рой и 3тий, ряд и столбик пикселей из рисунка (на правильность и проходимость лабиринта это не повлияет).

Подготовленный рисунок:

Ширина и высота изображения: 1802 пикселя.

1. Используем функцию сканирования изображения.
2. Перестраиваем изображение:

Var N:integer=1801; LABIRINT:array of integer; ... procedure rebuildArr2; var i,j:integer; begin for i:=0 to ((N div 3)) do for j:=0 to ((N div 3)) do LABIRINT:=LABIRINT; N:=N div 3; end; ...

3. Генерируем перестроенное изображение.

Результат работы процедуры:

Ширина и высота изображения: 601 пиксель.

И так, у нас есть изображение лабиринта нужного вида, теперь самое интересное, поиск всех вариантов прохождения лабиринта. Что у нас есть? Массив с записанными значениями WALL - стена и BLANK - дорога.

Была одна неудачная попытка найти прохождение лабиринта с помощью волнового алгоритма. Почему неудачная, во всех попытках данный алгоритм приводил к ошибке «Stack Overflow». Я уверен на 100%, что используя его, можно найти прохождение, но появился запал придумать что-то более интересное.

Идея пришла не сразу, было несколько реализаций прохождения, которые по времени, работали приблизительно по 3 минуты, после чего пришло озарение: «а что, если искать не пути прохождения, а пути которые не ведут к прохождению лабиринта и помечать их как тупиковые».

Алгоритм такой:
Выполнять рекурсивную функцию по всем точкам дорог лабиринта:
1. Если мы стоим на дороге и вокруг нас 3 стены, помечаем место где мы стоим как тупик, в противном случае выходим из функции;
2. Переходим на место которое не является стенкой из пункта №1, и повторяем пункт №1;

Программная реализация:

Var N:integer=600; LABIRINT:array of integer; ... procedure setBlankAsDeadblockRec(x,y:integer); var k:integer; begin k:=0; if LABIRINT=blank then begin if LABIRINT<><><><>BLANK then k:=k+1; if k=4 then LABIRINT:=DEADBLOCK; if k=3 then begin LABIRINT:=DEADBLOCK; if LABIRINT=BLANK then setBlankAsDeadblockRec(x-1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y-1); if LABIRINT=BLANK then setBlankAsDeadblockRec(x+1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y+1); end; end; end; procedure setDeadblock; var i,j:integer; begin for i:=1 to N-1 do for j:=1 to N-1 do setBlankAsDeadblockRec(i,j); end; ...

Заключение

Я получил «полный» рабочий алгоритм, который можно использовать для поиска всех прохождений лабиринта. Последний по скорости работы превзошел все ожидания. Надеюсь моя маленькая работа, принесет кому-то пользу или подтолкнет к новым мыслям.

Программный код и пройденный лабиринт:

//Прошу не бить ногами за использованный язык программирования. unit Unit1; interface uses Windows, Graphics, Forms, Dialogs, ExtCtrls, StdCtrls, Controls, Classes; const WALL=-1; BLANK=-2; DEADBLOCK=-3; type TForm1 = class(TForm) Button1: TButton; OpenDialog1: TOpenDialog; procedure Button1Click(Sender: TObject); private { Private declarations } public { Public declarations } end; var Form1: TForm1; N:integer=600; LABIRINT:array of integer; implementation {$R *.dfm} procedure genBitmap; var bit:TBitmap; i,j:Integer; begin bit:=TBitmap.Create; bit.Width:=N+1; bit.Height:=N+1; for i:=0 to N do for j:=0 to N do begin if LABIRINT=BLANK then bit.Canvas.Pixels:=clWhite // else if LABIRINT=WALL then bit.Canvas.Pixels:=clBlack else bit.Canvas.Pixels:=clRed; end; bit.SaveToFile("tmp.bmp"); bit.Free; end; procedure rebuildArr2; var i,j:integer; begin for i:=0 to ((N div 3)) do for j:=0 to ((N div 3)) do LABIRINT:=LABIRINT; N:=N div 3; end; procedure setBlankAsDeadblockRec(x,y:integer); var k:integer; begin k:=0; if LABIRINT=blank then begin if LABIRINT<>BLANK then k:=k+1; if LABIRINT<>BLANK then k:=k+1; if LABIRINT<>BLANK then k:=k+1; if LABIRINT<>BLANK then k:=k+1; if k=4 then LABIRINT:=DEADBLOCK; if k=3 then begin LABIRINT:=DEADBLOCK; if LABIRINT=BLANK then setBlankAsDeadblockRec(x-1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y-1); if LABIRINT=BLANK then setBlankAsDeadblockRec(x+1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y+1); end; end; end; procedure setDeadblock; var i,j:integer; begin for i:=1 to N-1 do for j:=1 to N-1 do setBlankAsDeadblockRec(i,j); end; procedure TForm1.Button1Click(Sender: TObject); var bit:TBitmap; i,j:integer; begin bit:=TBitmap.Create; If OpenDialog1.Execute then begin bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels=clWhite then LABIRINT:=BLANK else LABIRINT:=WALL; bit.Free; setDeadblock; genBitmap; end; end; end.

Для поиска кратчайшего пути, планируется применить волновой алгоритм к найденным прохождениям лабиринта. Было-бы интересно услышать, какие еще алгоритмы можно применить, для быстрого поиска пути в большом лабиринте?

Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута. Хотя у этого правила и есть один недостаток, но о нем мы поговорим позже.

Попробуем описать робота, действующего в соответствии с правилом "правой руки".

В начале своей работы робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду.

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

Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа.

Если прохода нет - впереди стена - робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.

Блок-схема алгоритма для робота, работающего по правилу "правой руки", представлена на рисунке.

Попробуем проверить работу данного алгоритма и напишем для него программу. Для этой цели обратимся к среде программирования . Эта среда является удобным средством для моделирования различных алгоритмов, связанных с управлением роботами. В ней есть исполнитель черепаха, который по своей сути является не чем иным, как самым настоящим роботом. Черепаха располагает очень удобным набором команд - вперед, направо, налево, назад. Кроме того, в центре черепахи есть датчик, принимающий значение от 0 до 100, в зависимости от тона поверхности, на которой она находится.

Диалект языка Лого, который мы будем использовать, очень прост и похож на Basic. Познакомиться с командами языка можно . А бесплатно скачать среду программирования GameLogo - . Размер дистрибутива невелик - всего 1 Mb.

В архиве с GameLogo есть фоны с лабиринтами, одним из которых мы и воспользуемся.

В самом начале программы дадим команду черепахе, чтобы она подняла перо (по умолчанию черепаха оставляет после себя след).

Размер поля - 800 на 600 точек. Исходное положение для черепахи находится в месте с координатами 115, 545 (белый квадрат).

Цвет дорожек лабиринта - светлый, на них датчик будет принимать значения больше 50. Цвет стен лабиринта - темный, значение датчика будет меньше 50. Выход из лабиринта представлен черным квадратом, значение датчика над которым будет равно 0.

Объявим переменную флаг, с помощью которой будем контролировать, достигнут ли выход из лабиринта.

Напишем программу и запустим ее с помощью большой красной кнопки с надписью "Выполнить".

Переменная флаг фон = maze1.gif поднять перо место 115, 545 " поиск первой стены повторять пока датчик > 50 { вперед 12 } " правило правой руки повторять пока флаг = 0 { направо 90 вперед 12 если датчик = 0 то флаг = 1 иначе если датчик

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

Если же лабиринт содержит отдельно стоящие стенки, то, применяя правило "одной руки", не всегда можно пройти все коридоры и тупики. Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами называются многосвязными. При этом многосвязные лабиринты можно разделить на две группы: без "петли" вокруг цели (замкнутый маршрут не проходит вокруг цели) и с замкнутой "петлей" вокруг цели (цель можно обойти по замкнутому маршруту).

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

Решение задачи о таких лабиринтах принадлежит сравнительно позднему времени, и начало ему положено Леонардом Эйлером. Эйлер не без оснований полагал, что выход из любого лабиринта может быть найден, и притом сравнительно простым путем.

Универсальный алгоритм прохождения любых лабиринтов был описан только через столетие в книге французского математика Э. Люка "Recreations matematiques", изданной в 1882 году. Интересно, что Люка при описании алгоритма указал на первенство другого французского математика М. Тремо. Таким образом, алгоритм стал известен как алгоритм Люка-Тремо .

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

Зная алгоритм Тремо, можно скорректировать поведение легендарного Тесея. Вдохновленный подарком любимой Ариадны, он уверенно идет по лабиринту. Вдруг перед ним возникает ход, по которому уже протянута нить... Что делать? Ни в коем случае не пересекать ее, а вернуться по уже известному пути, сдваивая нить, пока не найдется еще один непройденный ход.

Применив вариант алгоритма Тремо, отец теории информации Клод Шеннон (Claude Elwood Shannon) построил одного из первых самообучающихся роботов. Шеннон дал ему звучное имя "Тесей", но в истории "Тесей" стал больше известен как "мышь" Шеннона. "Мышь" сначала обследовала весь лабиринт, а затем (во второй раз) проходила весь путь значительно быстрее, избегая участков, пройденных дважды.

На первой Российской Олимпиаде Роботов проводились соревнования, целью которых было прохождение своеобразного лабиринта: за наиболее короткое время, двигаясь через "открытые двери" в стенках, робот должен был добраться от места старта до места финиша. Контролировать свое движение робот мог по черным линиям, нанесенным на пол лабиринта.