Тема 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, это означает, что все продукты из уже получены и тогда его результат добавляется в НОВЫЕ, если его там ранее не было. Для поиска таких используется СПИСОК [ ]. Во множестве ОБНОВА хранятся уже полученные продукты из НОВЫЕ, которые ещё не использовались для запуска новых процессов. Множества продуктов НОВЫЕ и ОБНОВА реализуются булевскими массивами длины , единицы которых объединены в списки.

Алгоритм БыстроеЗамыкание(X,F)

// Инициализация:

for t F

СЧЕТ[t]:= |Lt|;

for a Lt ВЫПОЛНЯТЬ

добавить t в СПИСОК[a];

НОВЫЕ:= X; ОБНОВА:= X;

// Вычисление:

while ОБНОВА <> ВЫПОЛНЯТЬ

выбрать a ОБНОВА;

ОБНОВА:= ОБНОВА \ {a};

for t СПИСОК[a]

СЧЕТ[t]:= СЧЕТ[t] - 1;

if СЧЕТ[t] = 0 then

if {bt} НОВЫЕ then

НОВЫЕ:= НОВЫЕ {bt}

ОБНОВА:= ОБНОВА {bt}

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

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

Теорема: Алгоритм БыстроеЗамыкание(X,F) строит замыкание Cl(X,F).

Отметим, что число шагов алгоритма БыстроеЗамыкание(X,F) пропорционально размеру его входа, т.е. числу продуктов в и . Такие алгоритмы называются линейными. Действительно, при инициализации каждый элемент рассматривается 2 раза, а в основном цикле общее число рассматриваемых элементов и операций уменьшения на 1 значений СЧЕТ [ ] не больше суммы размеров всех , т.е. также не превосходит размера входа.

Пример 10.3: Рассмотрим работу алгоритма БыстроеЗамыкание на следующем примере. Пусть ={a, b, c, d, e, f, g, h}, = {b, f}, а множество состоит из следующих 6 процессов:

a, b, c, h d;

b, c, d a;

a, b e;

e, f c;

f, e d;

b, f g;

Тогда при инициализации будут построен массив СЧЕТ = [4, 3, 2, 2, 2, 2] и следующие списки:

СПИСОК[a] = (1)

СПИСОК[b] = (1, 2, 3, 6)

СПИСОК[c] = (1, 2)

СПИСОК[d] = (2)

СПИСОК[e] = (4, 5)

СПИСОК[f] = (4, 5, 6)

СПИСОК[g] = (3)

СПИСОК[h] = (1)

Множества ДОБАВКА и НОВЫЕ будут инициализированы булевскими массивами 01000100 с 1 на местах, соответствующих продуктам b и f. Дальнейшие изменения этих структур представлены в следующей таблице.

СЧЕТ	ДОБАВКА	НОВЫЕ
						abcdefgh	abcdefgh

Алгоритм завершает работу, когда множество ДОБАВКА становится пустым. В этот момент результат Cl(X,F) представлен множеством НОВЫЕ. В нашем примере оно равно {a,b,c, d,e,f,g}.

Дата добавления: 2015-10-28