1

我正在学习 Prolog，但我发现在解释我的教授提出的幻灯片时遇到了一些困难。

从表示图的两个节点之间是否存在路径的经典程序开始，这个：

edge(a,b).
edge(b,c).
edge(a,e).
edge(c,d).
edge(d,e).
edge(f,e).

path(X,Y) :- edge(X,Y).

path(X,Y) :- path(X,Z),
             edge(Z,Y).

他介绍了一个使用谓词的新版本：path(X,Y,Path)如果图中存在 X 和 Y 之间的路径并且Path是访问节点的列表，则为 TRUE

于是他给了我之前程序的以下新版本：

/* BASE CASE: exist an edge between X and Y, so the Path is
              the couple [X,Y]
*/
path(X,Y,[X,Y]) :- edge(X,Y).

path(X,Y,P) :- path(X,Z,P1),
               edge(Z,Y),
               lastelem(P,Y,P1).

基本情况非​​常简单：如果存在连接 X 和 Y 的边，则确实存在从 X 到 Y 的路径，并且访问节点的列表是 [X,Y]

我对第二条规则有一些问题：如果 X 和 Y 不是仅通过一条边连接，因此 X 和 Y 之间存在路径，则 X 和另一个节点 Z 之间必须存在路径（并且 P1 是此路径中访问节点的列表）将 Z 连接到最终节点 Y 的一条边。

这很简单......问题在于幻灯片中未提供的最后一个谓词lastelem/3（所以我不知道它究竟做了什么）：

lastelem(P,Y,P1).

我认为它会生成 P 在 P1 中插入 Y 或类似的东西......

你对它有更精确的想法以及这个谓词的可能实现吗？

4

3 回答 3

3

无需自己编写递归代码来重新发明轮子。

简单地定义一个二元关系edge/2......

edge(a,b).
edge(b,c).
edge(a,e).
edge(c,d).
edge(d,e).
edge(f,e).

...并使用 path/4！

?- path(edge,Path,From,To).
  Path = [To]       , From = To
; Path = [a,b]      , From = a, To = b 
; Path = [a,b,c]    , From = a, To = c
; Path = [a,b,c,d]  , From = a, To = d
; Path = [a,b,c,d,e], From = a, To = e
; Path = [b,c]      , From = b, To = c
; Path = [b,c,d]    , From = b, To = d
; Path = [b,c,d,e]  , From = b, To = e
; Path = [a,e]      , From = a, To = e
; Path = [c,d]      , From = c, To = d
; Path = [c,d,e]    , From = c, To = e
; Path = [d,e]      , From = d, To = e
; Path = [f,e]      , From = f, To = e 
; false.
于 2015-08-05T07:04:47.607 回答
0

教授可能想附加Y到P：

lastelem(Lst0, X, Lst) :-
    append(Lst0, [X], Lst).

[不过，这是一个非常愚蠢的想法，因为附加到列表需要线性时间。一个恒定时间的解决方案是预先添加元素：

% I wouldn't actually write a predicate for this, but nevertheless:
lastelem(Lst, X, [X|Lst]).

这以相反的顺序给出了路径，但一个单一的reverse/2解决方案。]

于 2013-05-01T16:56:28.420 回答
0

我可能会做类似的事情：

path(X,Y,Path) :-
  path(X,Y,T) ,
  reverse(T,Path)
  .

path( X , Y , [] ) :- % a path exists between X and Y:
  connected(X,Y)      % - if they are directly connected
  .                   %
path( X , Y , P  ) :- % a path exists between X and Y:
  connected(X,T) ,    % - if X is connected to another node (T)
  T \= Y ,            % - and T is not the destination (Y)
  not visited(T,P) ,  % - and T has not yet been visited
  path(T,Y, [X|P])    % - and a path exists between T and Y
  .                   %

connected(X,Y) :- edge(X,Y) . % two nodes are connected if they are
connected(X,Y) :- edge(Y,X) . % if they are adjacent adjacent.

visited(X,[X|Xs]) :- ! .             % a node is visited
visited(X,[_|Xs]) :- visited(X,Xs) . % if it exists in the list of already-visited nodes
于 2013-05-01T17:26:02.573 回答