Решение задачи о продукции

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

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

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

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

Алгоритм ЗАМЫКАНИЕ(X,F)

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

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

1. СТАРЫЕ:= ПУСТО; НОВЫЕ:= X; 2. ПОКА НОВЫЕ!= СТАРЫЕ ВЫПОЛНЯТЬ 3. { СТАРЫЕ:= НОВЫЕ; 4. ДЛЯ КАЖДОГО процесса t принадлежит F ВЫПОЛНЯТЬ 5. ЕСЛИ {L_t} подмножество НОВЫЕ ТО НОВЫЕ:= НОВЫЕ ОБЪЕДИНИТЬ {b_t}; 6. }; 7. вернуть (НОВЫЕ).

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

1. Z:= ЗАМЫКАНИЕ (X,F); 2. ЕСЛИ y принадлежит Z\ ТО вернуть ("ДА") ИНАЧЕ вернуть ("НЕТ").

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

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

Доказательство этого утверждения фактически содержится в комментариях перед алгоритмом и его уточнение предоставляется читателю (см. задачу 6.2).

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

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

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

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

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

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

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

I) Инициализация: 1. ДЛЯ КАЖДОГО процесса t принадлежит F ВЫПОЛНЯТЬ 2. { СЧЕТ[t]:= |L_t|; 3. ДЛЯ КАЖДОГО a принадлежит L_t ВЫПОЛНЯТЬ 4. добавить t в СПИСОК[a]; 5. }; 6. НОВЫЕ:= X; ОБНОВА:= X; II) Вычисление: 7. ПОКА ОБНОВА не пусто ВЫПОЛНЯТЬ 8. { выбрать a принадлежит ОБНОВА; ОБНОВА:= ОБНОВА \ {a}; 9. ДЛЯ КАЖДОГО t принадлежит СПИСОК[a] ВЫПОЛНЯТЬ 10. { СЧЕТ[t]:= СЧЕТ[t] - 1; 11. ЕСЛИ СЧЕТ[t] = 0 12. ТО 13. ЕСЛИ {b_t} не принадлежит НОВЫЕ 14. ТО { НОВЫЕ:= НОВЫЕ объединить { b_t}; 15. ОБНОВА:= ОБНОВА объединить {b_t} } 16. } 17. }; 18. вернуть(НОВЫЕ).

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

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

Доказательство этого утверждения аналогично доказательству теоремы 6.2 (см. задачу 6.3).

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

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

1. a,b,c,h -> d;
2. b,c,d -> a;
3. g,b -> e;
4. e,f -> c;
5. f,e -> d;
6. b,f -> g.

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

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

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

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

Задачи

Задача 6.1. Докажите, что последовательность процессов в доказательстве теоремы 6.1 определена корректно, т.е. все исходные продукты каждого процесса в этой последовательности имеются перед его запуском.

Задача 6.2. Докажите теорему 6.2.

Указание. Пусть X_k - это состояние множества НОВЫЕ после k итераций основного цикла алгоритма ЗАМЫКАНИЕ в строках 2-6. Покажите, что для каждого продукта , который может быть получен из X последовательностью процессов длины k, z входит в X_k.

Задача 6.3. Алгоритм ПрямаяВолна(X,y,F) позволяет ответить на вопрос о возможности производства y из исходных продуктов X с помощью процессов F, но в случае положительного ответа не строит последовательность процессов, приводящую к y. Измените алгоритм ЗАМЫКАНИЕ (X,F) так, чтобы по его результату для любого продукта можно было построить последовательность процессов, приводящую к a.

Задача 6.4. Назовем сложным технологическим процессом (или производством)} такой процесс t, который по набору исходных продуктов L_t производит некоторое множество продуктов B_t (а не один продукт b_t). Обобщите алгоритм ЗАМЫКАНИЕ (X,F) так, чтобы он строил замыкание X относительно системы сложных технологических процессов F.

Задача 6.5. Определите, какая последовательность процессов в примере 6.3 приводит к получению a.

Задача 6.6. Используя алгоритм ЗАМЫКАНИЕ (X,F), вычислить замыкание для набора исходных продуктов X = { c,d} и следующей системы технологических процессов F:

1. a,b,d -> h;
2. a,c,d,g -> f;
3. d,g -> b;
4. e,f -> c;
5. b,k -> a;
6. d,c -> k;
7. h,d,c -> g;
8. d,g,a -> e;
9. c, d, k -> h.

Определите, какая последовательность процессов приводит к получению e.

Задача 6.7. Докажите теорему 6.3.

Указание. Пусть X_k - это состояние множества НОВЫЕ после k итераций основного цикла алгоритма БыстроеЗамыкание в строках 7-17. Покажите, что

• если на (k+1) -ой итерации основного цикла для некоторого процесса t обнаруживается, что СЧЕТ[t] = 0, то ;
• для каждого продукта , который может быть получен из X последовательностью процессов длины k, z входит в X_k;
• условие выхода из основного цикла выполнено после (k+1) -ой итерации тогда и только тогда, когда X_k= X_k+1.

Задача 6.8. Измените алгоритм БыстроеЗамыкание так, чтобы по его результату для любого продукта можно было построить последовательность процессов, приводящую к a.

Задача 6.9. Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных атрибутов X = { a,f} и следующей системы зависимостей F:

1. a,b,c -> h;
2. a,c,d,g -> h;
3. e,f -> c;
4. f,a -> d;
5. g,d -> e;
6. d,f,a -> g.

Определите, какая последовательность процессов приводит к получению h.