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

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

Об этой древней легенде напомнила сравнительно недавно автоматическая игрушка «Мышь в лабиринте», созданная американским математиком и инженером Клодом Шэнноном. В одном месте специального

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

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

Рис. 8.

Будем говорить, что площадка достижима из площадки X, если существует путь, ведущий от X к через промежуточные коридоры и площадки. Точнее это означает, что либо смежные площадки, либо существует последовательность площадок таких, что X к и, наконец, и смежны. Так, например, на рис. 8 площадка достижима из тупика А посредством пути в то время как площадка К не достижима из А. Вместе с тем, если вообще достижима из X, то она достижима и посредством простого пути, т. е. такого пути, в котором каждая площадка (а тем более и каждый коридор) проходится лишь одиц

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

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

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

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

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

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

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

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

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

3. Зеленая улица. От данной площадки есть выход по крайней мере в один зеленый коридор.

4. Ариадна. На данной площадке находится Ариадна.

5. Пятый случай. Отсутствие всех предыдущих признаков.

(см. скан)

Наш метод поиска может быть теперь задан следующей схемой:

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

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

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

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

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

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

Пример 1. Пусть с площадки А лабиринта (рис. 8) начинается поиск Минотавра, который находится в Процесс поиска в соответствии с нашим методом удобно изобразить посредством схемы (в силу произвола при выборе зеленого коридора — это лишь одна из возможных схем), представленной на таблице 1.

Таблица 1 (см. скан)

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

Пример 2. Если же поиск начинается с площадки К, то процесс поиска можно изобразить в схеме, представленной на таблице 2.

Таблица 2 (см. скан)

Мы видим, что в этом случае Минотавр недостижим.

Перейдем теперь к доказательству утверждений 1—3.

Доказательство утверждения 1. Покажем сперва методом индукции по числу ходов Тезея, что на любом этапе процесса поиска возникает следующая альтернатива (т. е. имеет место один из следующих двух случаев, взаимно исключающих друг друга):

а) В лабиринте нет желтых коридоров; при этом Тезей находится на площадке А (Ариадны).

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

Вместе с тем будет обнаружено, что Тезей никогда не проходит по красному коридору.

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

Пусть после хода имеет место случай а. Тогда очередной ход может быть либо продвижением по зеленому коридору от А до некоторой смежной площадки К (после хода возникает случай с

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

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

1. Минотавр. Происходит остановка на площадке К с сохранением прежних желтых коридоров (случай после хода).

2. Петля. Тезей наматывает нить, т. е. отступает по желтому коридору который теперь уже становится красным. Желтый путь укорачивается на один коридор; если число коридоров в прежнем пути было больше 1, то после хода будет иметь место случай желтыми коридорами; если же то будет иметь место случай а.

3. Зеленая улица. Тезей разматывает нить, т. е. продвигается по зеленому коридору, который теперь уже становится желтым. Имеет место случай желтым коридором.

4. Ариадна. Этим признаком Тезей не будет руководствоваться, ибо если он даже и вернется на площадку Ариадны, идя по желтому пути

(т. е. если то в соответствии с принятым методом поиска он должен руководствоваться признаком петля.

5. При отсутствии первых четырех признаков происходит наматывание нити, которое приводит так же, как и в случае петли, к случаю а (при или к случаю

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

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

Доказательство утверждения 3. Заметим, что в случае остановки на площадке Ариадны

1) каждый коридор лабиринта либо пройден дважды (красный коридор), либо ни разу не пройден (зеленый коридор); иными словами, нить полностью намотана (желтых коридоров в лабиринте нет).

2) все коридоры, выходящие из А, являются красными, ибо в соответствии с принятым соглашением признак Ариадна учитывается лишь в том случае, когда предшествующие ему в схеме три признака, среди которых и зеленая улица, не имеют места.

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

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

Сделаем теперь следующее замечание. В предложенном нами предписании для поиска пути допускается известный элемент случайности. Именно, при условии зеленая улица очередной ход не определен однозначно, поскольку с данной площадки могут оказаться выходы в несколько зеленых коридоров, а наше предписание не предусматривает, какой из них нужно выбрать, точнее — оно допускает произвольный случайный выбор одного из них. Тем самым нарушается свойство детерминированности, о котором в § 1 говорилось, что оно присуще всем алгоритмам. Этот элемент случайности можно было бы, однако, легко устранить (и тем самым превратить рассмотренное предписание в алгоритм) хотя бы соглашением, что при наличии нескольких зеленых коридоров выбирается коридор по некоторому правилу; например, выйдя на площадку, Тезей начинает ее обходить по часовой стрелке до появления первого зеленого коридора и далее идет по нему. Рассмотрение таких предписаний, в которых заранее предусматриваются акты случайного выбора, представляет большой теоретический и практический интерес, особенно в Современной теории игр и ее применениях к вопросам экономики.

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

Возвращаясь к предложенному алгоритму поиска (после устранения элемента случайности), следует

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

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