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

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

11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ

645

первоначальную текущую. Будут полезны при этом и программные экспери-

менты.

ААА

а) область не закраситсяа) область не закрасится б) область закрасится

незакрашиваемое

Рис. 11.2. Иллюстрация решения задачи о закраске области

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

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

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

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

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

Сложность разбиения действий для выбранного разбиения данных различна.

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

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

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

лось. Пожалуй, это самый простой случай рекурсии. Следующий, чуть более

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

ную и итеративную схемы (см. п. 8.7.1). Здесь вся сложность прямо связано

со сложностью и с избыточностью рекуррентного соотношения.

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

торые используются для перебора и генерации вариантов. Методы организа-

ции таких программ обсуждаются в следующем параграфе.

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

В практике программирования зачастую приходится решать задачи, в ко-

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

646

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

ребора — это цикл, каждая итерация которого выделяет вариант данных для

конкретной обработки.Вложенные циклы позволяют выделять все пары,трой-

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

A [1..N]

в цикле

for i := 1 to N do

for j := 1 to N do

for k := 1 to N do ...

индексы

, и

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

троек

(A [i], A [j], A [k])

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

менты массива

. Для перебора элементов без их повторения целесообразно

использовать цикл

for i := 1 to N - 2 do

for j := i + 1 to N - 1 do

for k := j + 1 to N do ...

Однако циклическая схема далеко не всегда применима. Например, для

генерации последовательностей кортежей 1 6

6 N,

(A [i1]),

(A [i1], A [i2]),

...

(A [i1], A [i2], ..., A [im])

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

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

определена статически. Не работает циклическая схема и тогда, когда не уда-

ется алгоритмически явно сформулировать условия окончания циклов.

11.3.1. Перебор/генерация вариантов с возвратами

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

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

ми. Суть его состоит в следующем. Определяется множество возможных, но

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

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

ванием неудовлетворительных вариантов. При нахождении неудачного вари-

анта происходит возврат к предыдущему варианту и попытка перейти от него

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

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

11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ

647

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

вается рекурсивный просмотр всех вариантов.

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

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

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

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

Однако для применения метода это не очень существенно, поскольку в лю-

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

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

вариантам. Именно это обстоятельство отражено в названии метода

Выделяются четыре ситуации использования метода перебора/генерации

вариантов с возвратами:

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

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

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

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

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

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

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

варианта нужно восстанавливать предыдущее состояние решения;

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

предыдущем случае, для всех возможных последовательностей не от-

вергаемых вариантов.

Теоретически все эти ситуации можно свести к последней с помощью

надлежащей конкретизации понятий варианта, решения и упорядоченности,

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

применения метода, а не сводить их к единой схеме. Более важно задать хо-

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

и вычисления порядка перебора его элементов. Так, в первой ситуации для

упрощения алгоритмов возможно дублирование вариантов, а во второй оно

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

риантов, чем это определяется постановкой задачи. Важно помнить, что и

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

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

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

648

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

Метод перебора/генерации вариантов не исключает случаи, когда полу-

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

вариантов гарантирует, что решение данной задачи не существует.

Для пояснения данного метода на рис. 11.3 представлена схема работы

— множество возможных

…

— нерассмотренные варианты

…

EE F

I II

Рис. 11.3. Схема выполнения перебора вариантов в методе перебо-

ра/генерации возможных вариантов с возвратами

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

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

A, B, C

, D

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

оказалась отвергнутой последовательность

A, B, C

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

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

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

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

11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ

649

(т. е.выбор варианта C

был неудачным). Очередным следующим для Bявля-

ется вариант C

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

текущего варианта в состоянии I. Следующим для D является вариант E, к

которому происходит переход при смене состояния.

В состоянии II последовательность

A, B, C

, D, E

— текущая последовательность, а

A, B, C

, E, F

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

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

в рассмотре-

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

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

то происходит возврат в состояние II (эти действия на схеме не показаны).

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

гается и он. Происходит возврат к текущему варианту D в состоянии I (серая

стрелка на рис. 11.3). Для D определен единственный следующий вариант,

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

врат к C

. Этот вариант также отвергается, и текущим снова становится B, а

следующим — C

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

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

ние рекурсии. В качестве иллюстрации этого утверждения и для демонстра-

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

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

элементов некоторого массива

A[1..N]

(

[

], . . . ,

[

])), 1 6

6 N.

Представленные фрагменты программ работают в контексте следующих опи-

саний:

const N = 4; {

значение

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

}

type TVariants = array [1..N] of Integer;

var Variants : TVariants;

650

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

procedure Handle (var V : TVariants; K : Integer );

var i: Integer;

s: string;

begin

s := ”;

for i := 1 to K do

s := s + Str ( V [i] ) + ’ ’;

writeln ( s );

end;

Процедура

Handle

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

торый представляется массивом (

) и переменной (

используется для

передачи кортежа индексов, а

— для хранения его длины.

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

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

Select

), а переход от вари-

анта к варианту — это просто увеличение на единицу значения компоненты

кортежа или его длины. Инициация процесса осуществляется следующими

операторами:

Variants [1] := 1;

Select ( Variants, 1 )

Первая версия процедуры

Select

является некорректной.

Программа 11.3.1

procedure Select ( V : TVariants; K : Integer );

begin

Handle( V, K );

if V [ K ] < N

then begin V [ K ] := V [ K ] + 1;

Select ( V, K );

end

else if K < N

then begin K := K + 1;

V [ K ] := 1;

Select ( V, K ); {*}

end

end;

11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ

651

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

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

тежа меньшей длины (см. строку

{*}

). В результате выполнения процедуры

будут напечатаны не все варианты:

4 1

4 2

4 3

4 4

4 4 1

...

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

щью другого порядка следования кортежей. При постановке решаемой зада-

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

выбирать его по своему усмотрению.

Программа 11.3.2

procedure Select ( V : TVariants; K : Integer );

begin

Handle( V, K ); if K < N

then begin V [ K + 1 ] := 1;

Select ( V, K + 1 );

end;

if V [ K ] < N

then begin V [ K ] := V [ K ] + 1;

Select ( V, K );

end;

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

данной версии процедуры

Select

, передача параметра

как значения — рас-

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

вов, тогда как в данном случае этого легко избежать: достаточно увидеть,

652

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

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

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

для обсуждаемого метода. Однако в общем случае без запоминания всей ин-

формации о варианте не обойтись. Поэтому в тексте процедуры

Select

было

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

предоставить читателю.

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

сматривать как оптимизацию алгоритма. При оптимизации решения обсу-

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

ны кортежей (т. е. оставить только второй параметр процедуры). Выбор по-

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

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

зависит и порядок вывода порождаемых кортежей. Для приводимой проце-

дуры рост индексов по мере вывода происходит справа налево:

1 1

1 1 1

1 1 1 1

1 1 1 2

1 1 1 3

1 1 1 4

1 1 2

1 1 2 1

1 1 2 2

1 1 2 3

1 1 2 4

1 1 3

1 1 3 1

1 1 3 2

...

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

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

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

слений, а решение об обращении к рекурсии принимается на основе анализа

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

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

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

11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ

653

Такой подход более функционален по сути, чем операционное манипулиро-

вание элементами обстановки вычислений. На нашей задаче он может быть

продемонстрирован следующим образом.

Множество кортежей, которое должно быть построено, может быть упо-

рядочено так,как это схематически показано на рис.11.4. Схема явно выделя-

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

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

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

значением

-того элемента.

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

правления в алгоритме. В соответствии с этой идеей рекурсивная процедура

SelectF

имеет два параметра-аргумента, отвечающие за горизонтальное (

)

и вертикальное (

) направления,

∈ {1, . . . , N}. Здесь уже учтено, что

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

массив

, не требуется. Процесс порождения нового кортежа из предыдуще-

го есть присваивание значения

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

V[Ie]

. Назначение следую-

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

ниями —вызов

SelectF(Ie+1,1)

, а смена текущего

-символа —

SelectF(Ie,

k + 1 )

. В результате этих рассуждений получается программа 11.3.3, которая

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

-символ.

Программа 11.3.3

procedure SelectF( Ie, k : Integer);

begin

V [Ie] := k;

Handle ( V, Ie );

if Ie < N then SelectF( Ie + 1, 1 );

if k < N then SelectF( Ie, k + 1 );

end;

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

нен. Так, при

N = 2

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

тежей

1 1

1 2

654

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

1 …

ie-1

ie+1

…

-ый элемент

Окончания

Номера элементов в кортежах

Начало

Рис. 11.4. Схема упорядочивания кортежей