Примеры, использующие отсечение
Примеры, использующие отсечение
Вычисление максимума
1. Вычисление максимума
Процедуру нахождения наибольшего из двух чисел можно запрограммировать в виде отношения
mах( X, Y, Мах)
где Мах = X, если Х больше или равен Y, и Мах есть Y, если Х меньше Y. Это соответствует двум таким предложениям:
mах( X, Y, X) :- Х >= Y.
max( X, Y, Y) :- Х < Y.
Эти правила являются взаимно исключающими. Если выполняется первое, второе обязательно потерпит неудачу. Если неудачу терпит первое, второе обязательно должно выполниться. Поэтому возможна более экономная формулировка, использующая понятие "иначе":
если Х >= Y, то Мах = X,
иначе Мах = Y.
На Прологе это записывается при помощи отсечения:
mах( X, Y, X) :- Х >= Y, !.
mах( X, Y, Y).
Процедура проверки принадлежности списку, дающая единственное решение2. Процедура проверки принадлежности списку, дающая единственное решение
Для того, чтобы узнать, принадлежит ли Х списку L, мы пользовались отношением
принадлежит( X, L)
Программа была следующей:
принадлежит( X, [X | L] ).
принадлежит X, [Y | L] ) :- принадлежит( X, L).
Эта программа дает "недетерминированный" ответ: если Х встречается в списке несколько раз, то будет найдено каждое его вхождение. Исправить этот недостаток не трудно: нужно только предотвратить дальнейший перебор сразу же после того, как будет найден первый X, а это произойдет, как только в первом предложении наступит успех. Измененная программа выглядит так:
принадлежит( X, [X | L] ) :- !.
принадлежит( X, [Y | L] ) :- принадлежит( X, L).
Эта программа породит только одно решение. Например:
?- принадлежит( X, [а, b, с] ).
Х = а;
nо
(нет)
3. Добавление элемента к списку, если он в нем отсутствует (добавление без дублирования)
Часто требуется добавлять элемент Х в список L только в том случае, когда в списке еще нет такого элемента. Если же Х уже есть в L, тогда L необходимо оставить без изменения, поскольку нам не нужны лишние дубликаты X. Отношение добавить имеет три аргумента:
добавить( X, L, L1)
где Х - элемент, который нужно добавить, L - список, в который его нужно добавить, L1 - результирующий новый список. Правила добавления можно сформулировать так:
если Х принадлежит к L, то L1 = L,
иначе L1 - это список L с добавленным к нему
элементом X.
Проще всего добавлять Х в начало списка L так, чтобы Х стал головой списка L1. Запрограммировать это можно так:
добавить( X, L, L) :- принадлежит( X, L), !.
добавить( X, L, [X | L] ).
Поведение этой процедуры можно проиллюстрировать следующим примером:
?- добавить( а, [b,с], L).
L = [a, b, c]
?- до6авить( X, [b, с], L).
L = [b, с]
Х = b
?- добавить( а, [b, с, X], L).
L = [b, с, а]
Х = а
Этот пример поучителен, поскольку мы не можем легко запрограммировать "недублирующее добавление", не используя отсечения или какой-либо другой конструкции, полученной из него. Если мы уберем отсечение в только что рассмотренной программе, то отношение добавить будет добавлять дубликаты элементов, уже имеющихся в списке. Например:
?- добавить( a, [a, b, c], L),
L = [а, b, с]
L = [а, а, b, с]
Поэтому отсечение требуется здесь для правильного определения отношения, а не только для повышения эффективности. Этот момент иллюстрируется также и следующим примером.
Задача классификации объектов4. Задача классификации объектов
Предположим, что у нас есть база данных, содержащая результаты теннисных партий, сыгранных членами некоторого клуба. Подбор пар противников для каждой партия не подчинялся какой-либо системе, просто каждый игрок встречался с несколькими противниками. Результаты представлены в программе в виде фактов, таких как
победил( том, джон).
победил( энн, том).
победил( пат, джим).
Мы хотим определить
отношение класс( Игрок, Категория)
которое распределяет игроков по категориям. У нас будет три категории:
победитель - любой игрок, победивший во всех сыгранных им играх
боец - любой игрок, в некоторых играх победивший, а в некоторых проигравший
спортсмен - любой игрок, проигравший во всех сыгранных им партиях
Например, если в нашем распоряжении есть лишь приведенные выше результаты, то ясно, что Энн и Пат - победители. Том - боец и Джим - спортсмен.
Легко сформулировать правило для бойца:
Х - боец, если существует некоторый Y, такой, что Х победил
Y, и
существует некоторый Z, такой, что Z победил
X.
Теперь правило для победителя:
Х - победитель, если
X победил некоторого Y и
Х не был побежден никем.
Эта формулировка содержит отрицание "не", которое нельзя впрямую выразить при помощи тех возможностей Пролога, которыми мы располагаем к настоящему моменту. Поэтому оказывается, что формулировка отношения победитель должна быть более хитрой. Та же проблема возникает и при формулировке правил для отношения спортсмен. Эту проблему можно обойти, объединив определения отношений победитель и боец и использовав связку "иначе". Вот такая формулировка:
Если Х победил кого-либо и Х был кем-то
побежден,
то Х - боец,
иначе, если Х победил кого-либо,
то Х - победитель,
иначе, если Х был кем-то побежден,
то Х - спортсмен.
Такую формулировку можно сразу перевести на Пролог. Взаимные исключения трех альтернативных категорий выражаются при помощи отсечений:
класс( X, боец) :-
победил( X, _ ),
победил( _, X), !.
класс( X, победитель) :-
победил( X, _ ), !.
класс( X, спортсмен) :-
победил( _, X).
Заметьте, что использование отсечения в предложении для категории победитель не обязательно, что связано с особенностями наших трех классов.
Содержание раздела
