«Поиск пути в лабиринте» — это задача по поиску самого короткого пути на планарном графе.
Введение
Логическими принято именовать алгоритмы, содержащие предписания (операции), относящиеся к объектам, имеющим нечисловую природу. Характерной чертой логического алгоритма может считаться осуществление выбора на всех шагах по заданным правилам альтернативной операции, которая реализуется при переходе к следующему шагу. К логическим задачам могут быть отнесено большинство разных игр.
Тем не менее, выделение логических задач из класса математических задач является весьма условным, поскольку практически всегда задачи выступают как смешанные, то есть, в них имеется совокупность и числовых, и логических операций. Например, машинные алгоритмы игры в шахматы применяют на всех шагах вычисление значения определенной функции, которые учитывают оценку позиции после каждого следующего хода и стоимость размена фигур.
«Поиск пути в лабиринте»
Задача «Поиск пути в лабиринте» относится еще к греческой мифологии. В ней, в том числе, описан подвиг Тезея, который проник в лабиринт, где находился чудовищный Минотавр, пожиравший местных красавиц. Тезей отыскал в этом лабиринте Минотавра и сумел убить его. А выйти из лабиринта ему помогла Ариадна, давшая ему клубок с нитками, один конец которых был в руках у нее самой. По мере проникновения Тезея в дебри лабиринта, клубок разматывался, а потом Тезей стал наматывать нитки обратно на клубок, и ему удалось успешно вернуться к выходу.
Будем рассматривать задачу поиска пути в лабиринте в общем случае, то есть, для класса аналогичных задач. Можно представить лабиринт как конечную систему площадок, от которых могут расходиться коридоры. При этом, любой из коридоров должен соединять две площадки, именуемые в таком случае смежными. Допускается возможность существования таких площадок, из которых есть путь лишь в один коридор, и подобные площадки следует именовать тупиками.
С геометрической точки зрения лабиринт может быть представлен в виде системы точек А, В, , ..., которые изображают площадки, и набора отрезков АВ, ВС, ..., отображающих коридоры, соединяющие определенные пары этих точек, как показано на рисунке ниже.
Рисунок 1. Геометрическое изображение лабиринта. Автор24 — интернет-биржа студенческих работ
Здесь смежными могут считаться, к примеру, точки В и С, К и М и так далее, а тупиковыми являются точки А, D, I, J.
Можно сказать, что площадка Y является достижимой из площадки X, если имеется путь от X к Y через промежуточные коридоры и площадки. Если говорить точнее, то или X и Y являются смежными площадками, или есть последовательность площадок X1, X2, ... Xn таких, что X и X1, X2 и Х3, .., и так далее, и, наконец, Xn и Y будут смежными. Необходимо отметить, что если площадка Y является достижимой из X, то она будет являться достижимой и при посредстве простого пути, то есть, такого пути, в котором все площадки, а также и все коридоры, должны проходиться только по одному разу. К примеру, путь ABCD может считаться простым, а путь ABCFECD таковым не является.
Тезею предстояло решить следующую задачу, а именно, является ли достижимой площадка М, на которой расположен Минотавр, из площадки А, на которой располагается Ариадна, или нет. В случае, когда ответ «да», то к М можно будет добираться по любому пути, а возврат к площадке А необходимо уже выполнять по простому пути. Так как устройство лабиринта заранее является неизвестным, то решение задачи следует представить в виде общей методики поиска для любого лабиринта и при любом расположении площадок А и М. Это означает, что необходимо сформировать алгоритм поиска пути в лабиринте.
Введем следующие обозначения, коридоры, которые являются не пройденными ни разу, пометим зеленой краской, те коридоры, которые пройдены один раз, пометим желтой краской, а коридоры, пройденные два раза, пометим красной краской.
Располагаясь на исходной площадке, Тезей способен переместиться на одну из смежных площадок при помощи одного из следующей пары ходов:
- Осуществляя разматывание нити. Можно пройти от исходной площадки по любому из зеленых коридоров до смежной площадки. После того как пройден этот коридор, он должен считаться желтым.
- Осуществляя наматывание нити. Можно вернуться от исходной площадки по последнему пройденному желтому коридору до смежной площадки. При этом нить должна наматываться обратно на клубок, а этот коридор должен стать красным.
Следует предположить, что Тезей оставляет какие-либо метки, которые позволяют ему в дальнейшем отличить красные коридоры от зеленых, а желтые коридоры имеют отличительный признак в виде протянутой по ним нити Ариадны.
Состояние на текущей площадке, где в какой-то момент располагается Тезей, может быть охарактеризовано следующими признаками:
- Наличие минотавра, то есть, его обнаружили.
- Наличие петли, то есть, через эту площадку уже проходит нить Ариадны. Это означает, что от этой площадки уходят, по меньшей мере, пара желтых коридоров.
- Наличие зеленой улицы, то есть, от этой площадки имеется вход по меньшей мере в один зеленый коридор.
- Наличие на этой площадке Ариадны.
- Наличие особого случая, то есть, отсутствуют все предыдущие признаки. Это, к примеру, может быть тупик. В таблице ниже приведены соответствующие каждому признаку необходимые дальнейшие ходы.
Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ
Располагаясь на какой-либо площадке, Тезей должен сделать очередной ход следующим образом. Он должен проверить по порядку номеров, какой из перечисленных признаков присутствует в настоящий момент. При обнаружении первого такого признака, он, уже без проверки остальных признаков, должен сделать необходимый ход из правого столбца. Такие ходы должны выполняться до тех пор, пока не будет достигнута остановка. Необходимо отметить, что при любом местоположении А и М в лабиринте после конечного количества ходов в любом случае должна наступить остановка или на площадке Минотавра, или на площадке Ариадны.
