Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 227

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 221 222 223 224 225 226 < 227 > 228 229 230 231 232 233 .. 316 >> Следующая

Выделяются четыре ситуации использования метода перебора/генерации вариантов с возвратами:
1. требуемое решение является результатом вычислений, связанных с одним из вариантов, для нахождения которого применяется перебор;
2. требуемое реение есть совокупность результатов, получаемх как в предыдущем случае, для всех не отвергаемых при переборе вариантов;
3. требуемое реение накапливается в процессе перехода от начального варианта к следуим — кадй элемент последовательности не отвергаемых вариантов вносит свой вклад в результат, а при отказе от варианта ну но восстанавливать предыдуее состояние реения;
4. требуемое реение есть совокупность результатов, получаемх как в предыдущем случае, для всех возможных последовательностей не отвергаемых вариантов.
Теоретически все эти ситуации мо но свести к последней с помоь надлеаей конкретизации понятий варианта, реения и упорядоченности, но для практических целей (как обычно) полезнее разграничивать случаи применения метода, а не сводить их к единой схеме. Более важно задать хорошие алгоритмы построения походящего множества возможных вариантов и вычисления порядка перебора его элементов. Так, в первой ситуации для упроения алгоритмов возмо но дублирование вариантов, а во второй оно не допускается, иногда полезно рассматривать более ирокое мно ество вариантов, чем это определяется постановкой задачи. Важно помнить, что и тогда, когда решение не зависит от порядка перебора вариантов, конкретный порядок мо ет суественно влиять на время получения результата3.
Для тех, кто изучал достаточно продвинутый курс логики. Семантические (аналитиче-
3
648
ГЛАВА 11. МЕТОДЫ, ОСНОВАННЫЕ НА РЕКУРСИИ
Метод перебора/генерации вариантов не исключает случаи, когда получить решение не удается, но тогда полный просмотр множества возможных вариантов гарантирует, что решение данной задачи не существует.
Для пояснения данного метода на рис. 11.3 представлена схема работы
Ci
чСс—і / В.
I
множество возможных
вариантов
О
—— отношение порядка вариантов і—у — переход к новому варианту ^ ^ZZI — возврат к прежнему варианту •
нерассмотренные варианты
рассматриваемые варианты текущий вариант отвергнутые варианты
Рис. 11.3. Схема выполнения перебора вариантов в методе перебора/генерации возмо ных вариантов с возвратами
переборного алгоритма. Ниже приводятся пояснения к схеме. В состоянии I последовательность вариантов
A, B, C2, D
является текущей последовательностью рассматриваемых вариантов .При этом оказалась отвергнутой последовательность
A, B, Ci
ские) таблицы для классической логики высказываний являются недетерминированным алгоритмом проверки ывысказываний, приводящим к результату при любой последовательности действий. Но Вы могли сами убедиться на практике, насколько сильно зависят размер и сложность структуры строения таблицы от избранного порядка действий.
11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ
649
(т. е. выбор варианта Ci был неудачным). Очередным следующим для B является вариант C2, который принимается и приводит к варианту D в качестве текущего варианта в состоянии I. Следующим для D является вариант E, к которому происходит переход при смене состояния. В состоянии II последовательность
A, B, C2, D, E
— текуая последовательность, а
A, B, C2, E, F
— одна из возмо ных следуих (числове пометки на стрелках обозначат порядок рассмотрения следуих вариантов). Вариант Ci в рассмотрении не участвует, т. к. он уже был пройден ранее.
Если на каком-то шаге вычислений вариант F оказывается отвергнутым, то происходит возврат в состояние II (эти действия на схеме не показан ). Если в этом состоянии все следующие для E варианты отвергаются, то отвергается и он. роисходит возврат к текуему варианту D в состоянии I (серая стрелка на рис. 11.3). Для D определен единственный следующий вариант, оказавийся отвергнутым, поэтому D так е отвергается и происходит возврат к C2. Этот вариант также отвергается, и текущим снова становится B, а следующим — C3.
з приведенной схемы видно, что для реализации алгоритмов по методу перебора/генерации возможных вариантов хорошо подходит использование рекурсии. В качестве иллстрации этого утвердения и для демонстрации некоторх сло ных моментов, связаннх с обсу даемым методом, ни е рассматривается способ построения мно ества индексов для всех корте ей элементов некоторого массива A[1..N]
(A[ii], А[І2],..., A[ik])), 1 < ik < N.
редставленные фрагментыпрограммработа тв контексте следуихопи-саний:
const N = 4; { значение N выбрано для определенности } 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 дает возможность вывода построенного варианта, который представляется массивом (V) и переменной (K), V используется для передачи кортеа индексов, а K — для хранения его длины.
дея алгоритма в том, что состояние процесса перебора вариантов запоминается в параметрах рекурсивной процедуры (Select), а переход от варианта к варианту — это просто увеличение на единицу значения компоненты кортежа или его длины. Инициация процесса осуществляется следующими операторами:
Предыдущая << 1 .. 221 222 223 224 225 226 < 227 > 228 229 230 231 232 233 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100