Механизм отсечений и отката(mechanism of Cuting and Backtracking) ПроЛога. Отличия ПроЛога от алгоритмичесих языков программирования.

Способность выдавать несколько решений

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

число_больше(А,3):-А<3.
число_больше(А,5):-А<5.
число_больше(А,8):-А<8.

Тогда вызов решателя ПроЛога

Goal число_больше(4,Больше).

Выдаст ответы: Больше = 5, 8.

Другими словами, согласно правилам в предикате "число_больше" больше числа 4 есть два числа 5 и 8. Здесь видно, что набор правил работает как структура ветвления case в алгоритмических языках. Предикаты которые могут выдавать несколько значений называются неопределенными (nondeterm). Предикаты, которые выдают только одно значение, называются определенными (determ). Кроме неопределенных предикатов в ПроЛоге еще используют механизм неопределенности факты. Пример.

иметь(долги, плохо).
иметь(квартира, хорошо).
иметь(дети, хорошо).

Тогда вызов решателя ПроЛога

Goal иметь(Что,хорошо).

Ответ будет: Что = квартира, дети

Откат (Backtracking)

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

database - знания
иметь(string, string)
predicates
показать(string)
clauses
показать(Как):-
% здесь переменная Что будет каждый раз освобождаться и
% связываться с новым значением
	иметь(Что,Как),
	nl,write(Что," иметь ",Как).
Goal
% загрузим знания с фактами иметь() из файла знания.txt
	consult("знания.txt",знания),
% вызовем предикат выдающий несколько вариантов ответа
	показать(хорошо).

Ответы ПроЛога:

	квартира иметь хорошо
	дети иметь хорошо

Отсечение (Cut)

Теперь введем понятие отсечения. Отсечением в ПроЛоге называется механизм, который запрещает перебор правил данного предиката находящихся ниже текущего правила и запрещает механизм отката. Отсечение обозначается знаком "!". Пример. Если переписать предыдущий предикат "число_болше" как:

число_больше(А,3):-А<3,
	!.
число_больше(А,5):-А<5,
	!.
число_больше(А,8):-А<8,
	!.

Тогда вызов решателя ПроЛога

Goal число_больше(4,Больше).

Выдаст ответ: Больше = 5.

Это происходит потому, что в каждом правиле предиката, после проверки на больше, идет оператор отсечения "!", что запрещает ПроЛогу последующий откат и поиск других вариантов ответа.

Пример использования механизма отката и отсечений.

Механизм отката и отсечений можно рассмотреть на следующем примере. Допустим у нас есть список значений, в котором нужно найти некое значение и выдать стоящее перед ним значение. Так как ПроЛог это логический язык, то поставленная задача решается с помощью создания набора правил:

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

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

Если предыдущие правила не сработали, то выдать текущий элемент как предыдущее значение.

Описание на языке ПроЛог предиката выполняющего эти правила будет такое:

1. найти_пред_значение(Значение,[Элемент|Список], Предыдущее):-
	not(Значение=Элемент),
	!, % отсечение перебора правил предиката, расположенных ниже
	найти_пред_значение(Значение,Список,Предыдущее),
	!.
2. найти_пред_значение(Значение,[Значение|_],_):-
	!,% отсечение перебора правил предиката, расположенных ниже
	fail.
3. найти_пред_значение(_,[Предыдущее|_],Предыдущее):- !.

Зная, что в ПроЛоге можно использовать порядок расположения правил как способ выбора последовательности обхода правил, и зная действие механизма отсечений, можно переставить правила 1 и 2 местами и убрать проверку на несовпадение. Тогда получим следующее описание предиката:

domains
Номер = integer
НСписок = Номер*
predicates
найти_пред_значение(Номер Значение, НСписок, Номер Предыдущее)
clauses
найти_пред_значение(Значение,[Значение|_],_):-
	!,% отсечение перебора правил предиката, расположенных ниже
	fail.
найти_пред_значение(Значение,[_|Список], Предыдущее):-
	найти_пред_значение(Значение,Список,Предыдущее),
	!.% отсечение выдачи других ответов
найти_пред_значение(_,[Предыдущее|_],Предыдущее):-
	!.% отсечение выдачи других ответов

Полученное описание состоит из трех правил и выполняет следующие действия. Первое правило сравнивает текущий элемент с искомым значением, и если они равны, то происходит а) отсечение правил предиката расположенных ниже от участия в поиске, б) вызывается неудача, что приводит к останову рекурсии. Второе правило делает перебор всех элементов списка с помощью вызова самой себя, то есть вызывает рекурсию. При этом, в правиле до вызова рекурсии нет отсечений, и если вызов рекурсии будет неуспешным, то управление перейдет на правило предиката, расположенное ниже. Если вызов рекурсии будет успешен, то вызывается отсечение ("!"), а потом выход из предиката. Третье правило выдает текущий элемент как предыдущее значение, которое стоит перед искомым значением, вызывает отсечение и выход из предиката. Действие предиката рассмотри на примере. Дадим решателю ПроЛога строку:

Goal найти_пред_значение(3,[1,2,4,3,5,2],Предыдущее).

ПроЛог делает первый вызов предиката:

• Правило 1 не срабатывает: 3 не равно 1. Переход на второе правило:
• Правило 2 вызывает рекурсию найти_пред_значение(3,[2,4,3,5,2],Предыдущее):
• Правило 1 не срабатывает: 3 не равно 2. Переход на второе правило:
• Правило 2 вызывает рекурсию найти_пред_значение(3,[4,3,5,2],Предыдущее):
• Правило 1 не сработает: 3 не равно 4. Переход на второе правило:
• Правило 2 вызывает рекурсию: найти_пред_значение(3,[3,5,2],Предыдущее):
• Первое правило сработает: 3=3. и выполняется: отсечение правил предиката ниже и неудача. Что приводит в выходу из рекурсии с результатом неудачи.
• Продолжение правила 2. Неудача вызова рекурсии со списком [3,5,2] приводит к неудаче второго правила на данном уровне. ПроЛог переходит на третье правило.
• Правило 3. Здесь список = [4,3,5,2]. Происходят действия: Предыдущее унифицируется с 4, выход с отсечением других возможных решений.
• Продолжение правила 2. Рекурсия возвращает удачное значение Предыдущее =4. Происходит выход с отсечением других возможных решений.
• Продолжение правила 2. Рекурсия возвращает удачное значение Предыдущее =4. Происходит выход с отсечением других возможных решений.
• Продолжение правила 2. Рекурсия возвращает удачное значение Предыдущее =4. Происходит выход с отсечением других возможных решений.

Ответ ПроЛога Предыдущее = 4.

Теперь посмотрим что будет, если убрать отсечение во втором правиле:

domains
Номер = integer
НСписок = Номер*
predicates
% обявляем что предикат неопределенный
nondeterm найти_пред_значение(Номер Значение, НСписок, Номер Предыдущее)
clauses
найти_пред_значение(Значение,[Значение|_],_):-
	!,% отсечение перебора правил предиката, расположенных ниже
	fail.
найти_пред_значение(Значение,[_|Список], Предыдущее):-
% в этом правиле нет ни одного отсечения
% что указывает на возможность отката в это место
% для выбора следующего варианта ответа
	найти_пред_значение(Значение,Список,Предыдущее).
найти_пред_значение(_,[Предыдущее|_],Предыдущее):-
	!.% отсечение выдачи других ответов

То ПроЛог уже выдаст несколько результатов:

Предыдущее = 4, 2, 1.

Это становится возможным, так как включается механизм отката ПроЛога и во втором правиле появляется возможность выдать ответ на каждом шаге рекурсии.