不清楚这个 Prolog 深度优先搜索 (DFS) 方法代码是如何工作的

Question

今天一位老师在序言中给了我们这段代码：

dfs_paths(tree(X, void, void), [X]) :- !.
dfs_paths(tree(X, L, _R), [X|Xs])   :- dfs_paths(L, Xs).
dfs_paths(tree(X, _L, R), [X|Xs])   :- dfs_paths(R, Xs).
    
tree(A) :-
   A = tree(i,
          tree(A,
          tree(la,void,void),
          tree(sa,void,void)
       ),
   tree(b,
      tree(lb,void,void),
      tree(sb,void,void)
    )).

他告诉我们代码是一种在 prolog 上运行 DFS 方法的方法，但我们没有收到有关代码如何在每一行上运行的更多信息。

我是使用 prolog 的新手，我正在尝试理解这段代码

谢谢大家！

更新：这是树

Answer 1

显然我们想要通过回溯从树根到它的叶子之一的所有路径。

首先，必须更正树的声明：

树是一个术语built/written，如下所示（N.B。每个文本元素都是小写，否则我们将写下变量而不是常量） :

tree(i,
     tree(a,
          tree(la,void,void),
          tree(sa,void,void)),
     tree(b,
          tree(lb,void,void),
          tree(sb,void,void))).

我们可以简单地通过声明一个 fact 将这棵树作为参数

来存储

tree_storage(
   tree(i,
        tree(a,
             tree(la,void,void),
             tree(sa,void,void)),
        tree(b,
             tree(lb,void,void),
             tree(sb,void,void)))
).

现在的“访问代码”

dfs_paths(+Tree,?Path)

通过 Tree.

给出的树构建（或验证）路径 Path

如果第一个参数看起来像叶节点（即使用具有 3 个参数的仿函数 tree 构建，参数位置 2 和 3 上的常量 void，路径就是节点名称：

dfs_paths(tree(X, void, void), [X]).

根本不需要cut (!)。

否则，如果树的左分支是非void，则提供了通过沿着左分支向下递归生成路径的可能性，并在根树节点的名称前加上，即 X。我们不关心在这里访问正确的分支。为了让编译器不报错，右分支的占位符前面写了一个_：

dfs_paths(tree(X, L, _R), [X|Xs]) :- dif(L,void), dfs_paths(L, Xs).

否则，如果树的右分支是非void，则提供了通过向下右分支递归生成路径的可能性，并在根树节点的名称前加上，即 X。我们不关心在这里访问左分支。为了让编译器不报错，左边分支的占位符前面写了一个_：

dfs_paths(tree(X, _L, R), [X|Xs]) :- dif(R,void), dfs_paths(R, Xs).

将其放在一起并添加一个 format/2 语句来打印正在发生的事情，我们看到 Prolog 通过将三个规则应用于“树”项来尝试所有可能性：

dfs_paths(tree(X, void, void), [X]) :-
   format("At leaf '~q'~n",[X]).
dfs_paths(tree(X, L, _R), [X|Xs]) :- 
   dif(L,void), 
   format("Going down left at inner node '~q'~n",[X]),
   dfs_paths(L, Xs).
dfs_paths(tree(X, _L, R), [X|Xs]) :- 
   dif(R,void),
   format("Going down right at inner node '~q'~n",[X]),
   dfs_paths(R, Xs).

tree_storage(
   tree(i,
        tree(a,
             tree(la,void,void),
             tree(sa,void,void)),
        tree(b,
             tree(lb,void,void),
             tree(sb,void,void)))
).

run(Path) :-
   tree_storage(Tree),    % Tree is our predefined tree
   dfs_paths(Tree,Path).   % A Path is some path through that tree

现在运行这个：

?- run(Path).
Going down left at inner node 'i'
Going down left at inner node 'a'
At leaf 'la'
Path = [i,a,la] ;
Going down right at inner node 'a'
At leaf 'sa'
Path = [i,a,sa] ;
Going down right at inner node 'i'
Going down left at inner node 'b'
At leaf 'lb'
Path = [i,b,lb] ;
Going down right at inner node 'b'
At leaf 'sb'
Path = [i,b,sb] ;
false.

不清楚这个 Prolog 深度优先搜索 (DFS) 方法代码是如何工作的

Not clear on how this Prolog depth first search (DFS) method code works

prolog

depth-first-search