自反传递闭包的定义 [英] Definition of Reflexive Transitive Closure
问题描述
许多谓词本质上使用某种形式的传递闭包,却发现终止也必须被解决.为什么不使用 closure0/3
一劳永逸地解决这个问题:
Many predicates essentially use some form of transitive closure, only to discover that termination has to be addressed too. Why not solve this once and forever with closure0/3
:
:- meta_predicate closure0(2,?,?).
:- meta_predicate closure(2,?,?).
:- meta_predicate closure0(2,?,?,+). % internal
closure0(R_2, X0,X) :-
closure0(R_2, X0,X, [X0]).
closure(R_2, X0,X) :-
call(R_2, X0,X1),
closure0(R_2, X1,X, [X1,X0]).
closure0(_R_2, X,X, _).
closure0(R_2, X0,X, Xs) :-
call(R_2, X0,X1),
non_member(X1, Xs),
closure0(R_2, X1,X, [X1|Xs]).
non_member(_E, []).
non_member(E, [X|Xs]) :-
dif(E,X),
non_member(E, Xs).
是否存在不能使用此定义来实现传递闭包的情况?
Are there cases where this definition cannot be used for implementing transitive closure?
详细回答@WouterBeek 的评论:dif/2
或 iso_dif/2
是理想的,因为它们能够显示或发出潜在问题的信号.然而,在当前的实现中,顶级循环通常隐藏了实际问题.考虑目标 closure0(\_^_^true,a,b)
本身肯定是有问题的.当使用以下系统时,实际问题是不可见的.
To answer @WouterBeek's comment in detail: dif/2
or iso_dif/2
are ideal, because they are able to show or signal potential problems. However, in current implementations the top-level loop often hides the actual issues. Consider the goal closure0(\_^_^true,a,b)
which certainly is quite problematic in itself. When using the following systems the actual problem is directly not visible.
| ?- closure0(\_^_^true,a,b). % SICStus
yes
?- closure0(\_^_^true,a,b). % SWI
true ;
true ;
true ...
两个顶级循环都没有显示我们真正想要看到的:悬空约束.在 SICStus 中,我们需要一个伪变量来产生一些替换,在 SWI 中,查询必须用 call_residue_vars/2
包装.通过这种方式,现在会显示所有附加了约束的变量.
Both top-level loops do not show what we actually want to see: the dangling constraints. In SICStus we need a pseudo variable to produce some substitution, in SWI, the query has to be wrapped with call_residue_vars/2
. In this manner all variables that have constraints attached are now shown.
| ?- closure0(\_^_^true,a,b), Alt=t. % SICStus
Alt = t ? ;
Alt = t,
prolog:dif(_A,a),
prolog:dif(b,_A) ? ;
Alt = t,
prolog:dif(_A,a),
prolog:dif(_B,_A),
prolog:dif(_B,a),
prolog:dif(b,_B),
prolog:dif(b,_A) ...
?- call_residue_vars(closure0(\_^_^true,a,b),Vs). % SWI
Vs = [] ;
Vs = [_G1744, _G1747, _G1750],
dif(_G1744, a),
dif(b, _G1744) ;
Vs = [_G1915, _G1918, _G1921, _G1924, _G1927, _G1930, _G1933],
dif(_G1915, a),
dif(b, _G1915),
dif(_G1921, _G1915),
dif(_G1921, a),
dif(b, _G1921) ...
推荐答案
它很有用,但在我看来还不是很理想,因为我无法在创建它们时剪切重复路径.
It's useful, but in my opinion not yet ideal because I cannot cut duplicate paths at the point of their creation.
考虑一下,完整的图K_n:
n_complete(N, Es) :-
numlist(1, N, Ns),
phrase(pairs(Ns), Es).
adjacent(Edges, X, Y) :- member(edge(X, Y), Edges).
pairs([]) --> [].
pairs([N|Ns]) --> edges(Ns, N), pairs(Ns).
edges([], _) --> [].
edges([N|Ns], X) --> [edge(X,N),edge(N,X)], edges(Ns, X).
以下查询现在具有超指数运行时,尽管实际上可以在多项式时间内找到闭包:
The following query now has super-exponential runtime, although the closure can actually be found in polynomial time:
?- length(_, N), n_complete(N, Es), portray_clause(N),
time(findall(Y, closure0(adjacent(Es), 1, Y), Ys)),
false.
1.
16 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 1982161 Lips)
2.
54 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4548901 Lips)
3.
259 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 14499244 Lips)
4.
1,479 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 16219595 Lips)
5.
9,599 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 27691393 Lips)
6.
70,465 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 28911161 Lips)
7.
581,283 inferences, 0.020 CPU in 0.020 seconds (100% CPU, 29397339 Lips)
8.
5,343,059 inferences, 0.181 CPU in 0.181 seconds (100% CPU, 29488001 Lips)
9.
54,252,559 inferences, 1.809 CPU in 1.808 seconds (100% CPU, 29994536 Lips)
10.
603,682,989 inferences, 19.870 CPU in 19.865 seconds (100% CPU, 30381451 Lips)
如果这个元谓词也可以表达一种更有效的方式来确定闭包,那就太好了.
It would be great if a more efficient way to determine the closure could also be expressed with this meta-predicate.
例如,人们通常会简单地使用 Warshall 算法来计算三次时间的闭包,代码类似于:
For example, one would normally simply use Warshall's algorithm to compute the closure in cubic time, with code similar to:
node_edges_closure(Node, Edges, Closure) :-
warshall_fixpoint(Edges, [Node], Closure).
warshall_fixpoint(Edges, Nodes0, Closure) :-
findall(Y, (member(X, Nodes0), adjacent(Edges, X, Y)), Nodes1, Nodes0),
sort(Nodes1, Nodes),
( Nodes == Nodes0 -> Closure = Nodes0
; warshall_fixpoint(Edges, Nodes, Closure)
).
屈服(与漂亮的声明式 closure0/3
相比具有所有缺点):
Yielding (with all drawbacks in comparison to the nicely declarative closure0/3
):
?- length(_, N), n_complete(N, Es), portray_clause(N),
time(node_edges_closure(1, Es, Ys)),
false.
1.
% 16 inferences, 0.000 CPU in 0.000 seconds (75% CPU, 533333 Lips)
2.
% 43 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1228571 Lips)
3.
% 69 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1769231 Lips)
4.
% 115 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 2346939 Lips)
5.
% 187 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 2968254 Lips)
6.
% 291 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 3548780 Lips)
7.
% 433 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 3866071 Lips)
8.
% 619 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 4268966 Lips)
9.
% 855 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 4500000 Lips)
10.
% 1,147 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4720165 Lips)
etc.
这篇关于自反传递闭包的定义的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!