ГЛАВА 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. Следовательно, начальный вызов завершается успешно.
Алгоритм ВПЕРЁД функционируют в режиме без возврата, так как раскрытие правила никогда не заменяется другим, а результат, произведенный правилом, никогда не ставится под вопрос. Эти алгоритмы порождают новые факты, которые в свою очередь производят аналогичное, и поэтому такие алгоритмы называют монотонными.