Интеллектуальные робототехнические системы

Методы поиска решений на основе исчисления предикатов - часть 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].


Начало  Назад  Вперед