Определение рефлексивного переходного закрытия

Многие предикаты по существу используют некоторую форму транзитивного замыкания только для того, чтобы обнаружить, что завершение тоже должно быть рассмотрено. Почему бы не решить эту проблему раз и навсегда с помощью 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).

Есть ли случаи, когда это определение нельзя использовать для реализации транзитивного замыкания?

Почему Dif / 2?

Чтобы подробно ответить на комментарий @ WouterBeek: dif/2 или iso_dif/2 идеально подходят, потому что они могут показать или сигнализировать о потенциальных проблемах. Однако в текущих реализациях цикл верхнего уровня часто скрывает актуальные проблемы. Рассмотрим цель closure0(\_^_^true,a,b), которая, безусловно, сама по себе довольно проблематична. При использовании следующих систем актуальная проблема напрямую не видна.

| ?- closure0(\_^_^true,a,b). % SICStus
yes

?- closure0(\_^_^true,a,b).   % SWI
true ;
true ;
true ...

Оба цикла верхнего уровня не показывают того, что мы действительно хотим видеть: висящих ограничений. В SICStus нам нужна псевдопеременная для подстановки, в SWI запрос должен быть заключен в call_residue_vars/2. Таким образом теперь отображаются все переменные, к которым привязаны ограничения.

| ?- 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) ...

prolog meta-predicate prolog-toplevel transitive-closure
person false    schedule 15.11.2014    source источник
comment
Почему вы используете nonmember/2 i.o. \+ memberchk/2? Вероятно, для этого есть хороший вариант использования, но я не могу его придумать сам.   -  person Wouter Beek    schedule 16.11.2014
comment
@WouterBeek: \+ memberchk/2 или \+member/2 дают неверные результаты, если задействованы переменные. nonmember/2 с dif/2 или iso_dif/2 не имеют этой проблемы.   -  person false    schedule 16.11.2014

Ответы (1)


arrow_upward
19
arrow_downward

Это полезно, но, на мой взгляд, еще не идеально, потому что я не могу вырезать повторяющиеся пути в момент их создания.

Рассмотрим с полным графиком 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).

Следующий запрос теперь имеет сверхэкспоненциальное время выполнения, хотя на самом деле закрытие может быть найдено за полиномиальное время:

?- 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)

Было бы здорово, если бы более эффективный способ определения замыкания также мог быть выражен с помощью этого мета-предиката.

Например, обычно можно просто использовать алгоритм Уоршалла для вычисления замыкания в кубическом времени с кодом, похожим на:

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):

?- 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.
person mat    schedule 19.11.2014
comment
Не уверен, как это можно сделать в общем случае: пока есть основные значения, это можно вообразить, но кто должен постоянно проверять надежность? - person false; 25.11.2014