序言中对称关系的传递闭包 [英] transitive closure over a symmetric relation in prolog

问题描述

我是 prolog 初学者，我想创建兄弟"关系.

I am a prolog beginner and I want to create the "brother" relation.

关系应该是对称的，如果 brother(alin, alex) 为真，brother(alex, alin) 也应该如此.

The relation should be symmetric as in if brother(alin, alex) is true, brother(alex, alin) should be as well.

它也应该是可传递的，如果 brother(alin, alex) 和 brother(alex, claudiu) 为真，brother(alin, claudiu) 也应该如此.

It should also be transitive as in if brother(alin, alex) and brother(alex, claudiu) are true, brother(alin, claudiu) should be as well.

结合to属性，如果brother(alex, alin)和brother(alex, claudiu)为真，brother(alin, claudiu) 也应该如此.

Combining the to properties, if brother(alex, alin) and brother(alex, claudiu) are true, brother(alin, claudiu) should also be true.

这是我的代码:

r_brother(alin, alex).
r_brother(alin, ciprian).
r_brother(alex, claudiu).

s_brother(X, Y) :- r_brother(X, Y).
s_brother(X, Y) :- r_brother(Y, X).

brother(L1, L2) :-
    t_brother(L1, L2, []).

t_brother(L1, L2, _) :-
    s_brother(L1, L2).

t_brother(L1, L2, IntermediateNodes) :-
    s_brother(L1, L3),
    \+ member(L3, IntermediateNodes),
    t_brother(L3, L2, [L3 | IntermediateNodes]).

r_brother - 是基本关系

s_brother - 是对称兄弟关系(这很好用)

s_brother - is the symmetric brother relation(this works well)

t_brother - 这应该是传递和对称关系，我保留中间节点，所以我没有得到一个循环

t_brother - this should be the transitive and symmetric relation, I keep the intermediate nodes so I don't get a loop

问题在于:

?- brother(X, alin).

是:

X = alex ;
X = ciprian ;
X = alin ;
X = alin ;
X = alin ;
X = alin ;
X = alex ;
X = alex ;
X = alex ;
X = alex ;
X = ciprian ;
X = ciprian ;
X = claudiu ;
X = claudiu ;
false.

我查看了跟踪，我知道问题所在，但我不知道如何解决.

I looked through the trace and I understand what the problem is, but I don't know how to solve it.

alin 不应该是一个可能的答案，其他人应该出现一次.

alin should not be a possible answer and the others should appear a single time.

推荐答案

我认为基本的问题是你没有检查 L2 是否已经在 t_brother/3 的第一个子句中找到.并且应该将初始的 L1 添加到兄弟/2 中的列表中:

I think the basic problem is that you do not check if L2 is already found in the first clause of t_brother/3. And the initial L1 should be added to the list in brother/2:

brother(L1, L2) :-
  t_brother(L1, L2, [L1]).                   % <-- [L1] instead of []

t_brother(L1, L2, IntermediateNodes) :-
  s_brother(L1, L2),
  \+ member(L2, IntermediateNodes).          % <-- added this check

t_brother(L1, L2, IntermediateNodes) :-      % <-- this clause is unchanged
  s_brother(L1, L3),
  \+ member(L3, IntermediateNodes),
  t_brother(L3, L2, [L3 | IntermediateNodes]).

您仍然可以使用析取来缩短解决方案:

You can still shorten the solution by using a disjunction:

t_brother(L1, L2, IntermediateNodes) :-
  s_brother(L1, L3),
  \+ member(L3, IntermediateNodes),
  ( L2=L3
  ; t_brother(L3, L2, [L3 | IntermediateNodes])).

这篇关于序言中对称关系的传递闭包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！