定义一条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/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更简单，更平易近人，特别是新手。 你会同意吗？
我没有看到在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”参数。
