Prolog:从间接关系中消除循环 [英] Prolog : eliminating cycles from indirect relation

问题描述

我有一个用户事实列表，定义为:

I have a list of user facts defined as:

user(@michael).
user(@ana).
user(@bob).
user(@george).
user(@john).

等等.此外，我有一组事实:

and so on. Furthermore, I have a set of facts as:

follows(@michael,@ana).
follows(@ana,@bob).
follows(@bob,@michael).

我正在尝试编写一个关系indirect(user1,user1)，它会告诉我user1 是否间接跟随user2.但是，我无法消除循环关系.

I am trying to write a relation indirect(user1,user1) which will tell me if user1 indirectly follows user2. However, I am not able to do away with cyclic relations.

就像在给定的例子中一样，michael -> ana -> bob -> michael 将导致一个循环.

Like in the given example, michael -> ana -> bob -> michael will cause a cycle.

从indirect(user1,user2)的结果中消除这些循环的最佳方法是什么?

What is the best way to eliminate these cycles from the result of indirect(user1,user2)?

推荐答案

您可以制定一个规则，传递您目前见过"的额外用户列表，并忽略源自这些用户的关注:follows(A，B，看到).

You can make a rule that passes an extra list of users that you have "seen" so far, and ignore follows originating from these users: follows(A, B, Seen).

为此，定义一个包含实际规则的遵循传递"规则，如下所示:

To do that, define a "follow transitive" rule that wraps the actual rule, like this:

follows_tx(A, B) :- follows(A, B, []).

现在你可以这样定义 follows/3 规则:

Now you can define follows/3 rule this way:

follows(A, B, Seen) :-
    not_member(B, Seen),
    follows(A, B).
follows(A, B, Seen) :-
    follows(A, X),
    not_member(X, Seen),
    follows(X, B, [A|Seen]).

基本子句说，如果B后面有一个关于A的事实，只要我们没有看到B，我们就认为这个谓词被证明了代码>之前.

The base clause says that if there is a fact about A following B, we consider the predicate proven as long as we have not seen B before.

否则，我们找到关注A的人，通过检查not_member/2来检查我们还没有看到该用户，最后查看该用户是否关注B，直接或间接.

Otherwise, we find someone who follows A, check that we have not seen that user yet by checking not_member/2, and finally see if that user follows B, directly or indirectly.

最后，这里是如何定义not_member:

Finally, here is how you can define not_member:

not_member(_, []).
not_member(X, [H|T]) :- dif(X, H), not_member(X, T).

演示.

这篇关于Prolog:从间接关系中消除循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！