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

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

11.4. ЛАБИРИНТ

665

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

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

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

ставление фиксирует информационную и концептуальную структуру, кото-

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

стороны процесса разработки программы:

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

числений, т. е. алгоритма решения задачи, с помощью подходящих язы-

ковых средств;

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

щью тех же средств конкретного представления, т. е. обеспечена воз-

можность отражения в интерфейсе самой этой структуры данных, хода

вычислений и получаемых результатов.

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

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

вающих независимость реализации алгоритма и его интерфейса.

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

работчика. Среди критериев предпочтения — удобство и эффективность ре-

ализуемых на этом уровне алгоритмов и возможность простой реализации

различных конкретных представлений. Понятно, что на выбор абстрактно-

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

как для описания структуры данных, так и для оперирования ею. Этот выбор

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

универсальности конструируемой программы (к расширению класса задач,

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

эффективной специализации программы. При разрешении этого противоре-

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

поэтому на выбор решиня часто влияет возможность переиспользования уже

существующего программного обеспечения. Но здесь возникает другое про-

блемное противоречие, поскольку слишком часто уже существующее обес-

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

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

заменить при переходе от абстрактного к конкретному представлению). По-

этому можно дать совет:

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

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

666

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

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

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

Полезно сопоставить представления данных с рассмотренными ранее по-

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

Мы выбирали понятие абстрактного синтаксиса, исходя лишь из потребно-

сти описания работы абстрактного вычислителя языка. Это как раз то, что

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

конкретному программному тексту. Таким образом, абстрактно-синтаксиче-

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

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

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

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

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

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

поэтому они концептуально согласованы.

11.4.3. Абстрактное представление лабиринта

Конкретизируя данное в предыдущем разделе определение изоморфно-

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

биринтов.

Определение 11.4.1. Два лабиринта называются изоморфными, если меж-

ду множествами их комнат и дверей можно установить взаимно-однозначное

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

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

го лабиринта соединяются соответственной дверью.

Конец определения 11.4.1.

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

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

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

кие цели преследуются при решении задачи блуждания.

Для иллюстрации на рис. 11.8 предлагаются два изоморфных лабиринта,

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

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

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

ность изображения комнат, стенок и дверей на рис. 11.8б пунктиром показа-

ны разделительные линии между комнатами.

11.4. ЛАБИРИНТ

667

а) Лабиринты без разметки

1 2 3 4 5 6 7 8

18 19

б) Лабиринты с разметкой

Рис. 11.8. Два изоморфных лабиринта

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

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

биринтов нахождение пути между комнатами достигается с помощью одного

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

может существенно различаться.

Что нужно для такой унификации решения задачи блуждания?

Абстрактное представление лабиринта — это программистское отраже-

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

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

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

668

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

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

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

жать абстрактное решение в изображениях лабиринта.

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

чает,во-первых,выбор конкретной структуры данных,реализующей абстракт-

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

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

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

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

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

ничений либо требований совместимости с какой-то другой системой.

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

жения, характеризирующие абстрактное представление лабиринта:

1. набор комнат лабиринта — это двумерный массив

Rooms

, соседство

элементов которого отражает соседство комнат в конкретном предста-

влении лабиринта;

2. комнаты идентифицируются парой индексов массива

Rooms

;

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

которых в массиве отличаются на единицу, а число дверей комнаты —

не более четырех (следствие предыдущих положений);

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

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

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

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

щими дверями);

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

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

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

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

в направлениях роста идентифицирующих индексов: запрет на переход

вправо (

) и запрет на переход вниз (

);

6. для унификации вычисления возможности перейти влево (противопо-

ложное

направление

) и вверх (противоположное

направление

), массив

Rooms

дополняется рядом и колонкой фиктивных комнат

11.4. ЛАБИРИНТ

669

с нулевым соответствующим индексом. Этим комнатам принудительно

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

для ряда и

запрета на переход

для колонки, соответственно. Их нельзя указы-

вать в качестве начальной или конечной комнат для блуждания;

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

ственно,

;

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

Way

, который со-

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

Lway

— длиной пути;

9. для отражения хода вычислительного процесса поиска пути в лабирин-

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

Inf

, который коди-

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

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

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

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

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

Inf

на изображение лабиринта с пометками у

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

В соответствии с данными положениями, абстрактное представление лаби-

ринта, принимаемое для решения поставленной задачи, на реализуется на

языке

Turbo Pascal

описаниями, приводимыми ниже. Для простоты и в со-

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

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

максимально возможные числа комнат в лабиринте по горизонтали —

MaxX

и вертикали —

MaxY

; фактические размеры лабиринта задаются переменны-

ми

. Дополнительные описания вспомогательного характера приво-

дятся без пояснений.

Программа 11.4.1

const MaxX = 20;

MaxY = 20;

MaxXY = MaxX * MaxY;

type Troom = record Rt, Dn : Boolean;

Inf : Integer;

end;

Tdir = ( Lf, Rt, Up, Dn );

670

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

{

направления возможных переходов из комнаты

}

TmaxX = 0 .. MaxX;

TmaxY = 0 .. MaxY;

TRooms = array [ TMaxX, TMaxY ] of Troom;

TRoomIndex = record

Col : TmaxX;

Row : TmaxY;

end; var Rooms : TRooms; {

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

}

bX : TMaxX; {

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

}

bY : TMaxY;

eX : TMaxX; {

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

}

eY : TMaxY;

mX : TMaxX; {

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

}

mY : TMaxY;

Way : array [ 1 .. MaxXY ] of TroomIndex;

{

представление пути в лабиринте

}

Lway : 0 .. MaxXY; {

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

}

function isWay ( X : TMaxX; Y : TMaxY; dir : TDir ): Boolean;

{

функция проверки отсутствия запрета на переход из комнаты

}

{ X, Y

по направлению

dir }

begin

case dir of

Lf : isWay := Rooms [ X - 1, Y ].Rt;

Rt : isWay := Rooms [ X, Y ].Rt;

Up : isWay := Rooms [ X, Y - 1 ].Dn;

Dn : isWay := Rooms [ X, Y ].Dn;

end

end;

В этом описании специального комментария требуют фрагменты, связанные

с понятием направления возможных переходов: имена первых двух полей

типа

Troom

(

),значения перечислимого типа

Tdir

(

),а также

функция

isWay

Само понятие направления можно рассматривать с формальной точки зре-

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

рядочивает их и стандартизирует их обозначения. Ничто не препятствует

определению и другого числа дверей, и другого упорядочивания. С другой

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

11.4. ЛАБИРИНТ

671

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

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

ного лабиринта, в котором комнаты разбивают прямоугольник на квадрат-

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

отражено в обозначениях.

Что касается функции

isWay

, то ее назначение — нивелировать различия

проверки возможности перемещения по разным направлениям. В рамках ис-

ходной постановки задачи открытость двери не зависит от направления, в

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

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

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

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

дверей вычисляется. Именно это и делает функция

isWay

. Для упрощения ал-

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

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

TmaxX

TmaxY

описываются как отрезки целых, начинающиеся с нуля (а не

с единицы). В результате пограничные (из первой строки и первого столбца)

комнаты перестают быть исключительными.

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

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

полагаются в одной плоскости) с дверями, ориентированными по сторонам

света

и допускающими переходы в обе стороны. Возможно модифициро-

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

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

сла пройденных комнат и других условий), но здесь это не делается.

Для работы с данным абстрактным представлением необходимо преду-

смотреть алгоритмы очистки (ликвидации стенок и пометок комнат)—

ClearRooms

и инициализации лабиринта (расстановка стенок) —

InitRooms

. В данном ре-

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

вероятностью, равной константе

. Переменные

передаются про-

цедурам

ClearRooms

InitRooms

через общий контекст. Их значения долж-

ны быть заданы до вызова этих процедур. Отрисовка и стирание лабиринта,

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

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

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

компасом. Так что ориентация по сторонам света — термин дискретной математики и не

имеет никакого отношения к фактической ориентации комнат.

672

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

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

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

и инициализацией.

Программа 11.4.2

const p = 0.5;

procedure ClearRooms;

var Col, Row : Integer;

begin

for Col := 0 to mX do

for Row := 0 to mY do

begin Rooms [ Col, Row ].Rt := True;

Rooms [ Col, Row ].Dn := True;

Rooms [ Col, Row ].Inf := 0;

end;

bX := 0; eX := 0;

bY := 0; eY := 0;

end;

procedure InitRooms;

var r : Real;

Col, Row : Integer;

begin

ClearRooms;

for Row := 1 to mY do

begin for Col := 1 to mX do

begin r := Random;

Rooms [ Col, Row ].Rt := r > part;

r := Random;

Rooms [ Col, Row ].Dn := r > part;

end;

Rooms [ 0, Row ].Rt := False;

Rooms [ 0, Row ].Dn := True;

Rooms [ mX, Row ].Rt := False;

end;

for Col := 1 to mX do

11.4. ЛАБИРИНТ

673

begin Rooms [ Col, mY ].Dn := False;

Rooms [ Col, 0 ].Dn := False;

Rooms [ Col, 0 ].Rt := True;

end;

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

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

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

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

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

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

Rooms

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

procedure CloseRtRoom ( Col : TMaxX; Row : TmaxY );

begin

Rooms [ Col, Row ].Rt := False;

end;

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

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

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

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

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

ний.

Заметно, что лабиринты, порождаемые процедурой

InitRooms

, при кон-

кретном представлении не очень “красивы”. Причина тому — слишком рав-

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

дверей. Это недостаток выбранного абстрактного представления, а точнее —

алгоритма его инициализации. Исправление его — еще одна задача для са-

мостоятельного решения.

11.4.4. Поиск пути в лабиринте

В настоящем разделе обсуждается построение алгоритма поиска пути в

лабиринте методом перебора/генерации вариантов с возвратами. В данном

случае рассматривается вариант задачи перебора,описанный в п.3на стр.647,

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

ходе от комнаты к комнате. Если такая последовательность ведет к конечной

674

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

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

отвергается. Как уже отмечалось, все ситуации можно свести друг к другу. В

качестве иллюстрации ниже будет показано такое сведение.

Как и в задаче о раскраске, множество возможных вариантов строится на

базе отношения соседства: комната считается соседней к данной, если в нее

ведет дверь. Порядок рассмотрения соседних комнат может быть любой. На-

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

части в соответствии со следующим соотношением. Если вычисление неко-

торой процедуры

Find

с параметрами

начX

начY

конX

конY

приводит к

нахождению пути из комнаты

начX

начY

в комнату

конX

конY

, то два после-

довательных ее вызова

Find ( bX, bY, X, Y ); Find ( X, Y, eX, eY );

(11.2)

приводят к нахождению требуемого пути как объединения двух полученных

последовательностей.

Непосредственное использование идеи разбиения, представленное функ-

цией

Программа 11.4.3

function FindWay1 (bX: TMaxX; bY: TMaxY; eX: TMaxX; eY: TMaxY): Boolean;

begin

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

then FindWay1:= True

else if isWay ( bX, bY, Lf )

then FindWay1:= FindWay ( bX - 1, bY, eX, eY )

else if isWay ( bX, bY, Rt )

then FindWay1:= FindWay ( bX + 1, bY, eX, eY )

else if isWay ( bX, bY, Up )

then FindWay1:= FindWay ( bX, bY - 1, eX, eY )

else if isWay ( bX, bY, Dn )

then FindWay1:= FindWay ( bX, bY + 1, eX, eY )

else FindWay1:= False

end;

не годится, но совсем не потому, что здесь нарушена схема (11.2). По су-

ществу схема сохраняется, просто первый вызов

Find(bX, bY, X, Y)

в целях

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

дующего возможного варианта.