5.2.3.6 Раздел дбд

Раздел database служит для описания предикатов динамической базы данных (ДБД). ДБД состоит из фактов, которые предполагается модифицировать (удалять, добавлять, изменять) во время работы программы. Если такая база не используется, то раздел database в программе отсутствует.

5.2.3.7 Раздел целей

Раздел goal служит для объявления внутренней цели программы. Программа с внутренней целью не использует стандартное диалоговое окно для взаимодействия с пользователем. При отсутствии в программе раздела goal цель является внешней, т.е. определяется вопросами, вводимыми пользователем с помощью стандартного диалогового окна.

Замечание: порядок расположения целей в разделе goal и подцелей в правилах определяет действия Турбо-Пролога.

6 Лекция №5. Унификация и поиск с возвратом: программа с фактами

Время: 2 часа (90 мин.)

6.1 Основные вопросы

- обработка фактов.

6.2 Текст лекции

Р ассмотрим пример описания схемы родственных отношений, представленной на рис.2.

Рис.2. Схема родственных отношений.

Стрелкой на схеме выражено отношение “родитель”. Обозначим это отношение предикатом roditel. Тогда факт того, что vita является родителем kata, будет выражен на Турбо-Прологе следующим образом:

roditel(vita,kata).

Составим теперь небольшую программу, описывающую всю схему родственных отношений, представленную на рисунке:

/* Программа 1 */

domains

person = symbol

predicates

roditel(person, person)

clauses

roditel(ola,sasha).

roditel(vita,sasha).

roditel(vita,kata).

roditel(sasha,ana).

roditel(sasha,vera).

roditel(vera,kola).

Программа содержит три раздела: domains, predicates и clauses. В разделе domains описывается домен person как символическое имя(symbol). В разделе predicates описывается бинарный предикат roditel с двумя доменами символьного типа. В разделе clauses содержится шесть утверждений, каждое из которых объявляет об одном факте наличия отношения roditel.

В программе отсутствует раздел goal, т.е. не определена внутренняя цель. Поэтому, после запуска такой программы на выполнение, в диалоговом окне главного меню Турбо-Пролога появится сообщение:

Goal:

Теперь можно задавать программе вопросы, касающиеся отношения roditel. Например, вопрос “Является ли sasha родителем vera? ” выражается на Турбо-Прологе следующим образом:

Goal: roditel(sasha, vera)

Если данный факт в разделе clauses программы имеется (что имеет место в нашем случае), то система, найдя его, ответит YES(ДА). Если такого факта в программе нет, то ответом будет NO(НЕТ).

После ответа (а точнее под ним) в диалоговом окне вновь появится сообщение:

Goal:

Зададим более сложный вопрос “Кто является родителем kata? ”:

Goal:roditel(X, kata)

Для формулировки данного вопроса была использована свободная переменная X. Решая поставленную задачу, Турбо-Пролог просматривает сверху вниз все факты раздела clauses до тех пор, пока не будет найден факт, в котором вторым аргументом будет kata. Переменная X при этом получит значение vita (т.е. станет связанной с этим значением), что и будет ответом системы:

X=vita

1 Solution

Сообщение системы 1 Solution определяет количество решений (выводов), т.е. понимается здесь как один вывод.

Используя отношение roditel, можно задать и такой вопрос, “Кто дети sasha? ”:

Goal: roditel(sasha, X)

В этом случае, просматривая факты, система найдет два совпадения с первым аргументом sasha и выдаст два следующих ответа:

X=ana

X=vera

2 Solutions

Нашей программе можно задать и более сложный вопрос, например, “Кто чей родитель? ”, который определяет, что нужно найти такие X и Y, чтобы X являлся родителем Y:

Goal:roditel(X, Y)

Решая эту задачу, система найдет все пары данного вида в разделе clauses программы и выдаст соответственно шесть пар решений:

X=ola, Y=sasha

X=vita,Y=sasha

. . .

6 Solutions

Таким образом, поиск решений в Турбо-Прологе, как можно видеть, состоит в сопоставлении вопросов (внешних целей) с утверждениями раздела clauses программы. Этот процесс называют унификацией.

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

–константа унифицируется с идентичной константой;

–переменная (в том числе анонимная) может унифицироваться с константой или структурой, в результате чего переменная принимает значение этой константы или структуры и становится связанной переменной, т.е. конкретизируется;

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

Зададим теперь нашей программе более сложные вопросы и посмотрим, как осуществляется поиск решений. Пусть нас, например, интересует вопрос “Кто является родителем родителя kola? ”. В программе нет отношения “родитель родителя” и поэтому необходимо использовать составной вопрос:

Goal: roditel(Y, kola), roditel(X,Y)

Составной вопрос, в данном случае, включает два простых вопроса. Простые вопросы разделяются запятыми. Запятая соответствует союзу “и”, т.е. в данном случае оба простых вопроса, входящих в составной вопрос, должны выполняться одновременно. Интерпретация составного вопроса следующая: найти такие X и Y, что Y является родителем kola, а X – является родителем Y.

При решении данной составной задачи она разбивается на две подзадачи, и Турбо-Пролог ищет решение каждой подзадачи последовательно (слева направо).

Окончательным результатом решения задачи является конъюнкция решений подзадач.

Первой подзадачей в нашем примере является задача:

roditel(Y, kola).

В процессе её унификации свободная переменная Y получит значение vera(Y=vera), т.е. конкретизируется и становится, за счет этого, связанной переменной. Теперь решается вторая подзадача, в которой значение Y уже определено:

roditel(X, vera).

Турбо-Пролог вновь просматривает все факты раздела clauses, начиная с первого предложения сверху вниз, и устанавливает значение X равное sasha(X=sasha). В результате система ответит:

Y=vera, X=sasha

1 Solution

Аналогично можно задать вопрос "Кто внуки vita?":

Goal: roditel(vita, X), roditel(X, Y)

В процессе решения первой подзадачи переменная X связывается со значением sasha. Поскольку далее в разделе clauses программы имеются другие предложения с предикатом roditel, то возможно более чем одно решение первой подзадачи. В этом случае Турбо-Пролог помещает маркер возврата после факта roditel(vita, sasha) и переходит к решению второй подзадачи при связанном X=sasha:

roditel(sasha, Y).

Все предложения раздела clauses, начиная с первого, вновь просматриваются сверху вниз, и Турбо-Пролог выявляет два решения второй подзадачи:

X=sasha, Y=ana

X=sasha, Y=vera

Теперь Турбо-Пролог осуществляет возврат к маркеру возврата. При этом все связанные переменные освобождаются. Вновь повторяется процесс унификации первой подзадачи путем сопоставления с предложениями, начиная с маркера возврата. Как видно из программы, произойдет унификация с фактом roditel(vita, kata), т.е. переменная X будет связана теперь со значением kata. Однако попытка решить вторую подзадачу roditel(kata, Y) терпит неудачу, поскольку соответствующих фактов в программе нет. Турбо-Пролог возвращается вновь к маркеру возврата, который был помещен после факта roditel(vita, kata), освобождает связанные переменные и продолжает поиск решений для первой подзадачи. Однако дальнейший просмотр фактов не даёт унификации с первой подзадачей. В итоге результат состоит из приведенных выше двух решений.