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

него столбца), получим следующий простой путь, ведущий от А к F:

/С, то процесс поиска можно изобразить в схеме, представ­

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

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

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

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

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

29

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

п-го хода, после п-го хода имеются следующие возможно­ сти:

2.Петля. Тезей наматывает нить, т. е. отступает по жел­

тому коридору КА„-г, который теперь уже становится красным. Желтый путь укорачивается па один коридор; если число s коридоров в прежнем пути было больше 1, то после п-го хода будет иметь место случай б с (s — 1) желты­ ми коридорами; если же s = 1, то будет иметь место слу­ чай а.

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

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

дит наматывание нити, которое приводит так же, как и в слу­ чае петли, к случаю а (при s = 1) или к случаю б (при s > 1).

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

Доказательство утверждения 2. В случае остановки на площадке Минотавра факт достижимости очевиден, причем

30

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

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

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

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

Л к М. Первый коридор в этом пути является красным, ибо он выходит из Л, последний же является зеленым, ибо Те­

коридоры. Рассмотрим теперь последнее прохождение Тезея через площадку Л; ; оно, очевидно, произошло по одно­

оно было вызвано либо наличием петли, либо пятым случаем, т. е. отсутствием всех четырех признаков. Однако послед­

прохождение через Ai было связано с обнаружением петли. Однако это немедленно приводит к противоречию, чем и завершается доказательство утверждения 3. Именно, если бы в Л; была обнаружена петля, то это означало бы, что из нее выходят по крайней мере два желтых коридора. Сде­ лав свой очередной ход, Тезей превратил бы один из этих желтых коридоров в красный, оставшийся же желтый кори­ дор должен быть обязательно пройден впоследствии повтор­

31

допущению, что рассматривается последнее прохождение

через Аг.

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

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

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

32