简单的序言查询
Easy prolog queries
我是 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 的书的建议。
编辑：失败的示例
我想出了以下两个例子：
例如1，规则是
can_connect(a,b,_).
can_connect(a,c,1).
link(1,2).
type(1,a).
type(2,_).
返回的可能解决方案是 [b,c] 这是正确的，因为我们要求 最多 1 link 从 A 到 C 意味着 0 links 也是可以接受的。
在示例 2 中，规则更改为以下内容：
can_connect(a,b,_).
can_connect(a,c,**2**).
link(1,2).
link(1,3).
type(1,a).
type(2,_).
type(3,c).
运行这里的代码returns[c]是错误的。 b 也是一个可接受的解决方案，因为我们再次要求 最多 2 A 到 C links 这意味着只有 1 是可以的。
我整个周末都在寻找解决方案。首先，我相信它会按示例 1 中的预期工作，因为在建议的解决方案中没有实例化从 A 到 C 的 link（其中检查 2 是否可以是 b），因此 can_connect( a,c,1) 未被检查，因此建议的解决方案已被接受。在示例 2 中，已经存在一个 A 到 C link，因此检查 can_connect(a,c,2) 并且拒绝节点 2 具有类型 b 的解决方案，因为规则检查是否存在正好 2 而不是 最多 2 links 从 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？我相信经过一些调试后，这是由于在当前实现中我只检查与 link 相关的 can_connect 规则，即 start 来自节点而不是 end 到节点。但是，我对此完全不确定。
感谢任何帮助。
问题的表示需要消除节点名称的歧义，因此我们可以适当地表示链接
现在我们可以写了
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).
编辑首先，更新的图表，标有已知类型：
我以前的代码只能在非常有限的假设下工作。这是更一般的东西，它使用 'generate and test' 方法检查整个图的约束（正如@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). 失败了...
我是 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 的书的建议。
编辑：失败的示例
我想出了以下两个例子：
例如1，规则是
can_connect(a,b,_).
can_connect(a,c,1).
link(1,2).
type(1,a).
type(2,_).
返回的可能解决方案是 [b,c] 这是正确的，因为我们要求 最多 1 link 从 A 到 C 意味着 0 links 也是可以接受的。
在示例 2 中，规则更改为以下内容：
can_connect(a,b,_).
can_connect(a,c,**2**).
link(1,2).
link(1,3).
type(1,a).
type(2,_).
type(3,c).
运行这里的代码returns[c]是错误的。 b 也是一个可接受的解决方案，因为我们再次要求 最多 2 A 到 C links 这意味着只有 1 是可以的。
我整个周末都在寻找解决方案。首先，我相信它会按示例 1 中的预期工作，因为在建议的解决方案中没有实例化从 A 到 C 的 link（其中检查 2 是否可以是 b），因此 can_connect( a,c,1) 未被检查，因此建议的解决方案已被接受。在示例 2 中，已经存在一个 A 到 C link，因此检查 can_connect(a,c,2) 并且拒绝节点 2 具有类型 b 的解决方案，因为规则检查是否存在正好 2 而不是 最多 2 links 从 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？我相信经过一些调试后，这是由于在当前实现中我只检查与 link 相关的 can_connect 规则，即 start 来自节点而不是 end 到节点。但是，我对此完全不确定。
感谢任何帮助。
问题的表示需要消除节点名称的歧义，因此我们可以适当地表示链接
现在我们可以写了
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).
编辑首先，更新的图表，标有已知类型：
我以前的代码只能在非常有限的假设下工作。这是更一般的东西，它使用 'generate and test' 方法检查整个图的约束（正如@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). 失败了...