Иван Братко - Программирование на языке Пролог для искусственного интеллекта Страница 28

Более точный смысл механизма отсечений можно сформулировать следующим образом:

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

Чтобы прояснить смысл этого определения, рассмотрим предложение вида

H :- В1, В2, ..., Вm, !, ..., Вn.

Будем считать, что это предложение активизировалось, когда некоторая цель G сопоставилась с H. Тогда G является целью-родителем. В момент, когда встретилось отсечение, успех уже наступил в целях В1, …, Вm. При выполнении отсечения это (текущее) решение В1, …, Вm "замораживается" и все возможные оставшиеся альтернативы больше не рассматриваются. Далее, цель G связывается теперь с этим предложением: любая попытка сопоставить  G  с головой какого-либо другого предложения пресекается.

Применим эти правила к следующему примеру:

С :- P, Q, R, !, S, T, U.

С :- V.

А :- В, С, D.

?- А.

Здесь А, В, С, D, P и т.д. имеют синтаксис термов. Отсечение повлияет на вычисление цели С следующим образом. Перебор будет возможен в списке целей P, Q, R; однако, как только точка отсечения будет достигнута, все альтернативные решения для этого списка изымаются из рассмотрения. Альтернативное предложение, входящее в С:

С :- V.

также не будет учитываться. Тем не менее, перебор будет возможен в списке целей S, T, U. "Цель-родитель" предложения, содержащего отсечения, — это цель С в предложении

А :- В, С, D.

Поэтому отсечение повлияет только на цель С. С другой стороны, оно будет "невидимо" из цели А. Таким образом, автоматический перебор все равно будет происходить в списке целей В, С, D, вне зависимости от наличия отсечения в предложении, которое используется для достижения С.

5.2. Примеры, использующие отсечение 

5.2.1.  Вычисление максимума

Процедуру нахождения наибольшего из двух чисел можно запрограммировать в виде отношения

mах( X, Y, Мах)

где Мах = X, если X больше или равен Y, и Мах есть Y, если X меньше Y. Это соответствует двум таким предложениям:

mах( X, Y, X) :- X >= Y.

max( X, Y, Y) :- X < Y.

Эти правила являются взаимно исключающими. Если выполняется первое, второе обязательно потерпит неудачу. Если неудачу терпит первое, второе обязательно должно выполниться. Поэтому возможна более экономная формулировка, использующая понятие "иначе":

 если X ≥ Y, то Мах = X,

 иначе Мах = Y.

На Прологе это записывается при помощи отсечения:

mах( X, Y, X) :- X >= Y,  !.

mах( X, Y, Y).

5.2.2. Процедура проверки принадлежности списку, дающая единственное решение

Для того, чтобы узнать, принадлежит ли X списку L, мы пользовались отношением

принадлежит( X, L)

Программа была следующей:

принадлежит( X, [X | L] ).

принадлежит X, [Y | L] ) :- принадлежит( X, L).

Эта программа дает "недетерминированный" ответ: если X встречается в списке несколько раз, то будет найдено каждое его вхождение. Исправить этот недостаток не трудно: нужно только предотвратить дальнейший перебор сразу же после того, как будет найден первый X, а это произойдет, как только в первом предложении наступит успех. Измененная программа выглядит так:

принадлежит( X, [X | L] ) :- !.

принадлежит( X, [Y | L] ) :- принадлежит( X, L).

Эта программа породит только одно решение. Например:

?- принадлежит( X, [а, b, с] ).

X = а;

nо    (нет)

5.2.3. Добавление элемента к списку, если он в нем отсутствует (добавление без дублирования)

Часто требуется добавлять элемент X в список L только в том случае, когда в списке еще нет такого элемента. Если же X уже есть в L, тогда L необходимо оставить без изменения, поскольку нам не нужны лишние дубликаты X. Отношение добавить имеет три аргумента:

добавить( X, L, L1)

где X — элемент, который нужно добавить, L — список, в который его нужно добавить, L1 — результирующий новый список. Правила добавления можно сформулировать так:

 если X принадлежит к L, то L1 = L,

 иначе L1 — это список L с добавленным к нему элементом X.

Проще всего добавлять X в начало списка L так, чтобы X стал головой списка L1. Запрограммировать это можно так:

добавить( X, L, L) :- принадлежит( X, L), !.

добавить( X, L, [X | L] ).

Поведение этой процедуры можно проиллюстрировать следующим примером:

?- добавить( а, [b,с], L).

L = [a, b, c]

?- до6авить( X, [b, с], L).

L = [b, с]

X = b

?- добавить( а, [b, с, X], L).

L = [b, с, а]

X = а

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

?- добавить( a, [a, b, c], L),

L = [а, b, с]

L = [а, а, b, с]

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

5.2.4. Задача классификации объектов

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

победил( том, джон).

победил( энн, том).

победил( пат, джим).

Мы хотим определить

отношение класс( Игрок, Категория)

которое распределяет игроков по категориям. У нас будет три категории:

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

 боец — любой игрок, в некоторых играх победивший, а в некоторых проигравший

 спортсмен — любой игрок, проигравший во всех сыгранных им партиях

Например, если в нашем распоряжении есть лишь приведенные выше результаты, то ясно, что Энн и Пат — победители. Том — боец и Джим — спортсмен.

Легко сформулировать правило для бойца:

 X — боец, если существует некоторый Y, такой, что X победил Y, и

  существует некоторый Z, такой, что Z победил X.

Теперь правило для победителя:

 X — победитель, если

  X победил некоторого Y и

  X не был побежден никем.

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

 Если X победил кого-либо и X был кем-то побежден,

 то X — боец,

 иначе, если X победил кого-либо,

  то X — победитель, 

  иначе, если X был кем-то побежден,

   то X — спортсмен.

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

класс( X, боец) :-

 победил( X, _ ),

 победил( _, X),  !.

класс( X, победитель) :-

 победил( X, _ ),  !.

класс( X, спортсмен) :-

 победил( _, X).

Заметьте, что использование отсечения в предложении для категории победитель не обязательно, что связано с особенностями наших трех классов.

5.1. Пусть есть программа:

p( 1).

p( 2) :- !.

p( 3).

Напишите все ответы пролог-системы на следующие вопросы:

(a) ?- p( X).

(b) ?- p( X), p(Y).

(c) ?- p( X), !, p(Y).

5.2. Следующие отношения распределяют числа на три класса - положительные, нуль и отрицательные: