Тема 10.2.Решение задачи о продукции

Можно ли построить эффективную процедуру, проверяющую разрешимость задачи о продукции или (что то же самое) задачи о следствии для -формул? Процедура, описанная во второй части доказательства теоремы, является основой для следующего алгоритма, который строит множество всех продуктов, которые можно получить из исходных продуктов с помощью заданной системы технологических процессов.

Определение:Пусть– множество технологических процессов,– исходное множество продуктов.Замыканиес помощью– это множество продуктов

Приводимый ниже алгоритм ПрямаяВолна решает задачу о продукции в два этапа: на первом строится замыкание , а на втором – проверяется, входит лив это замыкание. Итак, основную роль играет алгоритм построения замыкания ЗАМЫКАНИЕ (X,F). В нём переменные СТАРЫЕ и НОВЫЕ – это множества продуктов (истинных булевых переменных). Идея построения замыкания проста: вначале исходные данные из X заносятся в НОВЫЕ. Затем работа идёт поэтапно. Перед началом каждого этапа полученные ранее НОВЫЕ передаются в СТАРЫЕ. После этого результаты всех технологических процессов, входы которых уже получены, т.е. содержатся в множестве НОВЫЕ, добавляются к этому множеству. Алгоритм завершает работу, когда на очередном этапе ничего не добавилось, т.е. нет технологических процессов, применение которых может расширить множество полученных продуктов.

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

Алгоритм замыкание(X,f)

Вход: множество технологических процессов F и множество исходных продуктов X.

Выход: множество продуктов НОВЫЕ (=Cl(X,F)).

СТАРЫЕ := ; НОВЫЕ := X;

while НОВЫЕ <> СТАРЫЕ do

СТАРЫЕ := НОВЫЕ;

ДЛЯ КАЖДОГО процесса t F ВЫПОЛНЯТЬ

if {Lt} НОВЫЕ ТО НОВЫЕ := НОВЫЕ{bt};

вернуть (НОВЫЕ).

Алгоритм ПрямаяВолна(X,y,f)

Z := ЗАМЫКАНИЕ (X,F);

if y Z\ then вернуть («ДА») else вернуть («НЕТ»).

Следующая теорема утверждает корректность приведённого алгоритма.

Теорема.Алгоритм ЗАМЫКАНИЕ(X,F) возвращает множество Cl(X,F), а алгоритм ПрямаяВолна(X,y,F) выдаёт ответ «ДА» тогда и только тогда, когда .

Пример 10.2:Рассмотрим работу алгоритма ЗАМЫКАНИЕ(X,F) на задаче полученияy = дачапо исходному множеству X = {дерево, клей, гвозди, стекло, кирпич, крыша} из примера 10.1.

В следующей таблице показаны шаги алгоритма, на которых изменяются значения переменных СТАРЫЕ и НОВЫЕ. В первом столбце этой таблицы указан номер соответствующей строки алгоритма, после строки 5 в скобках указан тот процесс, который приводит к увеличению множества НОВЫЕ.

Стр.	СТАРЫЕ	НОВЫЕ
		дерево, клей, гвозди, кирпич, крыша, стекло
	дерево, клей, гвозди, кирпич, крыша, стекло	дерево, клей, гвозди, кирпич, крыша, стекло
	- " -	дерево, клей, гвозди, кирпич, крыша, стекло, столы
	- " -	дерево, клей, гвозди, кирпич, крыша, стекло, столы, полы
	- " -	дерево, клей, гвозди, кирпич, крыша, стекло, столы, полы, окна
	дерево, клей, гвозди, кирпич, крыша, стекло, столы, полы, окна	дерево, клей, гвозди, кирпич, крыша, стекло, столы, полы, окна, стены
	дерево, клей, гвозди, кирпич, крыша, стекло, столы, полы, окна, стены	дерево, клей, гвозди, кирпич, крыша, стекло, столы, полы, окна , стены, дача

Таким образом, в данном примере построение результирующего множества НОВЫЕ, равного Cl(X,F), завершается за два этапа, а на третьем выясняется, что ничего нового в него не может быть добавлено. После этого алгоритм ПрямаяВолна(X,y,F) проверит, что дача входит в Cl(X,F), и выдаст ответ «ДА».

С точки зрения сложности вычислений недостатком алгоритма ЗАМЫКАНИЕ(X,F) является то, что на каждой итерации основного цикла в строках 2-6 в строке 4 перебираются все процессы, даже уже отработавшие, а в строке 5 на вхождение в НОВЫЕ проверяются все элементы даже те, вхождение которых в НОВЫЕ уже было установлено на предыдущих итерациях. Ниже приведен более эффективный алгоритм для построения замыкания.

На этапе инициализации в нём для каждого процесса подсчитывается число элементов ви помещается в ячейку массива СЧЕТ [], кроме того, для каждогосоздаётся список СПИСОК [] (номеров) процессов, во входы (левые части) которых входит продукт. Далее в основной части алгоритма для каждого продуктаиз множества НОВЫЕ, куда вначале помещается, и каждого процесса, в условие которого входит, из СЧЕТ [] вычитается 1. Если СЧЕТ [] становится равным 0, это означает, что все продукты изуже получены и тогда его результатдобавляется в НОВЫЕ, если его там ранее не было. Для поиска такихиспользуется СПИСОК []. Во множестве ОБНОВА хранятся уже полученные продукты из НОВЫЕ, которые ещё не использовались для запуска новых процессов. Множества продуктов НОВЫЕ и ОБНОВА реализуются булевскими массивами длины, единицы которых объединены в списки.