如何在Prolog中找到图中两个节点之间的直接路径？

Question

我是Prolog的新手，我试图编写一个谓词，它以两个节点和一个图作为参数，然后检查图中这两个节点之间是否存在直接路径。

例如，下图中有一条从n(1)到n(4)的直接路径，从n(1)到n(3)，从n(3)到n(4)

g[n(1), n(4), g([n(1), n(2), n(3), n(4), n(5), n(6), n(7), n(8)],
[e(n(1), n(2)), e(n(1), n(3)), e(n(3), n(4)), e(n(4), n(5)), e(n(5), n(6)), e(n(5), n(7)), e(n(7), n(8))]))

最后

?− dirPath(n(1), n(4), g[n(1), n(4), g([n(1), n(2), n(3), n(4), n(5), n(6), n(7), n(8)],
[e(n(1), n(2)), e(n(1), n(3)), e(n(3), n(4)), e(n(4), n(5)), e(n(5), n(6)), e(n(5), n(7)), e(n(7), n(8))]))

应该返回true.

我的暂定代码如下所示：

edge(n(1),n(2)).
edge(n(1),n(3)).
edge(n(3),n(4)).
edge(n(4),n(5)).
edge(n(5),n(6)).
edge(n(5),n(7)).
edge(n(7),n(8)).

dirPath(A,B, g) :-   % - graph argument still missing.
  move(A,B,[])       % - two nodes are connected,
  .                  % - if one can move from one to the other,

move(A,B,V) :-       % -  and one can move from A to B
  edge(A,X) ,        % - if A is connected to X, and
  not(member(X,V)) , % - one hasn't yet reached X, and
  (                  % - either
    B = X            % - X is the desired destination
  ;                  %   OR
    move(X,B,[A|V])  % - one can get to that destination from X
  )                  
  .                

我的主要问题是，我无法理解如何使我的dirPath谓词接受一个图，因为它是一个参数。

Answer 1

首先，这是：

g[n(1), n(4), g([n(1), n(2), n(3), n(4), n(5), n(6), n(7), n(8)],
[e(n(1), n(2)), e(n(1), n(3)), e(n(3), n(4)), e(n(4), n(5)), e(n(5), n(6)), e(n(5), n(7)), e(n(7), n(8))]))

是无效的语法。术语不能以g[...开头。这可能应该是g([...。

第二，表示并不完全是直观的。n(1)和n(4)的特殊角色是什么？为什么有一个内在的g(...)术语？

尽管如此，很明显哪一部分应该是边缘。让我们定义一个谓词来访问边缘：

graph_edges(Graph, Edges) :-
    Graph = g(_Something, _SomethingElse, g(_Nodes, Edges)).

然后从图中选择一条边：

graph_edge(Graph, Edge) :-
    graph_edges(Graph, Edges),
    member(Edge, Edges).

然后，您可以将其合并到谓词中，如下所示：

dirPath(A, B, Graph) :-
    move(A, B, Graph, []).

move(A, B, Graph, Vs) :-
    graph_edge(Graph, e(A, X)),
    ...

注意，我将变量V更改为Vs。单字母变量名称在一般情况下通常不是很好(在我看来，From和To比A和B更清晰)。列表的单字母变量名特别少见；常见的惯例是为列表添加s (如英文复数、访问节点的)。对于图，这是特别推荐的，因为简单的V很可能被解释为一个单一的“顶点”。

(解决方案未测试)