Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

§3. АЛГОРИТМЫ ПОИСКА ПУТИ

ВЛАБИРИНТЕ

3.1. Лабиринты. Греческая мифология повествует о ле­ гендарном герое Тезее, который отважился проникнуть в лабиринт для того, чтобы разыскать в нем чудовищного Минотавра и убить его. Ему помогла выбраться из лаби­ ринта Ариадна, давшая Тезею клубок ниток, один конец которых держала она сама. По мере углубления Тезея в ла­ биринт клубок разматыва­ лся; наматывая потом нит­

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

Представим себе лабиринт в виде конечной системы пло­ щадок, от которых расходятся коридоры, причем каждый коридор соединяет две площадки (такие площадки будем называть смежными), но не исключается существование таких площадок, из которых можно пройти только в один коридор (такие площадки будем называть тупиками). Гео­ метрически лабиринт можно представить в виде системы точек А, В, С, ... (изображающих площадки) и совокупно­ сти отрезков АВ, ВС, ... (изображающих коридоры), со­ единяющих некоторые пары этих точек (рис. 8).

Будем говорить, что площадка Y достижима из площад­ ки А', если существует путь, ведущий от X к Учерез проме­ жуточные коридоры и площадки. Точнее, это означает, что либо X и Y — смежные площадки, либо существует после-

25

раз. В предыдущем примере путь не был простым, но, с р е ­

ясь на его поиски с площадки А, на которой его ждет Ариад­ на, должен решить след>ющую задачу: требуется выяснить, достижима ли М из Л или нет*'. Если достижима, то нужно добраться до нее по какому бы то ни было пути, но вернуть­ ся к Ариадне нужно уже по п р о с т о м у п у т и . Если же М недостижима, то вернуться к Ариадне.

Различных лабиринтов может быть бесчисленное мно­ жество, а взаимное расположение в данном лабиринте пло­ щадок А и М также можно варьировать. Поскольку Тезею заранее ничего не известно об устройстве данного лабирин­ та и о местонахождении в нем Минотавра, то решение по­ ставленной задачи мыслится в виде общего метода поисков, пригодного при любом лабиринте и при любом расположе­ нии в нем площадок А и М. Иными словами, решение мы­ слится в виде алгоритма, решающего любую из задач дан­ ного типа.

3.2. Алгоритм поиска. Для построения такого алгорит­ ма мы рассмотрим один специальный метод поисков. На лю­ бой стадии процесса поиска в соответствии с этим методом приходится различать коридоры, еще ни разу не пройден­ ные Тезеем (условно — зеленые), пройденные один раз (желтые), пройденные дважды (красные). Далее, находясь на какой-либо площадке, Тезей может попасть на одну из смежных площадок посредством одного из следующих двух ходов:

1. Разматывание нити. Прохождение от данной пло­ щадки по любому зеленому коридору до смежной площад­ ки. При этом нить Ариадны разматывается вдоль этого ко-

*) Естественно считать, что МфА.

26

ридора, который после прохождения уже считается жел­ тым.

2. Наматывание нити. Возвращение от данной пло­ щадки по последнему пройденному желтому коридору до смежной площадки. При этом нить Ариадны, ранее размо­ танная вдоль этого коридора, обратно наматывается, а этот коридор уже объявляется красным.

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

I . Минотавр. На данной площадке обнаружен Мино­ тавр.

2: Петля. Через данную площадку уже протянута нить Ариадны; иными словами, от данной площадки расходятся

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

27

Пригодность предложенного метода непосредственно вытекает из следующих трех утверждений:

1.При любом взаимном расположении А и М в лаби­ ринте после конечного числа ходов обязательно наступит остановка либо на площадке Минотавра, либо на площадке Ариадны.

2.Если остановка наступила на площадке Минотавра, то Минотавр достижим. Более того, в этом случае нить Ариадны оказывается протянутой по простому пути, веду­ щему от А до М; наматывая нить, Тезей может теперь вер­ нуться по этому лутн к Ариадне.

3.Если остановка наступила на площадке Ариадны, то Минотавр н е д о с т и ж и м.

Прежде чем доказывать эти утверждения, покажем на

начинается поиск Минотавра, который находится в F. Про­ цесс поиска в соответствии с нашим методом удобно изобра­

Мы видим, что в данном случае Минотавр достижим. Выделив в предпоследнем столбце те из коридоров, которые остались желтыми (в соответствии с показаниями послед-

28