Prolog探路者

Question

我对探路者的东西很感兴趣，并在 2011 年的网站上找到了一个很酷的例子，但没有对代码的任何解释。我了解它的作用，但不了解这些步骤的工作原理。因此，例如，这些是边缘：

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

通过这个我可以判断它们之间是否有路径：

path(X,Y,[X,Y]):- edge(X,Y).
path(X,Y,[X|Xs]):- edge(X,W), path(W,Y,Xs).

输出是这样的：

path(1,6,Xs).
Xs = [1,2,4,5,6];
Xs = [1,4,5,6];
...

但它究竟是如何工作的呢？ [X,Y] 在第一行中做了什么，在第二行中发生了什么？

Answer 1

在这个例子中要理解的关键是递归谓词是如何工作的。首先，递归总是需要一个recursion step（递归使用当前谓词），和一个recursion anchor（递归停止的步骤).解析算法是深度优先搜索，只要有多个选项可供选择（即 ; 或带有签名的不同规则或事实），解释器从上到下和从左到右选择.为了避免无限求值，递归锚点需要像这里一样在顶部，递归步骤应该在第二条规则的右边。

在上面的示例中，当 X 和 Y 之间存在直接边缘时递归停止，因为那是路径结束的地方。请记住，规则是从右到左的含义。由于第三个参数是一个输出参数（你想要得到的结果），所以需要先在锚点中初始化它。 [X,Y] 通过以包含路径的最后两个元素的列表开始它来做到这一点。该规则等同于以下内容：

path(X,Y,Result):- edge(X,Y), Result = [X,Y].

第二条规则旨在寻找中间路径元素：它假设有一个edge(X,W)到一个中间元素W，然后是一个从W到[=16=的路径].解释器将尝试从 X 到可能的 W 的每条边。如果存在从 W 到 Y 的路径，则也存在从 X 到 Y 的路径，并且第二条规则对该步骤成立。递归使用谓词（第三个参数中的路径列表）的结果将是 Xs。因此，当前步骤中需要做的就是将 X 添加到结果列表 ([X|Xs])。同样，这相当于：

path(X,Y,Result):- edge(X,W), path(W,Y,Xs), Result=[X|Xs].

长话短说：结果列表从递归锚中的最后两个元素开始，然后通过所有递归步骤向后传递，并且每个步骤将其当前 X 添加到前面列表。

当然，当数据（和路径）中存在循环时，递归仍然可以是无限的，就像示例中那样。如果你想避免这样的循环（以及可能不需要的解决方案，例如元素多次出现的路径），你可以跟踪已经访问过的元素：

path(X,Y,[X,Y],V):- \+member(X,V),\+member(Y,V),edge(X,Y).
path(X,Y,[X|Xs],V):- \+member(X,V),edge(X,W), path(W,Y,Xs,[X|V]).

在此解决方案中，附加第四个参数中的列表将已访问的项目收集在附加列表中。使用 \+member(X,V) 可以检查当前 X 是否已包含在 V 中。还有其他方法可以实现，例如仅使用 V 作为结果在锚中恢复它。 V 需要在查询中使用空列表进行初始化：

?- path(1,6,R,[]).
R = [1, 2, 4, 3, 6] ;
R = [1, 2, 4, 3, 7, 5, 6] ;
...

Prolog探路者

Prolog pathfinder

prolog