Вычисление цели. Механизм возврата

Правило унификации.

Унификация переменных.

Установление соответствия между термами является основной операцией при вычислении цели. Она осуществляется следующим образом: на каждом шаге выбирается очередной терм и отыскивается соответствующее выражение в БД. При этом переменные получают или теряют значения. Этот процесс можно описать в терминах текстуальных подстановок: «подставить терм t вместо переменной Y». Свободными переменными в Прологе называются переменные, которым не были присвоены значения, а все остальные переменные называются связанными переменными. Переменная становится связанной только во время унификации, переменная вновь становится свободной, когда унификация оказывается неуспешной или цель оказывается успешно вычисленной. В Прологе присваивание значений переменным выполняется внутренними подпрограммами унификации. Переменные становятся свободными, как только для внутренних подпрограмм унификации отпадает необходимость связывать некоторое значение с переменной для выполнения доказательства подцели.

1. Если x и y-константы, то они унифицируемы, только если они равны.

2. Если x- константа или функция, а Y-переменная, то они унифицируемы, при этом Y принимает значение x.

3. Если x и y -функции, то они унифицируемы тогда и только тогда, когда у них одинаковые имена функций (функторы) и набор аргументов и каждая пара аргументов функций унифицируемы.

Есть особый предикат «=», который используется в Турбо-Прологе для отождествления двух термов. Использование оператора «=» поможет лучше понять процесс означивания переменной. В Турбо-Прологе оператор «=» интерпретируется как оператор присваивания или как оператор проверки на равенство в зависимости от того, являются ли значения термов свободными или связанными.

Пример 20: X=Y, если X и Y – связанные переменные, то производится проверка на равенство, например: если X=5 и Y=5, то результат ДА (истина); если X=6 а Y=5, то результат НЕТ(ложь). Если одна из переменных X или Y – свободная, то ей будет присвоено значение другой переменной, для Турбо-Пролога несущественно слева или справа от знака «=» стоит связанная переменная.

Оператор «=» ведет себя точно так, как внутренние подпрограммы унификации при сопоставлении целей или подцелей с фактами и правилами программы.

Каноническая форма цели (вопроса) является конъюнкцией атомарных предикатов, то есть последовательностью подцелей, разделенных запятыми:

Q=Q₁, Q₂,…, Q_n.

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

Если некоторая подцель оказывается неуспешной, то Пролог возвращается влево и останавливается у ближайшего указателя возврата. С этой точки Пролог начинает попытку найти другое решение для неуспешной цели. До тех пор, пока следующая цель на данном уровне не будет успешной, Пролог будет повторять возврат к ближайшему указателю возврата. Эти попытки выполняются внутренними подпрограммами унификации и механизмом возврата.

Алгоритм вычисления цели – частный случай правила резолюции применительно к дизъюнктам Хорна. Вопрос Q является правилом без заголовка, аналогом выражения ШQ, то есть Q®Л. Пусть D – база данных (множество дизъюнктов). На вопрос Q, следует найти такую подстановку s, для которой множество s[DИ(ШQ)] невыполнимо. Стратегия выбора очередной пары дизъюнктов для резолюции здесь очень проста: подцели и предложения просматриваются в текстуальном порядке.

Пример 21: пусть есть БД семья:

1. мать (екатерина, юлия).

2. мать (екатерина, анастасия).

3. мать (мария, петр).

4. мать (анна, екатерина).

5. отец (петр, юлия).

6. отец (петр, анастасия).

7. отец (антон, петр).

8. отец (андрей, екатерина).

9. дед (X, Y): - отец(X, Z), мать(Z, Y).

10. дед (X, Y): - отец(X, Z), отец(Z, Y).

11. бабка (X, Y): - мать(X, Z), мать(Z, Y).

12. бабка (X, Y): - мать(X, Z), отец(Z, Y).

Зададим сложную цель:

Q₁, Q₂ = отец(X, Y), мать(екатерина, Y).

Подцель Q₁= отец(X, Y) соответствует пятому предложению БД:отец (петр, юлия). Это дает подстановку s₁={X=петр, Y=юлия}. Затем найденная подстановка применяется к s₁[Q₂]= мать(екатерина, юлия). Этой подцели соответствует 1 предложение БД, что дает пустую подцель, следовательно ответ найден: X=петр, Y=юлия.

Для получения нового ответа в БД ищется новая унификация для s₁[Q₂]. Так как в БД нет соответствующего предложения, то вычисления прекращаются, система вновь рассматривает последовательность Q₁, Q₂ и для Q₁ ищется новая унификация в БД, начиная с 6 предложения. Это и есть возврат. Шестое предложение сразу же дает желаемую унификацию с подстановкой s₂={X=петр, Y=анастасия}. Вновь найденная подстановка применяется к s₁[Q₂]= мать(екатерина, анастасия). Этой подцели соответствует 2 предложение БД. Далее указанная процедура повторяется и в итоге имеем:

Цель: отец(X, Y), мать(екатерина, Y).

2 решения: X=петр, Y=юлия

X=петр, Y=анастасия.

Дата добавления: 2015-06-27