路径/步道/步行的定义

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

我想专注于命名谓词.

• 与此不同maplist/2,参数顺序在这里并不重要.

• 谓词名称应该使各个参数的含义清晰.

到目前为止,我path_from_to_edges最喜欢,但也有它的优点和缺点.

path_from_to_edges(Path,From,To,Edges_2) :-
    path(Edges_2,Path,From,To).

让我们分开吧:

• 亲:path是一个名词,它不能被误读为动词.对我来说,暗示了顶点列表.

• pro:from代表顶点,同样代表顶点to.

• CON:edges 是有些模糊,但使用lambda表达式在这里是最通用的选择.

• con:根据维基百科,路径是一条路径,其中所有顶点(可能除了第一个和最后一个)都是不同的.因此,需要在说明中加以澄清.

将lambdas用于邻居顶点列表Ess:

?- Ess  = [a-[b],b-[c,a]], 
   From = a,
   path_from_to_edges(Path,From,To,\X^Y^(member(X-X_neibs,Ess),member(Y,X_neibs))).
Ess = [a-[b],b-[c,a]], From = a, To = a, Path = [a]     ;
Ess = [a-[b],b-[c,a]], From = a, To = b, Path = [a,b]   ;
Ess = [a-[b],b-[c,a]], From = a, To = c, Path = [a,b,c] ;
false.

编辑2015-06-02

更好的命名的另一个镜头!这更倾向于maplist/2......

graph_path_from_to(P_2,Path,From,To) :-
   path(P_2,Path,From,To).

graph当然,这里是名词,而不是动词.

关于"路径"的含义:路径肯定应该允许From=To而不是默认排除(使用成对术语不等式).通过额外的dif(From,To)目标很容易将其排除在外,但不是相反.

Answer 2

如此定义怎么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由OP 定义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).

上面的IMO path/4更简单,更平易近人,特别是对于初学者.你同意吗？

Answer 3

我不明白在 path/4 中定义参数“起始节点”和“结束节点”的原因。看起来一个带有规则和节点列表的简单的 path/2 就足够了。

如果用户想要一个以某个节点（例如“a”）开头的列表，他可以将语句查询为：path( some_rule, ['a'|Q] )。

例如，用户可以通过以下方式请求长度为 10 的路径：length(P,10), path(some_rule, P)。

* 附录 1 *

一些实用目标可以很容易地添加，但它们不是主要主题。例如，带有起始节点的 path/3 是：

path( some_rule, [start|Q], start ) :- 
  path ( some_rule, [start|Q ] ).   

* 附录 2 *

添加最后一个节点作为参数可能会产生此参数驱动算法的错误想法，但事实并非如此。举例假设：

n(a, b).
n(a, c).
n(a, d).

并跟踪查询的算法执行情况：

[trace]  ?- path( n, P, X, d ).
   Call: (6) path(n, _G1025, _G1026, d) ? creep
   Call: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Exit: (7) path(n, [], d, d, [d]) ? creep
   Exit: (6) path(n, [d], d, d) ? creep
P = [d],
X = d ;
   Redo: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Call: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, b) ? creep

   Call: (8) non_member(b, [a]) ? creep
   Call: (9) dif:dif(b, a) ? creep
   Exit: (9) dif:dif(b, a) ? creep
   Call: (9) non_member(b, []) ? creep
   Exit: (9) non_member(b, []) ? creep
   Exit: (8) non_member(b, [a]) ? creep
   Call: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Call: (9) n(b, _G1118) ? creep
   Fail: (9) n(b, _G1118) ? creep
   Fail: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Redo: (9) non_member(b, []) ? creep
   Fail: (9) non_member(b, []) ? creep
   Fail: (8) non_member(b, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, c) ? creep

   Call: (8) non_member(c, [a]) ? creep
   Call: (9) dif:dif(c, a) ? creep
   Exit: (9) dif:dif(c, a) ? creep
   Call: (9) non_member(c, []) ? creep
   Exit: (9) non_member(c, []) ? creep
   Exit: (8) non_member(c, [a]) ? creep
   Call: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Call: (9) n(c, _G1118) ? creep
   Fail: (9) n(c, _G1118) ? creep
   Fail: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Redo: (9) non_member(c, []) ? creep
   Fail: (9) non_member(c, []) ? creep
   Fail: (8) non_member(c, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, d) ? creep

   Call: (8) non_member(d, [a]) ? creep
   Call: (9) dif:dif(d, a) ? creep
   Exit: (9) dif:dif(d, a) ? creep
   Call: (9) non_member(d, []) ? creep
   Exit: (9) non_member(d, []) ? creep
   Exit: (8) non_member(d, [a]) ? creep
   Call: (8) path(n, _G1113, d, d, [d, a]) ? creep
   Exit: (8) path(n, [], d, d, [d, a]) ? creep
   Exit: (7) path(n, [d], a, d, [a]) ? creep
   Exit: (6) path(n, [a, d], a, d) ? creep
P = [a, d],
X = a .

正如你所看到的，在这种情况下，算法无法暴力破解。因此，如果算法没有改进，我建议不要添加“结束节点”作为“路径”参数。