43

许多谓词定义了某种从通过二元关系定义的边构建的非循环路径，与定义传递闭包非常相似。因此需要一个通用的定义。

请注意，图论中定义的概念并不容易与通常预期的相匹配。最值得注意的是，我们对边缘的名称不感兴趣。

更糟糕的是，图论也发生了一些变化，引入了walk的概念，注意到

传统上，路径指的是现在通常称为开放式步行的路径。如今，当没有任何限定的情况下，路径通常被理解为简单，这意味着没有顶点（因此没有边）重复。（术语链也被用来指代所有顶点和边都不同的游走。）

所以我的问题是：如何命名和定义这个功能？

到目前为止我所做的是定义：

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

3 回答 3

12

这样定义怎么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) :- % 强制成对项不等式
   冻结（Xs​​，all_dif_aux（Xs，[]））。%（可能会延迟）

all_dif_aux（[]，_）。
all_dif_aux([E|Es], Vs) :-               
   maplist (dif(E), Vs), % 从不延迟
   冻结（Es，all_dif_aux（Es，[E|Vs]））。%（可能会延迟）

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

上面的 IMOpath/4更简单，更平易近人，尤其是对于新手。你会同意吗？

于 2015-07-30T12:39:38.640 回答
11

我想专注于命名谓词。

  • 与 不同maplist/2，参数顺序在这里不是最重要的。

  • 谓词名称应该明确各个参数的含义。

到目前为止，我path_from_to_edges最喜欢它，但它也有其优点和缺点。

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

让我们把它分开：

  • pro：path是名词，不能误读动词。对我来说，一个顶点列表是隐含的。

  • pro:from代表顶点，to.

  • con:edges 有点模糊，但在这里使用lambdas是最通用的选择。

  • 缺点：根据维基百科，路径是一条轨迹，其中所有顶点（可能除了第一个和最后一个）都是不同的。所以这需要在描述中加以澄清。

将 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)，但反过来就不行了。

于 2015-06-02T11:49:56.753 回答
4

我看不到在 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 .

如您所见，在这种情况下，算法无法暴力破解。出于这个原因，如果算法没有改进，我建议不要添加“结束节点”作为“路径”参数。

于 2015-05-31T09:25:34.620 回答