4.10 Методы порождения объектов

Next:4.11 Порождение перестановок
Up:4 Разработка алгоритмов
Previous:4.9 Динамическое программирование

4.10 Методы порождения объектов

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

Простейший алгоритм систематического порождения объектов состоит из трех компонент: построения начального объекта, преобразования текущего объекта в следующий и условия окончания, говорящего о том, когда нужно остановиться. Этот алгоритм можно записать так:

Построить начальный объект и взять его в качестве текущего;
while ~ Условие окончания do
Вывести текущий объект;
Преобразовать объект в следующий объект
end.
Вывести текущий объект.

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

procedure ГЕНЕРАЦИЯ (var X : ОБЪЕКТ; var Y : Boolean);
begin
    if Y then Записать в начальный объект; Y := False
    else
        Преобразовать в следующий объект;
        if Выполнено условие окончания then Y := True end
    end
end;

В этой процедуре Y используется как сигнал вновь начать порождение всех объектов (вызов с Y равным True) и как сигнал о произведенном порождении последнего объекта (возврат с Y равным True).

Next:4.11 Порождение перестановок
Up:4 Разработка алгоритмов
Previous:4.9 Динамическое программирование