Общая схема согласования целевых утверждений



 

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

· успешного согласования целей вопроса;

· неуспеха (или неудачи).

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

Допустим, что логическая программа P состоит из фактов и правил, а вопрос Q ¾ конъюнктивный и содержит цели G1,G2,…Gn. Интерпретатор языка Пролог будет вычислять ответ на вопрос согласно следующим принципам, на которых он реализован:

· Цели запроса обрабатываются слева направо, G1 будет согласовываться первой, а Gn ¾последней.

· Предложения программы просматриваются интерпретатором сверху вниз.

· Если цель Gi сопоставима с заголовком правила Hj, то она должна быть сопоставима с предикатами в правой части правила. Интерпретатор заменяет цель Gi на правую часть правила Hj. Это действие называется редукцией. Другими словами, Редукцией цели G с помощью программы P называется замена цели Gi на тело правила Cj, заголовок которого Hj унифицируется с целью Gi. Вычисление вопроса выполняется в виде последовательности редукций, цепочки преобразований исходного вопроса. На каждом этапе вычисления существует некоторая конъюнкция целей (или одна цель), называемая резольвентой. Цели, которые добавляются в запрос в результате редукции, называются производными целями от цели Gi и правила Cj. Если цель Gi сопоставима с заголовком правила Hj, то список целей в запросе увеличивается. 

· Если цель Gi сопоставима с фактом, то конкретизируются переменные этой цели, и общие переменные цели Gi и других целей, входящих в вопрос, затем осуществляется переход к сопоставлению следующей цели Gi+1 , и, таким образом, список целей, подлежащих согласованию уменьшается.

· Когда мы таким образом достигнем последней цели в запросе, и она успешно будет согласована с каким-либо фактом программы, то текущая резольвента окажется пустой, и вычисление запроса будет успешным.

Процедуру Вычислить можно представить более формализовано на языке описания алгоритмов (псевдокоде) в следующем виде:


ПРОЦЕДУРА Вычислить(Прогр, СписокЦелей, ПризнакУспеха)

Входные параметры:
Прогр: список предложений на языке Пролог;
СписокЦелей: запрос;

Выходной параметр:
ПризнакУспеха: истина, если СписокЦелей истинен;
                        ложь, в противном случае.

Локальные переменные:
Цель: предикат;
ДругиеЦели: список целей;
Достигнуты: истинностное значение;
Конкрет: конкретизация переменных;
H, H’, B1, B1’, ……Bn,Bn’: цели;

Вспомогательные функции:
пустой(L): возвращает значение «истина», если L ¾пустой список;
голова(L): возвращает первый элемент списка L;
хвост(L): возвращает остальные элемент списка L;
конкат(L1,L2): присоединяет список L2 к концу списка L1;
сопоставление(T1,T2,Сопоставимы, Конкрет): пытается унифицировать термы Т1 и Т2; если они унифицируются, то переменной Сопоставимы присваивается значение “истина”, а Конкрет представляет собой конкретизацию переменных;
подстановка(Конкрет, Цели): производит подстановку переменных в Цели согласно Конкрет;

НАЧАЛО_ПРОЦЕДУРЫ
ЕСЛИ
  пустой(СписокЦелей)     ТО ПризнакУспеха=истина

ИНАЧЕ Цель:=голова(СписокЦелей);

ДругиеЦели:=хвост(СписокЦелей);

Достигнуты:=ложь;

ЦИКЛ ПОКА (Достигнуты=ложь И

    “в программе есть еще предложения”)

ЕСЛИ следующее предложение в Прогр есть H:¾B1,B2,…Bn.    ТО  создать вариант этого предложения H’:¾ B’1,B’2,…B’n.
    путем переименования переменных;
    сопоставление(Цель, H’, Сопоставимы, Конкрет);

ЕСЛИ   Сопоставимы ТО
НовыеЦели:= конкат([B’1,B’2,…B’n,],ДругиеЦели);

НовыеЦели:=подстановка(Конкрет,НовыеЦели);
Вычислить(Прогр,НовыеЦели,Достигнуты);

КОНЕЦ_ЕСЛИ
КОНЕЦ_ЕСЛИ
ИНАЧЕ найден факт H;

создать вариант этого факта H’
путем переименования переменных;

сопоставление(Цель, H’, Сопоставимы, Конкрет);

ЕСЛИ   Сопоставимы ТО
НовыеЦели:= ДругиеЦели;

НовыеЦели:=подстановка(Конкрет,НовыеЦели);
Вычислить(Прогр,НовыеЦели,Достигнуты);

     КОНЕЦ_ЕСЛИ
КОНЕЦ_ЦИКЛА

КОНЕЦ_ЕСЛИ
ПризнакУспеха:=Достигнуты;

КОНЕЦ_ПРОЦЕДУРЫ

 

Рассмотрим пример вычисления запроса на основе программы, включающей и факт, и правила. Пусть программа содержит утверждения, приведенные ниже:

 

big(‘медведь’).        %предложение 1

big(‘слон’).                       %предложение 2

little(‘кот’).                       %предложение 3

little(‘мышь’).          %предложение 4

black(‘кот’).             %предложение 5

grey(‘слон’).            %предложение 6

grey(‘мышь’).          %предложение 7

brown(‘медведь’).            %предложение 8

dark(Z):¾black(Z).  %предложение 9

dark(Z):¾brown(Z). %предложение 10

 

Для вычисления запроса “? ¾ dark(X),big(X). “ интерпретатор выполняется следующие действия:

Шаг 1.  Текущая резольвента Q1 есть исходный запрос ¾ dark(X),big(X).

Шаг 2.  Текущая резольвента Q2 является конъюнкцией целей dark(X),big(X). Выбираем первую цель G21¾dark(X) и, просматривая программу с первого предложения, находим предложение 9, сопоставимое с целью G21, является правилом

dark(Z):¾black(Z). 
переименовываем переменную Z на Х и вместо цели G21 подставляем правую часть правила 9. Получаем текущую резольвенту Q3¾black(X),big(X)

Шаг 3.  Текущая резольвента Q3 является конъюнкцией целей black(X),big(X). Выбираем первую цель G31¾black(X) и, просматривая программу с первого предложения, находим предложение 5, сопоставимое с целью G31, black(‘кот’).
при подстановке {X=’кот’}. Предложение 5 является фактом, поэтому список целей в резольвенте сократится, так как цель G31 удаляется , а в цель G32 при подстановке {X=’кот’} примет вид
big(‘кот’). Получаем текущую резольвенту Q4: big(‘кот’).

Шаг 4   Текущая резольвента Q4 включает одну цель G41 big(‘кот’). Просматривая программу с первого предложения, не находим ни одного предложения, сопоставимого с целью G41,
поэтому выполняется возврат на шаг 3.

Шаг 3.  Текущая резольвента Q3 является конъюнкцией целей black(X),big(X). Выбираем первую цель G31¾black(X) и, просматривая программу с предложения 6 до конца программы, и  не находим ни одного предложения 5, сопоставимого с целью G31, поэтому выполняется возврат на шаг 2.

Шаг 2.  Текущая резольвента Q2 является конъюнкцией целей dark(X),big(X). Выбираем первую цель G21¾dark(X) и, просматривая программу с предложения 10, находим предложение 10, сопоставимое с целью G21, является правилом

dark(Z):¾brown(Z).
переименовываем переменную Z на Х и вместо цели G21 подставляем правую часть правила 9. Получаем текущую резольвенту Q5¾ brown (X),big(X).

Шаг 5.  Текущая резольвента Q5 является конъюнкцией целей brown(X),big(X). Выбираем первую цель G51¾ brown(X) и, просматривая программу с первого предложения, находим предложение 8, сопоставимое с целью G51, brown(‘медведь’).
при подстановке {X=’медведь’}. Предложение 8 является фактом, поэтому список целей в резольвенте сократится, так как цель G51 удаляется , а в цель G52 при подстановке {X=’медведь’} примет вид
big(‘медведь’). Получаем текущую резольвенту Q6: big(‘медведь’).

Шаг 6   Текущая резольвента Q6 включает одну цель G61 big(‘медведь’). Просматривая программу с первого предложения, находим предложение 1, сопоставимое с целью G61,
которое является фактом, поэтому цель G61 удаляется из текущей резольвенты, и она становится пустой, Q7=ÿ.

Шаг 7.  Текущая резольвента Q7 есть пустой дизъюнкт, это указывает на успешное завершение вычисления запроса Q1. Интерпретатор выдает конкретизацию переменной {X=’медведь’} как результат вычисления запроса.

Процесс вычисления запроса удобно представить в виде дерева поиска. Дерево поиска ответа на любой запрос строится следующим образом.

· Корнем дерева является исходный вопрос Q.

· Вершины дерева соответствуют целям (резольвентам), которые в общем случае являются конъюнктивными. В каждой выделяется одна цель.

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

· На ребрах дерева записываются подстановки, которые образуются в результате унификации выделенной в вершине цели и утверждения.

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

Рассмотрим пример построения дерева поиска для запроса: dark(X),big(X).


 

 


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

В вычислительной модели языка Пролог приняты правила просмотра целей в запросе слева направо и поиска сопоставимых правил и фактов в программе сверху вниз. Такой принцип поиска называется поиском в глубину. Рассмотрим теперь механизм поиска с возвратом.

 

Механизм поиска с возвратом.

 

Для того, чтобы представить работу механизма автоматического возврата удобно воспользоваться понятием маркера. Маркер отмечает текущее утверждение в программе, сопоставимое с целью. Для каждой цели в запросе Пролог¾система создает свой собственный маркер, который будем обозначать значком “Ñ”. Маркеры могут передвигаться только вперед. Однако, когда цель начинает согласовываться сначала, соответствующий маркер устанавливается на первое утверждение, заголовок которого совпадает с именем предиката¾цели.

Рассмотрим этот процесс на примере. Пусть программа «Однокурсники» содержит следующие утверждения:

(1) student_course(X,Y):¾student(X,K1),                    student(Y,K2),X\=Y,K1=K2.

(2) student(‘Иванов’,1).

(3) student(‘Петров’,4).

(4) student(‘Сидоров’,2).

(5) student(‘Кузнецов’,4).

Пусть требуется согласовать запрос:

?¾ student_course(X,Y).

Этот запрос сопоставим с первым утверждением, которое является правилом, поэтому производится редукция цели, и текущая резольвента примет вид:

ТР: student(X,K1), student(Y,K2),X\=Y,K1=K2.

Создадим маркер Ñ1 для первой цели в резольвенте student(X,K1) и маркер Ñ2 для второй цели в резольвенте student(Y,K2).

При просмотре фактов student в программе маркеры будут передвигаться следующим образом:

(2) student(‘Иванов’,1). Ñ1 ¯Ñ2 (no)         ¯Ñ2 (no)

(3) student(‘Петров’,4).         ¯Ñ2 (no) Ñ1 ¯Ñ2 (no)

(4) student(‘Сидоров’,2).       ¯Ñ2 (no)         ¯Ñ2 (no)

(5) student(‘Кузнецов’,4).      ¯Ñ2 (no)         ¯Ñ2 (yes)

                       возврат 1-й цели                        успешный

                                                                      вывод

при подстановке {X=‘Петров’; Y=‘Кузнецов’}.

Таким образом, ответ на запрос будет выдан в следующем виде:

?¾ student_course(X,Y).

X=‘Петров’

Y=‘Кузнецов’¾ >

Получив решение, Пролог¾система предлагает пользователю решить, нужно ли искать другие решения. При нажатии клавиши «;» интерпретатор Пролога выполняет возврат на первую цель и переставляет маркер Ñ1 на предложение 3 программы, а маркер Ñ2 на первое предложение.

(2) student(‘Иванов’,1).         ¯Ñ2 (no)         ¯Ñ2 (no)

(3) student(‘Петров’,4).         ¯Ñ2 (no)         ¯Ñ2(yes)
(4) student(‘Сидоров’,2). Ñ1 ¯Ñ2 (no)             

(5) student(‘Кузнецов’,4).      ¯Ñ2 (no) Ñ1                 
                          возврат 1-й цели                    успешный

                                                                      вывод

 

при подстановке {X=‘Петров’; Y=‘Кузнецов’}.

Не найдя второкурсников, кроме Сидорова система сама производит возврат и переставляет маркер Ñ1 на предложение 4 программы, а маркер Ñ2 на первое предложение.

Таким образом, ответ на запрос будет выдан в следующем виде:

?¾ student_course(X,Y).

X=‘Кузнецов’

Y=‘Петров’

¾ >;

Если отказаться от этого решения, то система должна будет переставить маркер Ñ1 на предложение, следующее за пятым предложением программы, но поскольку все предложения программы исчерпаны, а маркер Ñ1 может передвигаться только вперед, вычисление запроса завершается, сообщением “no”, которое означает, что больше решений нет.   


Дата добавления: 2018-04-04; просмотров: 204;