Методы поиска решений на основе исчисления предикатов - часть 4

Предполагается, что X(smart(X)=¬stupid(X)) и Y(wealthy(Y)=¬poor(Y)). В третьем столбце таблицы записаны дизъюнкты.

Таблица 3.2. Интересная жизнь

Утверждения и заключениеПредикатыПредложения(дизъюнкты)1. Все небедные и умные люди счастливы2. Человек, читающий книги, - неглуп3. Джон умеет читать и является состоятельным человеком4. Счастливые люди живут интересной жизнью5. Заключение: Существует ли человек, живущий интересной жизнью?6. Отрицание заключения

X(¬poor(X) smart(X) happy(X))	poor(X) ¬smart(X) & happy(X)
Y (read(Y) smart(Y))	¬read(Y) & smart(Y)
read(John) ¬poor(John)	3a read(John) 3b ¬poor(John)
Z (happy(Z) exciting(Z))	¬happy(Z)&exciting(Z)
W(exciting(W))	exciting(W)
¬ W(exciting(W))	¬exciting(W)

Отрицание заключения имеет вид (строка 6): ¬

W(exciting(W))

Одно из возможных доказательств (их более одного) дает следующую последовательность резольвент:

1. ¬happy(Z)резольвента 6 и 4

2. poor(X)

   
   ¬smart(X)резольвента 7 и 1

3. poor(Y)

   
   ¬read(Y)резольвента 8 и 2

4. ¬read(John)резольвента 9 и 3b

5. NILрезольвента 10 и 3a

Символ NIL означает, что база данных выражений содержит противоречие и поэтому наше предположение, что не существует человек, живущий интересной жизнью, неверно.

В методе резолюции порядок комбинации дизъюнктивных выражений не устанавливался. Значит, для больших задач будет наблюдаться экспоненциальный рост числа возможных комбинаций. Поэтому в процедурах резолюции большое значение имеют также эвристики поиска и различные стратегии. Одна из самых простых и понятных стратегий - стратегия предпочтения единичного выражения, которая гарантирует, что резольвента будет меньше, чем наибольшее родительское выражение. Ведь в итоге мы должны получить выражение, не содержащее литералов вообще.

Среди других стратегий (поиск в ширину (breadth-first), стратегия "множества поддержки", стратегия линейной входной формы) стратегия "множества поддержки" показывает отличные результаты при поиске в больших пространствах дизъюнктивных выражений [2].

Содержание  Назад  Вперед