定义一条path/步道/步行

许多谓词定义了通过二元关系定义的一些非循环path,与定义传递闭包非常类似。 因此需要一个通用的定义。

请注意,图论中定义的概念并不容易匹配通常所期望的。 最值得注意的是,我们对边缘的名字不感兴趣。

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

传统上,path指的是现在通常所说的开放式散步。 如今,当没有任何资格时,通常认为path是简单的,意味着没有顶点(并且因此没有边)被重复。 (术语链也被用来指代所有顶点和边缘是不同的步行。)

所以我的问题是:如何命名和定义这个function?

我迄今所做的是定义:

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

我想专注于谓词的命名。

  • maplist/2不同的是,参数顺序在这里并不重要。

  • 谓词名称应该使各自的论点的含义清晰。

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

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

让我们分开来看看:

  • 亲: path是一个名词,它不能误读一个动词。 对我来说,隐含的顶点列表。

  • 亲:代表一个顶点,也是如此。

  • con: edges有些模糊,但是在这里使用lambda是最通用的select。

  • con:根据维基百科 ,path是所有顶点( 除了可能的第一个和最后一个 )不同的path。 所以这需要在说明中澄清。


使用lambda表示邻居顶点列表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当然是一个名词,而不是一个动词。

关于“path”的含义:path绝对应该允许From=To并且不排除默认情况下(使用成对的项不等式)。 用一个额外的dif(From,To)目标来排除这个问题是很容易的,但是却不能。

如何定义这样的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/4path/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更简单,更平易近人,特别是新手。 你会同意吗?

我没有看到在path / 4中定义参数“start node”和“end node”的原因。 看来,一个简单的path/ 2与规则和节点列表必须是足够的。

如果用户想要一个以某个节点(例如'a')开始的列表,他可以查询语句为:path(some_rule,['a'| Q])。

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

*附录1 *

一些效用目标可以很容易地join,但它们不是主要的主题。 例如,启动节点的path/ 3是:

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

*附录2 *

将最后一个节点添加为参数可能会给出错误的想法,即此参数驱动algorithm,但它不会。 举例来说:

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

并为查询执行跟踪algorithm:

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

正如你所看到的,在这种情况下algorithm没有蛮力。 为此,如果algorithm没有改进,我build议不要把“结束节点”添加为“path”参数。