Prolog图中连通边的含义

Question

我希望能够在prolog中创建一个谓词，用于检查一个节点是否能够到达图中的另一个节点。例如：Connected(1,X,[[1,3],[3,4],[2,5]])。第一个参数是我想要开始的节点，第二个参数是我想要到达的节点，第三个参数是边的列表。到目前为止，我已经能够实现这个谓词，但是当我尝试使用findall/3获取到达的所有节点时，代码会进入无限循环。

有没有办法停止无限循环，或者我应该从头开始思考这个问题？

下面是我的代码：

 match([X,Y],List):- member([X,Y], List).
 match([X,Y],List):- member([Y,X], List).


go(X,Y,List):-match([X,Y],List).
go(X,Y,List):-match([X,Z],List),go(Z,Y,List).

goes(X,List,List2):-findall(Y,go(X,Y,List),List2).

我是Prolog的新手，但我无法弄清楚我错在了哪里。

- JmRag

---

边的常见表示法是 X-Y 而不是 [X,Y]。 - false

Answer 1

可能是您代码的一个修正建议。

match([X,Y], List, Rest):- select([X,Y], List, Rest).
match([X,Y], List, Rest):- select([Y,X], List, Rest).

go(X,Y,List) :- match([X,Y],List,_).
go(X,Y,List) :- match([X,Z],List,Rest), go(Z,Y,Rest).

goes(X,List,List2) :- findall(Y, go(X,Y,List), List2).

现在匹配“消耗”边缘，避免无限循环。

- CapelliC

Answer 2

看看?- gtrace，goes（1，[[1,3]，[3,4]，[2,5]]，X）的作用。

对于所有递归go：- go，您需要一个停止条件。

在您的情况下，我建议添加一个参数Traversed，它是您已访问的所有节点（或边）的列表。然后，如果您已经访问过它们，就不会再次遍历节点。因此，您递归查看的元素越来越少，并且递归在某个点结束。

许多递归使用谓词！。请查看它。

- User