Формализованные правила

8. F, H ® B

Обработка БЗ с возвратом. Рассмотрим БЗ, состоящую из следующих строк фактов и правил:

С1: рабочий(михаил).

С2: студент(иван).

С3: отец(петр, иван).

С4: отец (михаил, петр).

С5: отец(иван, виктор).

С6: отец(, ): - сын(, ).

С7: дед(, ): - отец(, ), отец(, ).

С8: сын(михаил, юрий).,

где ": -" означает " если" а ", " между предикатами соответствует союзу " и". Пусть имеется запрос, который помещается в стек целей (СЦ):

СЦ1= дед( , ), рабочий( ).

Программа решает задачу: существуют ли такие и , что являются дедами и при этом - рабочие. Процедура поиска решения следующая.

1-й цикл. Разрешаются одна за другой две цели в СЦ1. Вначале отыскивается в БЗ пара для цели дед( , ). Сопоставление цели дед( , ) и С7 заканчивается успешно путем замены на и на , после чего оба выражения становятся идентичными. Это делает унификатор УНИФ =

= ( | , | ). Далее преобразуется содержимое СЦ1 в СЦ2 заменой цели дед( , ) посылкой (условной частью) из С7:

СЦ2= отец(, ), отец(, ), рабочий( ).

Новый СЦ является резольвентой СЦ1 и С7.

2-й цикл. Первая цель в СЦ2, т.е. отец(, ), сравнивается по очереди с С1-С8, и находится унификатор УНИФ=(петр | , иван | )для отец(, ) и С3. Первая цель нового СЦ считается решенной и удаляется из СЦ. К оставшимся целям СЦ2 применяют тот же УНИФ:

СЦ3= отец(иван, ), рабочий(петр).

3-й цикл. Цель отец(иван, ) можно сопоставить с С5 из С1-С8 через УНИФ=(виктор | ):

СЦ4= рабочий(петр).

4-й цикл. Цель рабочий(петр) вСЦ4 не сопоставляется с С1-С8. Тупик. Осуществляется возврат с восстановлением ближайшего к СЦ4 стека СЦ3, достижение первой цели которого привело к тупику (обозначим копию СЦ3 как СЦ3.1 - точка возврата ТВ):

СЦ3.1= отец(иван, ), рабочий(петр).

5-й цикл. Сопоставляется цель отец(иван, ) в СЦ3.1уже с С6 через УНИФ=(иван| ). Получаем новое состояние стека:

СЦ3.2= сын(, иван), рабочий(петр).

6-й цикл. Цель сын(, иван) в СЦ3.2не сопоставляется с С1-С8. Тупик.Возврат к ближайшему кСЦ3.2 стеку СЦ3.1:

СЦ3.1.1= отец(иван, ), рабочий(петр).

7-й цикл. Цель отец(иван, ) не сопоставляется с другими С7-С8. Тупик. Возврат к ближайшему к СЦ3.1.1=СЦ3.1=СЦ3 стеку СЦ2:

СЦ2.1= отец(, ), отец(, ), рабочий( ).

8-й цикл. Цель отец(, ) в СЦ2.1 сопоставляется уже с С4 через УНИФ=(михаил | , петр | ):

СЦ2.2= отец(петр, ), рабочий(михаил).

9-й цикл. Цель отец(петр, ) в СЦ2.2сопоставляется с С3 черезУНИФ =(иван | ), что дает

СЦ2.3= рабочий(михаил).

10-й цикл. Цель рабочий(михаил) в СЦ2.3 сопоставляется с С1. Стек становится пустым. Ответ: = михаил, = иван.

Прямая цепь рассуждений. Рассмотрим следующую базу правил:

1. Если процентные ставки =падают,

то уровень цен на бирже =растет.

2. Если процентные ставки =растут,

то уровень цен на бирже =падает.

3. Если валютный курс доллара =падает,

то процентные ставки =растут.

4. Если валютный курс доллара =растет,

то процентные ставки =падают.

5. Если процентные ставки федерального резерва =падают

и обращение федерального резерва =добавить,

то = процентные ставки падают.

С целью формализации записи правил введем следующие переменные:

INTEREST – изменение процентных ставок (рост или падение),

DOLLAR – валютный курс (падает, растет),

FEDINT – процентные ставки федерального резерва (растут, падают),

FEDMON – федеральный резерв (добавление или изъятие),

STOK – уровень цен на бирже (растет, падает).

Получим такую базу правил:

1. Если INTEREST=падает,

то STOK=растет.

2. Если INTEREST=растет,

то STOK=падает.

3. Если DOLLAR=падает,

то INTEREST=растет.

4. Если DOLLAR=растет,

то INTEREST=падает.

5. Если FEDINT=падает

и FEDMON=добавить,

то INTEREST=падает.

Образуем следующие структуры:

- список различных переменных (в условиях правил) и их значений,

- очередь переменных,

- указатели на правило и номер условия.

Введем запрос: “Если добавить денег из федерального бюджета, как будет вести себя фондовая биржа? ”. Алгоритм поиска решения методом “от причины к следствию” имеет следующий вид:

1. Определить начальное условие – причину. В нашем случае: FEDMON=добавить.

2. Занести переменную условия (FEDMON) в очередь переменных (очередь примет вид: 1. FEDMON), а ее значение (добавить) – в список переменных. Для рассматриваемого примера этот список содержит четыре переменных, из которых INTEREST и DOLLAR пока не могут иметь значения, так как меняют их в разных правилах, а FEDINT и FEDMON точно известны:

INTEREST=…

DOLLAR=…

FEDINT=падает

FEDMON=добавить.

3. Просмотреть список переменных из условных частей правил и найти ту переменную (FEDMON), которая стоит первой в очереди. Если переменная найдена, записать в указатели номер первого найденного правила (номер 5) и номер 1 условия. Если переменная не найдена - пункт 6 алгоритма.

4. Присвоить значения непроинициализированным переменным условной части найденного правила по списку переменных (FEDINT=падает) или запросить, если в списке переменных их значений нет. Проверить все условия правила (в правиле 5 два условия), отражая их номера вуказателе (вначале указатель условия будет равен 1, затем 2), и в случае их истинности (у нас оба условия истинны)обратиться к части “ то ” правила.

5. Присвоить в списке переменных значение (падает) переменной (INTEREST), входящей в часть “ то ” рассматриваемого правила, и поместить ее в конец очереди переменных (очередь: 1. FEDMON, 2. INTEREST). Пункты 3, 4, 5 повторить для других правил, в условных частях которых встречается та же переменная очереди (FEDMON, в нашем примере после 5 других правил нет).

6. Удалить переменную, стоящую в начале очереди (FEDMON).

7. Закончить процесс рассуждений, как только опустеет очередь. Если в очереди есть переменные (INTEREST), вернуться к шагу 3 алгоритма.

На шаге 3 для нашего примера переменная INTEREST встречается в правилах 1, 2. Но найденное на шаге 5 значение падает соответствует только правилу 1. Получим STOK=растет. Очередь переменных: 1. INTEREST, 2. STOK. Переменная INTEREST удаляется из очереди. Очередь: 1. STOK. Переменной STOK нет в условных частях правил, поэтому поиск завершен. Ответ: 1. Процентные ставки падают. 2. Уровень цен на бирже растет.

Обратная цепь рассуждений. Рассмотрим следующую базу правил:

Если DEGREE=нет, то POSITION=нет.

Если DEGREE=да, то QUALIFY=да.

Если DEGREE=да и DISCOVERY=да,

то POSITION=научный работник.

Если QUALIFY=да и GRADE< 3.5 и EXPERIENCE> =2,

то POSITION=инженер по эксплуатации.

Если QUALIFY=да и EXPERIENCE< 2,

то POSITION=нет.

Если QUALIFY=да и GRADE> =3.5,

то POSITION=инженер-конструктор,

где

DEGREE – ученое звание (да, нет),

DISCOVERY – открытие (да, нет),

EXPERIENCE – стаж работы,

GRADE – средний балл,

POSITION – должность,

QUALIFY – возможность принятия на работу.

Введем запрос: “Какую работу предложить данному посетителю, имеющему ученую степень, не сделавшему никакого открытия, со средним баллом 3 и стажем работы 4 года? ” Для ответа образуем структуры:

- упорядоченного списка переменных вывода (список логических выводов) с номером правила: 1. POSITION, 2. QUALIFY,

3. POSITION, 4. POSITION, 5. POSITION, 6. POSITION;

- списка неповторяющихся переменных и их значений из условных частей правил (список переменных условия), не встречающихся в следствиях, с учетом запроса:

DEGREE=да,

DISCOVERY=нет,

EXPERIENCE=4,

GRADE=3;

- стека пар указателей номеров правил и условий.

Поиск ответа методом “от цели к фактам ”имеет следующий порядок.

1. Определить неизвестную переменную логического вывода (здесь -переменная запроса POSITION).

2. В списке логических выводов искать первое вхождение этой переменной (1. POSITION). Если переменная найдена, в указатели ввести номер вхождения-правила (в нашем случае это 1) и установить номер условия 1. Если переменная не найдена, выдать “ответа нет”.

3. Присвоить значения всем переменным условий найденного правила, наращивая номера условий (для нашего примера условие одно: известно, что DEGREE=да).

4. Если в списке переменных условий какой-либо переменной найденного правила не присвоено значения и её нет в списке переменных логических выводов, запросить у оператора (в нашем случае не требуется).

5. Если какая-либо переменная условий найденного правила входит в список переменных логического вывода (в рассматриваемом примере такого нет), поместить в стек указателей номер ближайшего правила, в логический вывод которого она входит, установить номер условия 1 и перейти к шагу 3.

6. Если из правила нельзя определить значение переменной логического вывода (POSITION =?, так как в нашем примере правило 1 противоречиво), удалить соответствующий ему элемент (номер правила 1) из стека указателей и по списку переменных логического вывода продолжить поиск следующего правила (3) с этой переменной логического вывода (POSITION).

7. Если новое правило (3) найдено, заполнить стек указателей новыми данными (номер правила 3, номер условия 1) и перейти к шагу 3 (переменная первого условия правила 3: DEGREE=да, второго условия: DISCOVERY=нет). Правило 3 противоречиво. Из стека указателей удаляем номер этого правила. По списку переменных логических выводов переходим к правилу 4 и шагу 3. Переменная QUALIFY первого условия правила 4 входит в список переменных логических выводов. Добавляем в стек указателей пару “правило 2, условие 1”, сохраняя предыдущие данные - ”правило 4, условие 1”. Переходим к шагу 3: DEGREE=да, QUALIFY=да. Удаляем пару “правило 2, условие 1” из стека указателей, обрабатываем предыдущую пару “правило 4, условие 1”: QUALIFY=да. Увеличиваем номер условия: “правило 4, условие 2”: GRADE=3, т.е GRADE < 3.5. Следующее условие: EXPERIENCE=4, т.е. EXPERIENCE> =2.

8. Если переменная не найдена ни в одном из оставшихся правил в списке логических выводов, правило для предыдущего вывода неверно. Если предыдущего вывода не существует, сообщить, что “ответа нет”. Если предыдущий вывод существует, вернуться к шагу 6.

9. Определить значение переменной из правила, расположенного в начале стека логических выводов (правило 4: POSITION=инженер по эксплуатации); правило 4 из стека удалить. Если среди переменных условий есть еще переменные логического вывода (в нашем примере их больше нет), увеличить значение номера условия и перейти к шагу 3. Если в условиях больше нет переменных логического вывода, сообщить окончательный ответ (POSITION=инженер по эксплуатации).

Обратная цепь рассуждений особенно ярко демонстрирует себя в задачах, где ищется причина (причины) при известных следствиях. Пример: определить причину, по которой не заводится автомобиль.