如何表达传递关系 [英] How to express a transitive relationship

问题描述

我想表达一种传递关系.如果 A 引用 B 和 B 引用 C，则 A 引用 C.我有这个:

I want to express a transitive relationship. If A references B and B references C then A references C. I have this:

proj(A).
proj(B).
proj(C).
ref(A,B).
ref(B,C).

当我使用 proj(A) 查询时，我得到:

When I query using proj(A) I obtain:

[46] ?-proj(A).
A = _639

[46] ?-proj(A).
A = _639

_639"是什么意思?我期待是或否，并得到了那种陌生感.我需要添加一条规则来说明:

What does "_639" mean? I expected a yes or no and got that strangeness. I need to add a rule to say:

ref(A,C). 并得到 YES.理想情况下，如果可能，我想展示这种关系是如何产生的:(A => B => C).

ref(A,C). and get YES. Ideally, if possible, I would like to show how this relationship came about: (A => B => C).

推荐答案

_639 是一个未实例化的匿名变量.你的事实"有变量而不是原子.例如:

The _639 is an uninstantiated, anonymous variable. Your "facts" have variables rather than atoms. For example:

proj(A).   % This has a variable A and means "any A is a project"

所以如果我查询:

:- proj(X).
X = _blah    % anonymous variable: anything is a project!

你需要原子:

proj(a).
proj(b).

查询结果:

:- proj(X).
X = a ;
X = b 

如果你有:

ref(a,b).
ref(b,c).

那么，在 Prolog 中表达传递属性的最简单方法是声明一个规则(或者在 Prolog 中被称为谓词):

Then, the simplest way in Prolog to express a transitive property is by declaring a rule (or what's known as a predicate in Prolog):

ref(A,C) :- ref(A,B), ref(B,C).

这说明，ref(A,C) 为真，如果 ref(A,B) 为真，并且 ref(B,C) 是真的..运行查询:

This says that, ref(A,C) is true if ref(A,B) is true, AND ref(B,C) is true.. Running the query:

:- ref(a,c).
true ;
Out of stack

或者:

:- ref(a,X).
X = b ;
X = c ;
Out of stack

所以这听起来合乎逻辑但有一个问题:由于自我引用，您可能会陷入循环.一个简单的方法是使规则名称与事实不同:

So it sounds logical but has an issue: you can get into a loop due to the self-reference. A simple way around that is to make the rule name different than the fact:

refx(A, B) :- ref(A, B).
refx(A, C) :- ref(A, B), refx(B, C).

现在如果我查询:

:- refx(a, b).
true ;
no

:- refx(a, c).
yes

:- refx(a, X).
X = b ;
X = c
yes

等

但是，如果事实包含自反或交换关系，则仍有可能出现终止问题的情况.例如:

There are still cases where this could have termination issues, however, if the facts contain reflexive or commutative relationships. For example:

ref(a,b).
ref(b,a).
ref(b,c).

在这种情况下，对 refx(a, b) 的查询产生:

In this case, a query to refx(a, b) yields:

| ?- refx(a, b).
true ? ;
true ? ;
true ? ;
...

正如@lambda.xy.x 指出的，这可以通过跟踪我们去过的地方并避免重复访问"来解决:

As @lambda.xy.x points out, this could be resolved by tracking where we've been and avoiding repeat "visits":

refx(X, Y) :-
    refx(X, Y, []).

refx(X, Y, A) :-
    ref(X, Y),
    \+ memberchk((X, Y), A).   % Make sure we haven't visited this case
refx(X, Y, A) :-
    ref(X, Z),
    \+ memberchk((X, Z), A),   % Make sure we haven't visited this case
    refx(Z, Y, [(X,Z)|A]).

现在我们以 refx(a,b) 终止并成功一次:

Now we terminate with refx(a,b) and succeed once:

| ?- refx(a,b).
true ? ;
no
| ?-

和 refx(X, Y) 产生所有的解决方案(尽管由于多次成功，有些重复):

And refx(X, Y) produces all of the solutions (albeit, some repeats due to succeeding more than once):

| ?- refx(X, Y).

X = a
Y = b ? ;

X = b
Y = a ? ;

X = b
Y = c ? ;

X = a
Y = a ? ;

X = a
Y = c ? ;

X = b
Y = b ? ;

X = b
Y = c ? ;

(2 ms) no

这篇关于如何表达传递关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！