路径/小径/步行的定义

Question

路径/小径/步行的定义许多谓词定义了一种由通过二进制关系定义的边缘构建的非循环路径，非常类似于定义传递闭包..因此需要一个通用定义。请注意，图论中定义的概念并不能很容易地与人们普遍期望的相匹配。最值得注意的是，我们对边缘的名称不感兴趣。更糟糕的是，图论也发生了一些变化，引入了步行，注意到传统上，一条路是指现在通常被称为开放步行的一条路。现在，在没有任何限定条件的情况下，路径通常被理解为简单，这意味着没有顶点(因此没有边)被重复。(“链”一词也用于指所有顶点和边都是不同的游走。)所以我的问题是：如何命名和定义这个功能？到目前为止，我所做的是界定：path(Rel_2, Path, X0,X)第一个论点必须是这种关系的延续。然后要么是Path或者一对顶点。示例用法n(a, b). n(b, c). n(b, a). ?- path(n,Xs, a,X). Xs = [a], X = a ; Xs = [a, b], X = b ; Xs = [a, b, c], X = c ; false.实施:- meta_predicate path(2,?,?,?). :- meta_predicate path(2,?,?,?,+). path(R_2, [X0|Ys], X0,X) :-    path(R_2, Ys, X0,X, [X0]). path(_R_2, [], X,X, _). path(R_2, [X1|Ys], X0,X, Xs) :-    call(R_2, X0,X1),    non_member(X1, Xs),    path(R_2, Ys, X1,X, [X1|Xs]). non_member(_E, []). non_member(E, [X|Xs]) :-    dif(E,X),    non_member(E, Xs).

Answer 1

定义一下path/4是像这样吗？

path(R_2, Xs, A,Z) :-                   % A path `Xs` from `A` to `Z` is ...
   walk(R_2, Xs, A,Z),                  % ... a walk `Xs` from `A` to `Z` ...
   all_dif(Xs).                         % ... with no duplicates in `Xs`.

为了帮助普遍终止，我们交换了上面的两个目标.

path(R_2, Xs, A,Z) :-
   all_dif(Xs),                         % enforce disequality ASAP
   walk(R_2, Xs, A,Z).

..并使用以下延迟实现all_dif/1:

all_dif(Xs) :-                          % enforce pairwise term inequality
   freeze(Xs, all_dif_aux(Xs,[])).      % (may be delayed)

all_dif_aux([], _).
all_dif_aux([E|Es], Vs) :-               
   maplist(dif(E), Vs),                 % is never delayed
   freeze(Es, all_dif_aux(Es,[E|Vs])).  % (may be delayed)

walk/4定义如下path/4和path/5任择议定书：

:- meta_predicate walk(2, ?, ?, ?).
walk(R_2, [X0|Xs], X0,X) :-
   walk_from_to_step(Xs, X0,X, R_2).

:- meta_predicate walk_from_to_step(?, ?, ?, 2).
walk_from_to_step([], X,X, _).
walk_from_to_step([X1|Xs], X0,X, R_2) :-
   call(R_2, X0,X1),
   walk_from_to_step(Xs, X1,X, R_2).

以上海事组织path/4是更简单和更平易近人的，特别是对于新手。你同意吗？