Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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





Обработка базы знаний (БЗ) методом "до первого успеха".Рассмотрим процедурудостижения некоторой обобщенной цели “установить факт” по методу "до первого успеха":

1. Если факт принадлежит базе фактов (БФ), то “успех”. В противном случае п.2.

2. Выполнить цикл обработки базы правил (БП) – п.3.

3. Если БП пуста, то “неуспех”. В противном случае п.4.

4. Рассмотреть первое правило БП (ПБП) – п.4.1.

4.1. Если все факты условия из ПБП принадлежат БФ, то пп.4.2,

4.3. Иначе – п.4.4.

4.2. Если результат действия из ПБП есть искомый факт, то

“успех”. В противном случае пп.4.3 – 4.5.

4.3. Добавить результат действия из ПБП в БФ, если его там нет.

4.4. Определить БП=БП-ПБП.

4.5. Перейти к п.2.

Пример. Рассмотрим следующую базу знаний:

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

БП: 1. K,L,M®I

2.I,L,J®Q

3. C,D,E®B

4. A,B®Q

5. L,N,O,P ® Q

6. C,H ® R

7. R,J,M ® S

8. F,H ® B

9. G ®F,

где "," между фактами условных частей правил означает логическое перемножение, а "®" - "следует"; любое правило читается как "изследует…".Задание: установить факт Q. Последовательность решения (по пунктам алгоритма): п.1: QÏБФ ® п.2 ® п.3: БП¹Æ (не пусто)® п.4: ПБП=1БП (первое правило из БП)® п.4.1: {L,M}ÏБФ ® п.4.4: новая база правил БП1=БП -1БП (остаются правила 2,…,9) ® п.4.5 ® п.2 ® п.3: БП1¹Æ® п.4: ПБП=2БП ® п.4.1: {I,L,J}ÏБФ ® п.4.4: БП2=БП1 -2БП (правила 3,…,9) ® п.4.5 ® п.2 ® п.3: БП2¹Æ ® п.4: ПБП=3БП ® п.4.1: {C,D,E}ÎБФ ® п.4.2: B¹Q ® п.4.3: новая база фактов БФ1=БФ+B ® п.4.4: БП3 = БП2 - 3БП (правила 4,…,9) ® п.4.5 ® п.2 ® п.3: БП3 ¹ Æ ® п.4:

ПБП=4БП ® п.4.1: {A,B}ÎБФ1 ® п.4.2: "успех". Очевидно, что БП рассматривается не полностью и программа не приводит к новым требованиям "установить факт".

Обработка БЗ с перебором всей БП. Алгоритм обработки поясним на примере предыдущей базы знаний с той же целью:

1. Анализ БФ на предмет наличия Q: QÏБФ.

2. Выбор правила 1БП.

3. Анализ условной части 1БП: {L,M}ÏБФ.

4. Выбор правила 2БП.

5. Анализ условной части 2БП: {I,L,J}ÏБФ.

6. Выбор правила 3БП.

7. Анализ условной части 3БП: {C,D,E}ÎБФ.

8. БФ1=БФ+B.

9. Выбор правила 4БП.

10. Анализ условной части 4БП: {A,B}ÎБФ1.

11. БФ2=БФ1+Q.

12. Выбор правила 5БП.

13. Анализ условной части 5БП: {L,N,O,P}ÏБФ2.

14. Выбор правила 6БП.

15. Анализ условной части 6БП: {C,H}ÎБФ.

16. БФ3=БФ2+R.

17. Выбор правила 7БП.

18. Анализ условной части 7БП: {R,J,M}ÏБФ3.

19. Выбор правила 8БП.

20. Анализ условной части 8БП: FÏБФ3.

21. Выбор правила 9БП.

22. Анализ условной части 9БП: GÎБФ.

23. БФ4=БФ3+F.

24. Анализ БФ3 на предмет наличия Q: "успех".

Очевидны просмотр всей БП и наращивание БФ. Увеличенная БФ может использоваться при решении других задач, следующих за рассмотренной. В рассмотренных программах при анализе базы знаний порождаются новые факты, которые приводят к порождению других новых фактов. Такие алгоритмы относятся к монотонным алгоритмам.

Обработка БЗ с ветвлением (порождение подпроблем). Алгоритм поясним на примере прежней задачи. Для установления факта Q (цель) анализируем БФ и, поскольку там нет Q, просматриваем правила и находим то действие, результат которого равен Q (2БП). Для установления факта Q требуется установить факты I, L, J (порождение подпроблем или ветвление). Факт Q называется отцом подпроблем I, L, J. Для установления факта I отыскиваем правило с результатом действия I (1БП). Факт K есть в БФ. Факты L, M отсутствуют в качестве результатов действий. Поэтому переходим к следующему правилу, содержащему результат действия Q (4БП). Факт A условной части 4БП есть в БФ. Факт B устанавливается после анализа 3БП , так как в нем {C,D,E}ÎБФ. Теперь легко устанавливается требуемый факт Q.

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

С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=инженер по эксплуатации).

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

 






Дата добавления: 2014-11-10; просмотров: 414. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.116 сек.) русская версия | украинская версия