Глава 11. Вывод на знаниях

11.1. Схема машины вывода с просмотром знаний «вперед»

В последующих параграфах мы рассмотрим схемы машин вывода, которые используют алгоритм перебора: вперёд и назад, в глубину и в ширину, и функционируют в режимах без возврата и с возвратом. В программах схем примем следующие соглашения. Ключевое слово ВОЗВРАТ означает выход из процедуры, в которой оно находится; значение выражения, которое следует за этим словом, пересылается процедурой; в качестве выражения может использоваться вызов процедуры, которая, в свою очередь, устанавливает некоторое значение при выполнении.

Переменные, представленные в заголовке процедуры, сохраняются; в момент вызова процедуры значения переменных перед вызовом запоминаются; в момент выхода из процедуры значения переменных, которые были до ее вызова, восстанавливаются. Эти переменные являются локальными в процедуре. Некоторые переменные будут глобальными для всех процедур, например, БФ (база фактов) и БП (база правил).

Возьмем в качестве примера следующую БЗ:

БФ: A,C,D,E,G,H,K

БП:

1. K,L,M®I

2. I,L,J®Q

3. C,D,E®B

A,B®Q

L,N,O,P®Q

C,H®R

R,J,M®S

F,H®B

G®F

Левая часть каждого правила представляет собой условие - логическое умножение символических фактов, а правая часть - действие (предполагается единственным). Так, правило 1 интерпретируется следующим образом: если факты K, L и M истинны, тогда имеет место факт I; или, чтобы установить истинность факта I, достаточно доказать истинность фактов K, L и M. Все правила БЗ можно представить в виде графа И/ИЛИ (рис.11.1.).

На графе можно видеть, что если установлен E и D и C или H и F, тогда истинно B. С целью упрощения вершины C, H, J, M дублированы. На рис. 11.2. показан подграф И/ИЛИ графа на рис. 11.1, устанавливающий действие Q, когда установлены A,C,D,E.

 

Алгоритм перебора правил в режиме без возврата (ВПЕРЕД).

Этот алгоритм объединяет действия правил.

Процедура УСТАНОВИТЬ_ФАКТ (ФАКТ)

1. если ФАКТ принадлежит БФ то возврат «успех»

2. возврат ВЫПОЛНИТЬ_ЦИКЛ(БП)

Процедура ВЫПОЛНИТЬ_ЦИКЛ (ПРАВИЛА, ФАКТ, ПРАВИЛО)

1. если ПРАВИЛА пусто то возврат «неуспех»

2. ПРАВИЛО←выбор некоторого элемента из ПРАВИЛА (например, первого встретившегося)

3. ПРАВИЛА←ПРАВИЛА уменьшенное на ПРАВИЛО

4. если все факты условия из ПРАВИЛО принадлежит БФ то

Начало

4.2 если действие из ПРАВИЛО есть ФАКТ то возврат «успех»

4.3 добавить действие из ПРАВИЛО в БФ (если его там еще нет)

4.4 БП←БП уменьшенная на ПРАВИЛО

4.5 возврат ВЫПОЛНИТЬ_ЦИКЛ (БП)

Конец

5. возврат ВЫПОЛНИТЬ_ЦИКЛ (ПРАВИЛА)

Выполнение алгоритма начинается запуском процедуры УСТАНОВИТЬ_ФАКТ() правило 3 разъединяется, т.е. элементы условия сравниваются с элементами БФ, и его действие B добавляется в БФ (рис. 11.3). Далее раскрывается правило 4 и устанавливается факт Q. Следовательно, начальный вызов завершается успешно.

Алгоритм ВПЕРЁД функционируют в режиме без возврата, так как раскрытие правила никогда не заменяется другим, а результат, произведенный правилом, никогда не ставится под вопрос. Эти алгоритмы порождают новые факты, которые в свою очередь производят аналогичное, и поэтому такие алгоритмы называют монотонными.