prolog - 写入未命名变量

Question

我正在 Prolog (gprolog) 中编写一个在图上查找路径的程序。我部分基于 this SO post .

让我举个例子。这是我绘制的示例图:

这是代码最初的样子:

path([Goal],Goal,Goal).
path(P,Start,Goal) :- adjacent(Start,X),
                      \+ (memberchk(X,P)),
                      (
                        Goal=X
                      ;
                        path([Start|P],X,Goal)
                      ).

无论该基本情况是否多余，问题都在这里。我想要的输入样式为

| ?- path(P,a,f).

对于该输入，我会得到输出

P = [a,s,f]

true ?

但是，现有代码的问题在于 memberchk。对于 memberchk(a,P)，它尝试统一，调用 memberchk(a,[a|_])，并返回 true。我不希望发生这种情况，因此我首先检查 P 是否使用 var/1 谓词实例化。因此，我的代码更改为

path([Goal],Goal,Goal).
path(P,Start,Goal) :- var(P), 
                      path([],Start,Goal).
path(P,Start,Goal) :- adjacent(Start,X),
                      \+ (memberchk(X,P)),
                      (
                        Goal=X
                      ;
                        path([Start|P],X,Goal)
                      ).

现在，如果 P 未实例化，我们将使用空列表调用 path/3。 我的问题是这样的:现在我无法在最后打印 P，因为我调用 path([],Start,Goal) 和 P 不再与 [] 关联。

我尝试过使用 write/1 谓词，但它要么在每一步打印出 P ，要么打印出 P = _26 (意思是它打印的是未实例化的 P，而不是 P 的最终值)。

我希望这是一个简单的问题，我对 Prolog 还很陌生。

如果有人问过类似的问题，我们深表歉意；我很乐意被指出其他可能有帮助的问题。在发布此内容之前，我通过 SO 和 Google 进行了搜索。

Answer 1

您需要的概念是累加器

您实际上非常接近:您确实意识到将 P 初始化为 []，并用 [Start|P] 填充它作为你递归是一种工作策略。这称为累加器，要获得最终结果，您只需添加另一个参数。

这是您查询的新 path/3 谓词:

path(P, Start, Goal) :-
    path([], P, Start, Goal).

如您所见，这里我们将 [] 添加为 path/4 的第一个参数，我们的实现如下:

path(L, P, Goal, Goal) :-
    reverse([Goal|L], P).
path(L, P, Start, Goal) :- 
    adjacent(Start, X),
    \+ (memberchk(X, L)),
    path([Start|L], P, X, Goal).

第一个子句用于终止递归。一旦 Start 和 Goal 参数与您注意到的相同，递归就应该结束。当使用累加器时，这意味着我们将累加器与输出参数统一起来。但是，累加器包含相反的答案(并且缺少最终目标)，因此我们有 reverse([Goal|L], P)。

第二个子句与您编写的内容非常相似，但我们现在需要将 P 按原样传递给递归子句。请注意，我已经删除了该子句中的析取，在这种情况下不需要它。

完整代码:

path(P, Start, Goal) :-
    path([], P, Start, Goal).
path(L, P, Goal, Goal) :-
    reverse([Goal|L], P).
path(L, P, Start, Goal) :- 
    adjacent(Start, X),
    \+ (memberchk(X, L)),
    path([Start|L], P, X, Goal).