Не повторяйте решения в Прологе
Предположим, у вас есть база данных со следующим содержанием:
son(a, d).
son(b, d).
son(a, c).
son(b, c).
Так что а и б - сыновья д и в. Теперь вы хотите знать, учитывая большую базу данных, кто брат кому. Решение будет:
brother(X, Y) :-
son(X, P),
son(Y, P),
X \= Y.
Проблема в том, что если вы спросите "брат (X, Y)". и начните нажимать ";" вы получите избыточные результаты, такие как:
- X = a, Y = b;
- X = b, Y = a;
- X = a, Y = b;
- X = b, Y = a;
Я могу понять, почему я получаю эти результаты, но я ищу способ исправить это. Что я могу сделать?
6 ответов
Я получил ответ.
% Include the dictionary
:- [p1]. % The dictionary with sons
:- dynamic(found/2).
brother(X, Y) :-
% Get two persons from the database to test
son(X, P),
son(Y, P),
% Test if the two persons are different and were not already used
testBrother(X, Y).
% If it got here it's because there is no one else to test above, so just fail and retract all
brother(_, _) :-
retract(found(_, _)),
fail.
testBrother(X, Y) :-
X \= Y,
\+found(X, Y),
\+found(Y, X),
% If they were not used succed and assert what was found
assert(found(X, Y)).
Он всегда возвращает неудачу в конце, но это происходит с помощью следующего.
- брат (X, Y). Каждый брат без повторений
- брат ('Urraca', X). Каждый брат Urraca без повторений
- брат ("Уррака", "Санчо I"). Верно, потому что Уррака и Санчо у меня одинаковые отец и мать. На самом деле, даже если бы у них была одна и та же мать или один и тот же отец, это вернуло бы истину. Немного вне контекста, но все еще в силе, если у них есть три или более общих родителей, это все равно будет работать
Это терпит неудачу со следующим:
- брат (X, X). % Ложь, потому что это один и тот же человек
- брат ("Нет", X). % False, потому что нет даже в базе данных
- брат ("Нет", "Санчо I"). % False, та же причина
Так вот так я могу, например, спросить: брата (X, Y) и начать нажимать ";" видеть каждого брата и сестру без повторений.
Я также могу сделать брата (a, b) и брата (b, a), предполагая, что a и b являются людьми в базе данных. Это важно, потому что некоторые решения будут использовать @<для проверки чего-либо, и поэтому брат (b, a) потерпит неудачу.
Так и есть.
Prolog всегда будет пытаться найти любое возможное решение для ваших утверждений, учитывая ваш набор истин. Расширение работает как поиск в глубину:
son(a, d).
son(b, d).
son(a, c).
son(b, c).
brother(X, Y) :-
son(X, P),
son(Y, P),
X \= Y.
brother(X, Y)
_______________________|____________________________ [son(X, P)]
| | | |
X = a, P = d X = b, P = d X = a, P = c X = a, P = b
| | | |
| ... ... ...
|
| (X and P are already defined for this branch;
| the algorithm now looks for Y's)
|__________________________________________ [son(Y, d)]
| |
son(a, d) -> Y = a son(b, d) -> Y = b
| |
| | [X \= Y]
X = a, Y = a -> false X = a, Y = b -> true
|
|
solution(X = a, Y = b, P = d)
Но, как вы можете видеть, расширение будет выполняться во всех ветвях, так что вы получите больше того же решения, что и в окончательном ответе. Как указано @Daniel Lyons, вы можете использовать setof встроенный.
Вы также можете использовать ! - оператор cut - останавливает "горизонтальное" расширение, как только ветвь будет признана допустимой, или добавляет какое-либо утверждение, которое позволяет избежать нескольких решений.
Для получения дополнительной информации взгляните на алгоритм объединения.
Во-первых, я бы посоветовал не обновлять базу данных Prolog динамически. По некоторым причинам рассмотрите статью "Как работать с динамической базой данных Prolog?",
Вы можете использовать комбинацию встроенных setof/3 а также member/2, как @DanielLyons предложил в своем ответе.
В качестве еще одной альтернативы рассмотрим следующий запрос, который использует setof/3 довольно необычным образом, как это:
?- setof(t,brother(X,Y),_).
X = a, Y = b ;
X = b, Y = a.
Вы можете исключить один набор с помощью сравнения:
brother(X, Y) :-
son(X, P),
son(Y, P),
X \= Y, X @< Y.
?- brother(X, Y).
X = a,
Y = b ;
X = a,
Y = b ;
false.
Поскольку X и Y будут реализованы в обоих случаях, требование, чтобы X было меньше Y, является хорошим способом разрезать решения пополам.
Ваша вторая проблема заключается в том, что X и Y являются братьями по нескольким родителям. Самым простым решением было бы сделать ваши правила более явными:
mother(a, d).
mother(b, d).
father(a, c).
father(b, c).
brother(X, Y) :-
mother(X, M), mother(Y, M),
father(X, F), father(Y, F),
X \= Y, X @< Y.
?- brother(X, Y).
X = a,
Y = b ;
false.
Этот метод очень специфичен для данной конкретной проблемы, но основная причина этого не в том, что у вас было две копии, потому что a а также b "братья" c а также d- Пролог был прав, создавая это решение дважды, потому что была скрытая переменная, созданная для двух разных значений.
Более элегантное решение, вероятно, будет использовать setof/3 чтобы получить решения. Это может работать даже с вашим исходным кодом:
?- setof(X-Y, (brother(X, Y), X @< Y), Brothers).
Brothers = [a-b].
Недостатком этого подхода является то, что вы получаете список, а не пролог, генерирующий различные решения, хотя вы можете восстановить это поведение с помощью member/2,
Это должно работать. Но я думаю, что это можно улучшить (я не специалист по Прологу):
brother(X, Y) :-
son(X, P1),
son(Y, P1),
X @< Y,
(son(X, P2), son(Y, P2), P1 @< P2 -> false; true).
Если вы используете компилятор Strawberry Prolog, вы не получите ответы на все вопросы, набрав:
?- brother(X, Y),
write(X), nl,
write(Y), nl.
Чтобы получить ответы на все вопросы, напишите это:
?- brother(X, Y),
write(X), nl,
write(Y), nl,
fail.
Я надеюсь, что это поможет вам.:)