prolog - 简单的序言查询

Question

我对 Prolog 很陌生，虽然我读过一些书，但我可以肯定地说我的编程大脑不能用 Prolog 的方式思考。我想解决的问题非常简单(我相信)。我将通过一个例子来描述它。

假设我有一个图，其中包含 4 种“类型”的节点和连接节点的 3 条边。类型可以是 A、B、C 或 D，如下图所示(参见图 1)，A 可以与 B 和 C 连接(分别为 A_To_B 和 A_To_C 边)，而 C 可以与 D 连接( C_To_D 边缘)。还有一条图中未显示的附加规则:A 最多可以连接 1 个 C。

我想在Prolog中表达这些简单的规则来解决第二张图所示的问题。有 3 个节点类型缺失(标记为 X?、Y? 和 Z?)。通过在我的脑海中应用上述规则，我可以很容易地找到X？和Z？是 B 类型(因为 A 最多可以连接 1 个 C)，Y 类型？属于 D 类型，因为 C 只能连接到 D。

请为我提供任何帮助吗？我写这篇文章不仅仅是为了选择解决方案。我也想学习 Prolog，所以如果有人建议我写一本向像我这样以前从未研究过 Prolog 概念的人解释 Prolog 的书，我们将非常欢迎。

编辑:失败的示例

我想出了以下两个例子:

例如例1，规则为

can_connect(a,b,_).
can_connect(a,c,1).

link(1,2).

type(1,a).
type(2,_).

返回的可能解决方案是 [b,c]，这是正确的，因为我们请求最多 1 个从 A 到 C 的链接，这意味着 0 个链接也是可以接受的。

在示例 2 中，规则更改为以下内容:

can_connect(a,b,_).
can_connect(a,c,**2**).

link(1,2).
link(1,3).

type(1,a).
type(2,_).
type(3,c).

运行此处的代码会返回 [c]，这是错误的。 b 也是一个可接受的解决方案，因为我们再次需要最多 2 个 A 到 C 链接，这意味着只有 1 个链接就可以了。

我花了这个周末试图找出解决方案。首先，我相信它按照示例 1 中的预期工作，只是因为在建议的解决方案中没有实例化从 A 到 C 的链接(其中检查 2 是否可以是 b)，因此 can_connect(a,c,1) 不是已检查，因此建议的解决方案已被接受。在示例 2 中，已经存在一个 A 到 C 的链接，因此会检查 can_connect(a,c,2)，并且节点 2 具有类型 b 的解决方案会被拒绝，因为规则会检查是否存在完全 2 个，而不是至多 2 个从 A 到 C 的链接。

我找到了一个适用于这些场景但在其他一些场景下失败的解决方案。这是:

% value #3 is the lower bound and #4 is the upper bound.
can_connect(a,b,0,500).
% A C node can be connected by 0, 1 or 2 A nodes
can_connect(a,c,0,2).
can_connect(d,c,1,1).
can_connect(c,e,0,1).

%The same as previous solution
link(1,2).
link(1,3).

% No change here
type(1,a).
type(2,_).
type(3,c).

% No change here
node_type(N, NT) :- 
    type(N, NT), 
    nonvar(NT), 
    !. % assume a node has only one type

% No change here
node_type(N, NT) :-
    assoc_types(Typed),
    maplist(check_connections(Typed), Typed),
    memberchk(N:NT, Typed).

% No change here
assoc_types(Typed) :-
    findall(N, type(N, _), L),
    maplist(typed, L, Typed).

% No change here
typed(N, N:T) :- 
    type(N, T),
    member(T, [a,b,c]).

% Changes here
check_connections(Graph, N:NT) :-
    forall(link(N, M), (
        memberchk(M:MT, Graph),
        can_connect(NT, MT, L, U),
        findall(X, (link(N, X), memberchk(X:MT, Graph)), Ts),
        mybetween(L, U, Ts),
        forall(can_connect(NT, Y, LM, UM), (
            findall(P, (link(N,P),memberchk(P:Y, Graph)), Ss),
            length(Ss, SsSize ),
            SsSize>=LM,
            SsSize=<UM
        ))
    )).

% It is used to find if the length of a list is between two limits.
mybetween(Lower, Upper, MyList) :-
    length(MyList, MySize),
    MySize=<Upper,
    MySize>=Lower.

此解决方案在此示例中失败

在此示例中，X?必须始终是 b，Y？必须始终是 C 和 Z 吗？必须始终是 D。它找到 X？和Y？正确但不是Z？我相信经过一些调试后，这是由于在当前实现中我只检查与从节点开始的链接相关的 can_connect 规则，而不是与从节点开始的链接相关的 can_connect 规则，而不是与从节点开始的链接相关的 can_connect 规则到一个节点。不过，我对此完全不确定。

感谢任何帮助。

Answer 1

问题的表示需要消除节点名称的歧义，以便我们可以适本地表达链接

现在我们可以写了

can_connect(a,b,_).
can_connect(a,c,1).
can_connect(c,d,_).

link(1,2).
link(1,3).
link(1,4).
link(4,5).
link(4,6).
link(7,4).
link(7,8).

type(1,a).
type(2,b).
type(3,_).
type(4,c).
type(5,d).
type(6,_).
type(7,a).
type(8,_).

Prolog中的下划线(匿名变量)的作用类似于SQL中的NULL，它可以取任意值。

所以，第一个片段

node_type(N, NT) :- type(N, NT), nonvar(NT), !. % assume a node has only one type

可以用来表达我们对问题的了解。

事实 can_connect/3 可以这样读

a can connect to any number of b
a can connect to just 1 c
etc

如果我们不知道节点类型，则需要一个复杂的规则，从目标节点的类型推断源节点的类型，并考虑计数约束，例如

node_type(N, NT) :-
    link(M, N),
    type(M, MT),
    can_connect(MT, NT, C),
    aggregate(count, Y^(link(M, Y), type(Y, NT)), C).

?- forall(between(1,8,N), (node_type(N,T),writeln(N:T))).
1:a
2:b
3:b
4:c
5:d
6:d
7:a
8:b
true.

编辑如果你的Prolog没有库( aggregate )，从那里加载aggregate/3，你可以尝试

node_type(N, NT) :-
    link(M, N),
    type(M, MT),
    can_connect(MT, NT, C),
    findall(t, (link(M, Y), type(Y, NT)), Ts), length(Ts, C).

编辑首先，更新的图表，用已知的类型标记:

我以前的代码只能在非常有限的假设下工作。这是更通用的内容，它使用“生成和测试”方法检查整个图表的约束(如@false 评论所建议)。

node_type(N, NT) :-
    assoc_types(Typed),
    maplist(check_connections(Typed), Typed),
    memberchk(N:NT, Typed).

assoc_types(Typed) :-
    findall(N, type(N, _), L),
    maplist(typed, L, Typed).

typed(N, N:T) :- type(N, T), member(T, [a,b,c,d]).

check_connections(Graph, N:NT) :-
    forall(link(N, M), (
        memberchk(M:MT, Graph),
        can_connect(NT, MT, C),
        aggregate(count, X^(link(N, X), memberchk(X:MT, Graph)), C)
    )).

现在？-node_type(4,X)。失败...