如何在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(如在英语复数中，被访问节点s(。对于图，这是特别是推荐的，因为简单的V可以很好地解释为单个"；顶点"；。

(未测试溶液。(