Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

11.4. ЛАБИРИНТ

675

Это решение не подходит совсем по другой причине:

FindWay1

не рабо-

тает, так как в большинстве случаев выполнения программы путь зациклива-

ется. Он приводит к цели лишь в вырожденных случаях, например, для мни-

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

и конечной, существует ровно две двери: одна ведет в предыдущую, другая

в следующую, а для начальной и конечной — одна дверь (см. рис. 11.9). та-

кая ошибка типична при составлении рекурсивных программ. Одних толь-

ко алгебраических соотношений недостаточно для организации правильной

рекурсии, нужно помнить, что рекурсия соответствует индукции, и каждый

шаг нашей рекурсии должен уменьшать некоторый параметр, оцениваемый

значениями из фундированного чума. То, что чаще всего этот параметр явля-

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

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

Рис. 11.9. Мнимый лабиринт (Н - начальная, К - конечная комнаты)

жить число непроверенных комнат, поскольку, как и при закраске, возврат в

уже пройденные комнаты бессмысленен. Поэтому нужен запрет на перехо-

ды в комнаты, которые уже пройдены (в случае закраски он был реализован

с помощью проверки цвета пикселя). Его реализация, естественно, зависит

от абстрактного представления лабиринта.

Для предложенного выше абстрактного представления лабиринта вполне

достаточно помечать в массиве

Rooms

комнаты, которые уже пройдены (ис-

пользуется атрибут

Inf

), а путь запоминать в массиве

Way

, корректируя его

при возвратах. В качестве множества возможных вариантов здесь выступа-

ют все допустимые значения этого массива (т. е. такие последовательности

пар индексов, которые являются реальными путями) вместе со значениями

676

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

переменной

Lway

(длина пути). Переходы от одного варианта к другому ре-

гламентируются пометками в массиве

Rooms

,запрещающими зацикливание.

Ниже рассматривается альтернативная реализация: алгоритм,который не

использует массив

Way

. Иными словами, модифицируется абстрактное пред-

ставление лабиринта: из него исключается этот массив, а текущий путь со-

храняется в состояниях комнат (атрибут

Inf

), значениями которых будут:

• 0 — комната еще не посещалась;

• число из диапазона

1..mX*mY

(фактическое число комнат) —номер ша-

га текущего пути, на котором осуществляется вход в комнату (или вы-

ход из нее, если это будет удобнее для задания алгоритма);

•

MXY

— число, большее

MaxXY

, отмечает тот факт, что комната уже

посещалась (использование в качестве пометки особой ситуации зна-

чения, выходящего за диапазон осмысленных с точки зрения решения

задачи — достаточно стандартный технический прием).

Длина пути в новом абстрактном представлении лабиринта, т. е. переменная

Lway

, сохраняется.

Кодирование состояний комнат нового абстрактного представления удоб-

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

Тем не менее, абсолютное утверждение, что решение задачи без массива

Way

лучше, чем с использованием его, было бы необоснованным. В частности,

если необходимо распечатать результирующую последовательность шагов,

то решение задачи усложнится. Как станет понятно из дальнейшего, в ряде

случаев новое абстрактное представление потребует больше памяти по срав-

нению с алгоритмом, предложенным для самостоятельной работы.

Для нового абстрактного представления в качестве множества возмож-

ных вариантов выступают все допустимые значения массива

Rooms

(допу-

стимость значения определяется,как такая кодировка состояний,которая обес-

печивает возможность переходов между комнатами).Отношение порядка меж-

ду такими значениями задается следующим образом. Выбирается комната с

максимальным значением атрибута

Inf

, не превосходящим

MXY

. Пусть это

значение равно

. В качестве следующих возможных вариантов рассматри-

ваются все такие значения массива

Rooms

, которые отличаются от текущего

варианта тем, что у одной из соседних комнат, связанных с текущей комна-

той открытой дверью, значение атрибута

Inf

равно

t+1

. Иными словами, сле-

дующие варианты — это все те, которые могут быть получены из текущего

11.4. ЛАБИРИНТ

677

варианта при правильном переходе (без прохода через закрытую дверь и без

повторов) в новую комнату. Если таких комнат несколько, то все следующие

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

выбирается такой порядок перебора: сначала проверяется возможность идти

налево, затем направо, вверх и, наконец, вниз. Если следующих вариантов

нет, то текущий вариант тупиковый, и нужно вернуться в предыдущую ком-

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

Для старого абстрактного представления каждый возможный вариант —

это значение построенной последовательности пар индексов (массив

Way

и переменная

Lway

), начальным значением которой является одноэлемент-

ная последовательность с индексами, указывающими на начальную комнату.

Следующие варианты строятся из текущего после проверки, в какие сосед-

ние комнаты можно пройти, в сочетании с упорядочиванием выбора очеред-

ной следующей комнаты, если их несколько (аналогично предыдущему). Во-

прос зацикливания решается за счет выставления ненулевых значений атри-

бута

Inf

элементов массива

Rooms

для комнат, которые уже посещались.

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

может быть различна и, в частности, не обязательно связывать ее с помет-

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

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

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

представлена в текущем пути (в старом абстрактном представлении это легко

сделать, проверяя массив Way). Однако при таком решении окажется, что не-

которые из ком-нат будут посещаться неоднократно, поскольку информация

о том, что все пути из данной комнаты тупиковые, не запоминается. Именно

поэтому предпочтительнее оставлять пометки (ненулевые значения атрибу-

та

Inf

элементов массива

Rooms

) для комнат, которые уже исследованы. Это

решение верно для статических лабиринтов, т. е. таких, у которых состояние

открытия и закрытия дверей не меняется. В противном случае отмечать ту-

пиковые комнаты бесполезно (впрочем, если удастся ввести понятие полно-

стью исследованной комнаты, разумеется, зависящее от правил открывания

и закрывания дверей, то пометки таких комнат могут оказаться целесообраз-

ными).

Прямое решение задачи блуждания связывается с тем, что при переходе

от варианта к варианту текущее состояние программы запоминается полно-

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

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

переменных абстрактного представления. Проще всего это делать через па-

678

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

раметры, которые передаются рекурсивной процедуре, реализующей поиск.

Однако некоторые из переменных состояния программы не меняют своих

значений, а потому их запоминать не требуется. При выборе первого из рас-

смотренных выше абстрактных представлений требуется запоминать

Rooms

Way

Lway

. Кроме того, использование идеи разбиения, представленное вы-

ше (см. функцию

FindWay1

), предполагает запоминание начальной комнаты

пути. Для этого в

FindWay1

предусмотрены параметры

. Что каса-

ется конечной комнаты, то уместно заметить, что как в

FindWay1

, так и в

программе, которая строится ниже, запоминание ее координат избыточно:

при переходе от варианта к варианту

остаются неизменными. Тем

не менее, для повышения гибкости программы решение о передаче этих ко-

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

как осуществляется переход от варианта к варианту. Ничто не заставляет ре-

ализовывать схему (11.2), как в

FindWay1

. Возможны и переходы в обратном

направлении, т. е. от

, или даже навстречу друг другу, в обоих

направлениях, когда выбор прямого или обратного хода делается на основе

сравнения количеств доступных соседних комнат. За счет этого может замет-

но сокращаться число рассматриваемых вариантов (правда, появится необ-

ходимость восстановления пути при обратном ходе, но это не очень дорого

и достаточно просто).

При выборе абстрактного представления без

Way

запоминаются

Rooms

Lway

, а также

Что должно делаться в ходе обработки текущего варианта пути? В пря-

молинейном решении задачи блуждания требуемые действия складываются

из следующих шагов.

1. Следует проверить, не ли достигнута ли цель поиска, т. е.

(bX = eX)

and (bY = eY)

. В этом случае ничего дополнительного с текущим ва-

риантом делать не требуется, надо просто передать факт достижения

цели на уровень обработки предыдущего варианта (возможность реа-

лизации тех или иных декоративных эффектов здесь не обсуждается,

т. к. она рассматривается как часть задачи трансформации абстрактно-

го представления в конкретное).

2. Если цель поиска не достигнута, следует проверить для каждого на-

правления, достижима ли цель из соседней комнаты, связанной с теку-

щей открытой дверью. Эта проверка распадается на выяснение возмож-

ности перехода по выбранному направлению, проверку достижимости

цели из выбранной соседней комнаты и дальнейшие действия.

11.4. ЛАБИРИНТ

679

(a) Первая часть проверки достижимости в соответствии со сделан-

ными выше соглашениями задается условием:

isWay (bX, bY, <направление>)

and

(Rooms[<X координата следующей комнаты>,

<Y координата следующей комнаты >].inf = 0)

координаты следующей комнаты определяются как моди-

фикация текущих координат

, соответствующая направле-

нию.

(b) Вторая часть проверки достижимости цели требует перехода к об-

работке следующего варианта. Для этого нужно предварительно

пометить текущую комнату как исследуемую, что удобно сделать,

задав атрибуту

inf

значение очередного шага:

Rooms[<X координата следующей комнаты>,

<Y координата следующей комнаты>].inf:= Lway + 1;

подготовить новое состояние программы:

< X координата следующей комнаты >,

< Y координата следующей комнаты >,

eX, eY,

Lway + 1,

Rooms

и, запомнив текущее состояние, активизировать процесс обработ-

ки следующего варианта, который в данном случае реализуется

как рекурсивный вызов:

FindWay (< X координата следующей комнаты >,

< Y координата следующей комнаты > ],

Lway + 1, Rooms);

следующего варианта. Они связаны с анализом результата этой

обработки: если обработанный вариант принят, то и текущий ва-

риант принимается. В противном случае делается попытка прове-

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

предыдущие шаги для очередного направления, а если направле-

680

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

ния исчерпаны, текущий вариант объявляется тупиковым и отвер-

гается.

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

варианта, — подготовить обработку после возврата. В алгоритме, кото-

рый сейчас обсуждается, такая подготовка сводится к восстановлению

состояния памяти (обеспечивается возвратом из рекурсивного вызова)

и передаче сведений о результате завершаемой обработки: достигает

данный вариант цели или нет. Проще всего результат передавать по-

средством оформления алгоритма в виде функции, вырабатывающей

логические значения true и false в зависимости от достижения цели.

Представленный подход реализован функцией

FindWay2

, которая описана

ниже. Чтобы запоминание состояния программы в тексте выглядело нагляд-

нее, имена параметров выбраны в точности теми же, какие имеют перемен-

ные абстрактного представления. Но это не должно вводить в заблуждение:

все параметры передаются функции как значения, а потому каждый вызов

приводит к порождению нового комплекта переменных, инициализирован-

ных фактическими параметрами.

Программа 11.4.4

function FindWay2 ( bX : TMaxX; bY : TMaxY; eX : TMaxX; eY : TMaxY;

Lway : Integer; Rooms : TRooms ) : Boolean;

var oX : TMaxX;

oY : TMaxY;

Rslt : Boolean;

begin

if ( bX = eX ) and ( bY = eY )

then FindWay2 := true

else begin Rslt := false;

if isWay ( bX, bY, Lf ) and ( Rooms [ bX - 1, bY ] . inf = 0 )

then begin Rooms [ bX - 1, bY ] . inf := Lway + 1;

Rslt := FindWay2(bX-1,bY,eX,eY,Lway+1,Rooms);

FindWay2 := Rslt

end;

if Rslt then exit;

if isWay ( bX, bY, Rt ) and ( Rooms [ bX + 1, bY ] . inf = 0 )

then begin Rooms [ bX + 1, bY ] . inf := Lway + 1;

11.4. ЛАБИРИНТ

681

Rslt := FindWay2(bX+1,bY,eX,eY,Lway+1,Rooms);

FindWay2 := Rslt

end;

if Rslt then exit;

if isWay ( bX, bY, Up ) and ( Rooms [ bX, bY - 1 ] . inf = 0 )

then begin Rooms [ bX, bY - 1 ] . inf := Lway + 1;

Rslt:= FindWay2(bX,bY-1,eX,eY,Lway+1,Rooms);

FindWay2 := Rslt

end;

if Rslt then exit;

if isWay ( bX, bY, Dn ) and ( Rooms [ bX, bY + 1 ] . inf = 0 )

then begin Rooms [ bX, bY + 1 ] . inf := Lway+ 1;

Rslt := FindWay2(bX,bY+1,eX,eY,Lway+1,Rooms);

FindWay2 := Rslt

end

end;

Стоит обратить внимание на то, за счет чего в

FindWay2

исключается заци-

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

новом комплекте переменных весь пройденный к данному моменту путь по-

мечен номером шага (см. присваивание и рекурсивный вызов в п. 2b, кото-

рые распространяют ненулевые значения атрибута

inf

посещаемой комнаты

по глубине рекурсии). Во-вторых, принятый способ перехода от варианта к

варианту гарантирует, что всякий раз выбирается новая соседняя комната, и

пути из нее исследуются до конца, а при возврате только истинное значение

результата берется в расчет для определения того, произошло ли достиже-

ние цели. Однако это наблюдение показывает и существенный недостаток

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

но эта информация нигде не запоминается, и, таким образом, если комната

будет выбрана повторно, то повторится процесс выявления тупика (см. об-

суждение кодирования состояний комнат при выборе второго абстрактного

представления). Подобные повторения наслаиваются, и в результате эффек-

тивность программы падает.

Запоминание всех переменных состояния программы при генерации ва-

риантов при использовании второго абстрактного представления лабирин-

та делает решение не только неэффективным, но и неприемлемым. В са-

мом деле, единственный эффект вычисления

FindWay2

— это значение true

682

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

или false в зависимости от того, есть или нет путь между начальной и ко-

нечной комнатами. Здесь восстановление пути как последовательности ин-

дексов вершин потребовало бы на самом внутреннем рекурсивном вызове

осуществить обход массива

Rooms

, что явно избыточно. При использовании

абстрактного представления с массивом

Way

построенный путь запоминал-

ся бы, но и в этом случае понимаемая буквально установка на запоминание

всех переменных состояния программы привела бы к аналогичному резуль-

тату: возможность работы с найденным путем была бы ограничена самым

внутренним рекурсивным вызовом. Это мешает разграничению оперирова-

ния с абстрактным и конкретным представлениями.

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

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

рекурсивному вызову.Решению этой задачи способствует следующее наблю-

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

Rooms

.Вместо этого

можно выставлять пометку исследуемой и уже исследованной комнаты не-

посредственно в

Rooms

общего контекста. При выяснении того факта, что из

комнаты нельзя выйти к цели ее вместо значения номера шага текущего пути

ее атрибуту

Inf

следует присвоить признак исследованности:

Rooms [ bX, bY ] . Inf := MXY;

Это решает все проблемы абстрактного представления без массива

Way

. Тем

не менее,следует проанализировать и другие возможности минимизации объ-

ема запоминаемого состояния. Уже отмечалось, что включение переменных

в запоминаемое состояние сделано для повышения алгоритмической

гибкости программы. Что касается

Lway

, то эту переменную можно также не

передавать между рекурсивными вызовами, но тогда переход от шага к ша-

гу нужно смоделировать: увеличивать

Lway

на единицу перед каждым вы-

зовом и уменьшать ее после вызова. Считать ли такую модификацию целе-

сообразной, зависит от глубины рекурсии. Если исследуемые лабиринты не

очень велики, то накладными расходами (требование к памяти), связанны-

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

сления, пусть и весьма незначительные (как в данном случае) — это допол-

нительное время выполнения программы.

Окончательный алгоритм поиска пути в лабиринте представлен следую-

щей рекурсивной функцией.

Программа 11.4.5

11.4. ЛАБИРИНТ

683

function FindWay ( bX : TMaxX; bY : TMaxY; eX : TMaxX; eY : TMaxY;

Lway : Integer ) : Boolean;

var Rslt : Boolean;

begin

if ( bX = eX ) and ( bY = eY )

then FindWay := True

else

begin Rslt := False;

if isWay ( bX, bY, Lf ) and ( Rooms [ bX - 1, bY ] . inf = 0 )

then begin Rooms [ bX - 1, bY ] . inf := Lway + 1;

Rslt := FindWay(bX-1,bY,eX,eY,Lway+1,Rooms);

FindWay := Rslt

end;

if Rslt then exit;

if isWay ( bX, bY, Rt ) and ( Rooms [ bX + 1, bY ] . inf = 0 )

then begin Rooms [ bX + 1, bY ] . inf := Lway + 1;

Rslt := FindWay(bX+1,bY,eX,eY,Lway+1,Rooms);

FindWay := Rslt

end;

if Rslt then exit;

if isWay ( bX, bY, Up ) and ( Rooms [ bX, bY - 1 ] . inf = 0 )

then begin Rooms [ bX, bY - 1 ] . inf := Lway + 1;

Rslt:= FindWay(bX,bY-1,eX,eY,Lway+1,Rooms)

FindWay := Rslt

end;

if Rslt then exit;

if isWay ( bX, bY, Dn ) and ( Rooms [ bX, bY + 1 ] . inf = 0 )

then begin Rooms [ bX, bY + 1 ] . inf := Lway+ 1;

Rslt := FindWay(bX,bY+1,eX,eY,Lway+1,Rooms)

FindWay := Rslt

end

end;

if not Rslt then Rooms [ bX, bY ] . Inf := MXY;

end;

684

ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ

§ 11.5. РЕКУРСИЯ ПРИ ОБРАБОТКЕ СИМВОЛЬНОЙ ИНФОРМАЦИИ

Следующая процедура демонстрирует рекурсивное решение задачи обра-

щения символьной последовательности: требуется напечатать все вводимые

символы в обратном порядке.

Программа 11.5.1

procedure REV;

var S : Char;

begin

if not Eof

then begin

Read (S); { * }

REV; { ** }

Write(S); { *** }

end

end;

Процедура вычисляется следующим образом. Если файл ввода не пустой, то

сначала в локальной переменной

запоминается очередной входной сим-

вол (строка

{ * }

), далее порождается новый экземпляр процедуры (строка

{ ** }

, в которой указан рекурсивный вызов процедуры

REV

), а затем, т. е.

после завершения рекурсивного вызова

REV

, распечатывается запомненный

символ (строка

{ *** }

). Таким образом, алгоритм порождает одновременно

существующие экземпляры

REV

ровно в том количестве, какое необходимо

(равном числу символов файла ввода), и в той последовательности, которая

обеспечивает нужный порядок вывода (в соответствии с правилом «первым

порожден — последним завершен»).

Последний пример представлен без использования рекуррентного соот-

ношения. При желании, вводя соответствующую нотацию, такое соотноше-

ние легко составить. Его можно считать определением обращения строки.

Пусть V — алфавит входных символов, ε — обозначение пустой строки (со-

стоящей из нуля символов), A — переменная для строк. Любая непустая

строка xy . . . z (x, y, z ∈ V ) может быть записана в виде xA, где A = y . . . z.

При этих соглашениях функция R обращения произвольной строки A опре-

деляется следующим образом:

(

R(A) = ε, если A = ε;

R(xA) = R(A)x, если A 6= ε.