Примеры, использующие отсечение
Вычисление максимума
Процедуру нахождения наибольшего из двух чисел можно запрограммировать в виде отношения
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).
Процедура проверки принадлежности списку, дающая единственное решение
Для того, чтобы узнать, принадлежит ли 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о (нет)
Добавление элемента к списку, если он в нем отсутствует (добавление без дублирования)
Часто требуется добавлять элемент 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, с]
Поэтому отсечение требуется здесь для правильного определения отношения, а не только для повышения эффективности. Этот момент иллюстрируется также и следующим примером.
Задача классификации объектов
Предположим, что у нас есть база данных, содержащая результаты теннисных партий, сыгранных членами некоторого клуба. Подбор пар противников для каждой партия не подчинялся какой-либо системе, просто каждый игрок встречался с несколькими противниками. Результаты представлены в программе в виде фактов, таких как
победил( том, джон).
победил( энн, том).
победил( пат, джим).
Мы хотим определить
отношение класс( Игрок, Категория)
которое распределяет игроков по категориям. У нас будет три категории:
победитель — любой игрок, победивший во всех сыгранных им играх
боец — любой игрок, в некоторых играх победивший, а в некоторых проигравший
спортсмен — любой игрок, проигравший во всех сыгранных им партиях
Например, если в нашем распоряжении есть лишь приведенные выше результаты, то ясно, что Энн и Пат — победители. Том — боец и Джим — спортсмен.
|
|
|
Легко сформулировать правило для бойца:
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. Следующие отношения распределяют числа на три класса - положительные, нуль и отрицательные:
класс( Число, положительные) :- Число > 0.
класс( 0, нуль).
класс( Число, отрицательные) :- Число < 0.
Сделайте эту процедуру более эффективной при помощи отсечений.
5.3. Определите процедуру
разбить( Числа, Положительные, Отрицательные)
которая разбивает список чисел на два списка: список, содержащий положительные числа (и нуль), и список отрицательных чисел. Например,
разбить( [3, -1, 0, 5, -2], [3, 0, 5], [-1, -2] )
Предложите две версии: одну с отсечением, другую — без.
Отрицание как неуспех
"Мэри любит всех животных, кроме змей". Как выразить это на Прологе? Одну часть этого утверждения выразить легко: "Мэри любит всякого X, если X — животное". На Прологе это записывается так:
любит( мэри, X) :- животное ( X).
Но нужно исключить змей. Это можно сделать, использовав другую формулировку:
Если X — змея, то "Мэри любит X" — не есть истина,
иначе, если X — животное, то Мэри любит X.
Сказать на Прологе, что что-то не есть истина, можно при помощи специальной цели fail (неуспех), которая всегда терпит неудачу, заставляя потерпеть неудачу и ту цель, которая является ее родителем. Вышеуказанная формулировка, переведенная на Пролог с использованием fail, выглядит так:
любит( мэри, X) :-
змея( X), !, fail.
любит( Мэри, X) :-
животное ( X).
Здесь первое правило позаботится о змеях: если X — змея, то отсечение предотвратит перебор (исключая таким образом второе правило из рассмотрения), а fail вызовет неуспех. Эти два предложения можно более компактно записать в виде одного:
любит( мэри, X):-
змея( X), !, fail;
животное ( X).
Ту же идею можно использовать для определения отношения
различны( X, Y)
которое выполняется, если X и Y не совпадают. При этом, однако, мы должны быть точными, потому что "различны" можно понимать по-разному:
• X и Y не совпадают буквально;
• X и Y не сопоставимы;
• значения арифметических выражений X и Y не равны.
Давайте считать в данном случае, что X и Y различны, если они не сопоставимы. Вот способ выразить это на Прологе:
Если X и Y сопоставимы, то
цель различны( X, Y) терпит неуспех
иначе цель различны( X, Y) успешна.
Мы снова используем сочетание отсечения и fail:
различны( X, X) :- !, fail.
различны( X, Y).
То же самое можно записать и в виде одного предложения:
различны( X, Y) :-
X = Y, !, fail;
true.
Здесь true — цель, которая всегда успешна.
Эти примеры показывают, что полезно иметь унарный предикат "not" (не), такой, что
nоt( Цель)
истинна, если Цель не истинна. Определим теперь отношение not следующим образом:
Если Цель успешна, то not( Цель) неуспешна,
иначе not( Цель) успешна.
Это определение может быть записано на Прологе так:
not( P) :-
P, !, fail;
true.
Начиная с этого момента мы будем предполагать, что not — это встроенная прологовская процедура, которая ведет себя так, как это только что было определено. Будем также предполагать, что оператор not определен как префиксный, так что цель
not( змея( X) )
можно записывать и как
not змея( X)
Многие версии Пролога поддерживают такую запись. Если же приходится иметь дело с версией, в которой нет встроенного оператора not, его всегда можно определить самим.
Следует заметить, что not, как он здесь определен с использованием неуспеха, не полностью соответствует отрицанию в математической логике. Эта разница может породить неожиданности в поведении программы, если оператором not пользоваться небрежно. Этот вопрос будет рассмотрен в данной главе позже.
Тем не менее not — полезное средство, и его часто можно с выгодой применять вместо отсечения. Наши два примера можно переписать с not:
любит( мэри, X) :-
животное ( X),
not змея( X).
различны( X, Y) :-
not( X = Y).
Это, конечно, выглядит лучше, нежели наши прежние формулировки. Вид предложений стал более естественным, и программу стало легче читать.
Нашу программу теннисной классификации из предыдущего раздела можно переписать с использованием not так, чтобы ее вид был ближе к исходным определениям наших трех категорий:
класс( X, боец) :-
победил( X, _ ),
победил( _, X).
класс( X, победитель) :-
победил( X, _ ),
not победил( _, X).
класс( X, спортсмен) :-
not победил( X, _ ).
В качестве еще одного примера использования not рассмотрим еще раз программу 1 для решения задачи о восьми ферзях из предыдущей главы (рис. 4.7). Мы определили там отношение небьет между некоторым ферзем и остальными ферзями. Это отношение можно определить также и как отрицание отношения "бьет". На рис. 5.3 приводится соответствующим образом измененная программа.
решение( []).
решение( [X/Y | Остальные] ) :-
решение( Остальные),
принадлежит( Y, [1, 2, 3, 4, 5, 6, 7, 8] ),
not бьет( X/Y, Остальные).
бьет( X/Y, Остальные) :-
принадлежит( X1/Y1, Остальные),
( Y1 = Y;
Y1 is Y + X1 - X;
Y1 is Y - X1 + X ).
принадлежит( А, [А | L] ).
принадлежит( А, [В | L] ) :-
принадлежит( А, L).
% Шаблон решения
шаблон( [1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).
Рис. 5.3. Еще одна программа для решения задачи о восьми ферзях.
Упражнения
5.4. Даны два списка Кандидаты и Исключенные, напишите последовательность целей (используя принадлежит и not), которая, при помощи перебора, найдет все элементы списка Кандидаты, не входящие в список Исключенные.
5.5. Определите отношение, выполняющее вычитание множеств:
разность( Множ1, Множ2, Разность)
где все три множества представлены в виде списков. Например,
разность( [a, b, c, d], [b, d, e, f], [a, c] )
Посмотреть ответ
5.6. Определите предикат
унифицируемые( Спис1, Терм, Спис2)
где Спис2 — список всех элементов Спис1, которые сопоставимы с Терм'ом, но не конкретизируются таким сопоставлением. Например:
?- унифицируемые( [X, b, t( Y)], t( a), Спис).
Спис = [ X, t( Y)]
Заметьте, что и X и Y должны остаться неконкретизированными, хотя сопоставление с t( a) вызывает их конкретизацию. Указание: используйте not ( Терм1 = Терм2). Если цель Терм1 = Терм2 будет успешна, то not( Терм1 = Tepм2) потерпит неудачу и получившаяся конкретизация будет отменена!
Дата добавления: 2018-05-01; просмотров: 474; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!