路径/小径/步行的定义 [英] Definition of a path/trail/walk
问题描述
许多谓词定义某种非循环路径，该路径由通过二元关系定义的边构建，非常类似于定义传递闭包.因此需要一个通用的定义.
请注意，图论中定义的概念并不容易符合通常的预期.最值得注意的是，我们对边的名称不感兴趣.
更糟糕的是，图论也发生了一些变化，引入了 walk 的概念, 注意到
<块引用>传统上，路径指的是现在通常称为开放式步行的路径.如今，当没有任何限定的情况下，路径通常被理解为简单，这意味着没有顶点(因此没有边)重复.(术语链也被用来指代所有顶点和边都不同的游走.)
所以我的问题是:如何命名和定义这个功能?
到目前为止我所做的是定义:
path(Rel_2, Path, X0,X)第一个参数必须是关系的延续，这是一个不完整的目标，缺少两个进一步的参数.然后是 Path 或顶点对.
示例用法
n(a, b).n(b, c).n(b, a).?- 路径(n，Xs，a，X).Xs = [a], X = a ;Xs = [a, b], X = b ;Xs = [a, b, c], X = c;错误的.实施
:- meta_predicate(path(2,?,?,?)).:- meta_predicate(path(2,?,?,?,+)).路径(R_2，[X0|Ys]，X0，X):-路径(R_2，Ys，X0，X，[X0]).路径(_R_2，[]，X，X，_).路径(R_2，[X1|Ys]，X0，X，Xs):-调用(R_2，X0，X1)，非成员(X1，Xs)，路径(R_2，Ys，X1，X，[X1|Xs]).非成员(_E，[]).非成员(E，[X|Xs]):-差异(E，X)，非成员(E，Xs).这样定义path/4怎么样?
path(R_2, Xs, A,Z) :- % 从 `A` 到 `Z` 的路径 `Xs` 是 ...walk(R_2, Xs, A,Z), % ... a walk `Xs` 从 `A` 到 `Z` ...all_dif(Xs).% ... `Xs` 中没有重复项.为了帮助通用终止，我们将上述两个目标互换...
路径(R_2, Xs, A,Z) :-all_dif(Xs), % 尽快执行不等式步行(R_2，Xs，A，Z)....并使用 all_dif/1 的以下惰性实现:
walk/4 的定义类似于 OP 给出的 path/4 和 path/5:
:- meta_predicate walk(2, ?, ?, ?).步行(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) :-调用(R_2，X0，X1)，walk_from_to_step(Xs，X1，X，R_2).path/4 上面的
IMO 更简单、更容易上手，尤其是对于新手而言.你同意吗?
Many predicates define some kind of an acyclic path built from edges defined via a binary relation, quite similarly to defining transitive closure. A generic definition is thus called for.
Note that the notions defined in graph theory do not readily match what is commonly expected. Most notably, we are not interested in the edges' names.
Worse, also graph theory has changed a bit, introducing the notion of walk, noting
Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated. (The term chain has also been used to refer to a walk in which all vertices and edges are distinct.)
So my question is: How to name and define this functionality?
What I have done so far is to define:
path(Rel_2, Path, X0,X)
The first argument has to be the continuation of the relation which is an incomplete goal that lacks two further arguments. Then comes either the Path or the pair of vertices.
Example usage
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.
Implementation
:- 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).
How about defining path/4 like this?
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`.
To aid universal termination, we swap the two goals in above conjunction ...
path(R_2, Xs, A,Z) :-
all_dif(Xs), % enforce disequality ASAP
walk(R_2, Xs, A,Z).
... and use the following lazy implementation of 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 is defined like path/4 and path/5 given by the OP:
:- 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).
IMO above path/4 is simpler and more approachable, particularly for novices. Would you concur?
这篇关于路径/小径/步行的定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
