Запросы
Основные запросы, о которых шла речь в прошлом разделе очень легко проверить на выполнение, из кода программы. Но запросы могут обладать переменными как параметрами; такие запросы называются просто запросами(в отличие от основных запросов, которые не содержат переменных, и являются частным случаем запроса). Рассмотрим следующий запрос:
tedge(a, X)
Атом в этом запросе содержит как аргументы переменную и константу. Истинен ли этот запрос? Ну, непонятно, имеет ли смысл вообще подобный вопрос. В самом деле, если мы заменим X константой d, значит запрос истинен. Это понятие удовлетворимости. Говорят, что запрос удовлетворяется(истинен) в зависимости от программы, потому что существует подстановка для переменной, которая делает запрос истинным.
Рассуждения о этом запросе не так просты: следите за ними внимательно(выписывайте на бумажке!). Когда мы просматриваем программу мы находим правило 7, которое определяет tedge: присмотримся к этому правилу. Запрос выглядит почти как голова правила. Запишем подстановку:
Node1 = a, X = Node2
и спросим, когда tedge(a, Node2) истинен. Конечно, смысл правила подсказывает нам, что этот атом должен быть истинным, если тело правила(с теми же подстановками) также истинно. Таким образом, истинность нашего первоначального запроса может быть заменена истинностью нового запроса.
edge(a, SomeNode), edge(SomeNode, Node2)
Нам нужно проверить истинность двух атомов в нашем новом запросе. Давайте для начала рассмотрим edge(a, SomeNode). Сканируя программу, мы видим, что есть два возможных факта, которые подходят; мы возьмем первый, edge(a, b). Если мы возьмем подстановку
SomeNode = b
и применим её к нашему запросу, тогда первый атом нашего запроса удовлетворяется(удовлетворен). Теперь прокручиваем второй атом. После последней подстановки этот атом изменился и теперь он tedge(b, Node2). Проводя аналогичные рассуждения мы видим, что если взять подстановку
Node2 = d
и применить её к запросу, запрос будет полностью удовлетворен.
Весь запрос был разрешен. Если мы посмотрим на наш первоначальный запрос, мы хотим знать какие значения X удовлетворяют tedge(a, X)? Благодаря дальнейшей серии подстановок, X = Node2, Node2 = d, мы выясним, что подстановка X = d удовлетворяет первоначальному запросу.
Унификация / Резолюция
Мы можем выделить две различные сущности этого процесса(который был рассмотрен – разрешение). Унификация – это процесс, когда берется два атома(один из запроса, а второй – некий факт или голова правила в программе) и определяется, существует ли подстановка, которая делает из них одинаковый атом. Мы заглянем в алгоритм, лежащий за унификацией позднее. Второй процесс, это резолюция. Когда атом из запроса унифицировался с головой правила (или фактом), резолюция заменяет атом телом правила (или ничем, если это был факт) и затем применяет подстановку к новому запросу. Мы можем показать унификацию и резолюцию в более явном виде, снова обработав первоначальный запрос.
Первый шаг:
Унификация
tedge(a, X) и tedge(Node1, Node2),
даёт подстановку
Node1 = a, X = Node2.
Резолюция: заменяем tedge(a, X) на edge(Node1, SomeNode), edge(SomeNode, Node2) и применяем подстановку (получена выше) для получения нового запроса:
edge(a, SomeNode), edge(SomeNode, Node2)
Второй шаг:
Выбираем атом edge(a, SomeNode).
Унификация
edge(a, SomeNode) на edge(a, b),
даёт подстановку
SomeNode = b.
Резолюция: заменяем edge(a, SomeNode) ничем (потому что унифицировали с фактом) и применяем полученную подстановку для получения нового запроса:
edge(b, Node2)
Третий шаг:
Остался всего один атом в запросе.
Унификация
edge(b, Node2) и edge(b, d)
даёт подстановку
Node2 = d.
Резолюция: заменяем edge(b, Node2) ничем (потому что унифицировали с фактом). Так как результирующий запрос пуст, мы достигли конца.
Находясь здесь (на этой точки познания Prolog ( :) ) ) мы можем определить понятие подстановки. На данный момент хорошей идеей будет остановится и осмотреться, осознать, что произошло с параметрами атомов, вовлеченных в вычисления. В нашем первоначальном запросе у нас была одна константа и одна переменная. Если присмотреться внимательно, можно заметить, что константный параметр передаётся каждому выводимому атому как значение, тогда как переменная X передаётся как ссылка. Заметьте, что нигде не присутствует классическое вычисление, просто применяется унификация для сопоставления аргументов (передачи параметров) а затем резолюция, чтобы переформировать запрос.
Бэктрекинг
С приведенным примером мы еще не закончили. Можете заметить, что существует еще одно решение: мы можем отменить вычисления сделанные выше, и получить подстановку X = b или X = c или X = d. Способ, которым Пролог справляется с ситуацией, когда запрос редуцируется к пустому запросу, называется бэктрекингом(откатом). Система Пролог откатывается к последней унификации для того, чтобы определить, существует ли другой факт или правило, с которым сработает унификация. Если таковой имеется, тогда можно найти дополнительное решение. Бэктрэкинг продолжается до тех пор, пока не найдены все возможные ответы.
Задачи 3
1. Рассмотрим задачу связанную с бэктрекингом, возникающую при запросе ?- tedge(a, X). Предположим, что граф взят из примера 3.3. Выпишете шаги унификации / резолюции как сделано выше и явно отметьте любые случае, когда более чем одно правило или факт могут быть унифицированы (помните, что каждый такой случай может привести к дополнительному решению). Затем продолжайте расписывать унификацию / резолюцию через бэктрекинг (подмечая все ветки решений). Найдите таким образом все решения.
2. (Похвально будет решить!) Генеалогическое дерево. Пожалуй наиболее популярная логическая программа среди новичков. Создайте множество фактов, которые помогут определить ваши семейные взаимоотношения:
male = { The males in your family. }
female = { The females in your family. }
parent_of = { The pairs (x,y) where x is the parent of y in your family. }
Не надрывайтесь (если у вас большая семья). Напишите несколько членов семьи.
Обратите внимание, что предикаты male и female имеют только один аргумент. Вам понадобится одна запись на каждого члена семьи. Определите следующие предикаты, полагаясь на определенные ранее.
father, mother, son, daughter, grandfather,
aunt, uncle, cousin, ancestor
Заметьте, что начальные из этих предикатов могут быть определены с применением фактов, но более поздние должны быть определены с помощью предикатов, заданных ранее.
Продемонстрируем подход к решению данной задачи(как бы автор подошел к решению этой задачи):
male(jerry).
male(stuart).
male(warren).
female(kathe).
female(maryalice).
brother(jerry,stuart).
brother(jerry,kathe).
sister(kather,jerry).
parent_of(warren,jerry).
parent_of(maryalice,jerry).
Вот и вся 3-я глава. Следующая глава про списки.
Комментариев нет:
Отправить комментарий