在序言中思考困难。无限递归问题

Question

在阅读一本关于 prolog 的书时，我遇到了这个问题。

% Write a predicate travel_to/2 which determines whether it is possible to 
% travel from one place to another by chaining together car, train, and
% plane journeys. For example, your program should answer yes to the
% query travel_to(valmont,raglan).

by_car(auckland,hamilton).
by_car(hamilton,raglan).
by_car(valmont,saarbruecken).
by_car(valmont,metz).

by_train(metz,frankfurt).
by_train(saarbruecken,frankfurt).
by_train(metz,paris).
by_train(saarbruecken,paris).

by_plane(frankfurt,bangkok).
by_plane(frankfurt,singapore).
by_plane(paris,losAngeles).
by_plane(bangkok,auckland).
by_plane(singapore,auckland).
by_plane(losAngeles,auckland).

travel_to(X,Y) :- ( by_car(X,Y)
                  ; by_train(X,Y)
                  ; by_plane(X,Y)
                  ).
travel_to(X,Y) :-
    travel_to(X,Z),
    travel_to(Z,Y).

我很难看出无限递归的来源。我认为这段代码是这样的：“如果 X 可以直接到达 Y，那么我们就满足谓词。否则让我们看看我们是否可以找到递归连接。是否存在 X 连接到然后连接到 Y 的 Z？

旋转：

?- travel_to(valmont,raglan).
true ; % So it works?
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.9Gb, global: 84.2Mb, trail: 0Kb
ERROR:   Stack depth: 11,028,501, last-call: 0%, Choice points: 12
ERROR:   Probable infinite recursion (cycle):
ERROR:     [11,028,501] user:travel_to(raglan, _22060066)
ERROR:     [11,028,500] user:travel_to(raglan, _22060086)

这应该是错误的：

?- travel_to(losAngeles,metz).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.9Gb, global: 84.1Mb, trail: 0Kb
ERROR:   Stack depth: 11,028,558, last-call: 0%, Choice points: 6
ERROR:   Probable infinite recursion (cycle):
ERROR:     [11,028,558] user:travel_to(raglan, _22059564)
ERROR:     [11,028,557] user:travel_to(raglan, _22059584)

Answer 1

问题是你的第二个条款：

travel_to(X, Y) :-
    <b>travel_to(X, Z)</b>,
    travel_to(Z, Y).

将始终匹配。即使根本没有源自 X 的目的地，travel_to/2 也会简单地回退到递归子句。

即使我们设法解决这个问题，仍然有可能进入无限递归，例如如果有 by_car(a , b), 和 by_train(b, a )，那么prolog可能会搜索一条路径a - b - a - b - ….

基本上有两个问题：

没有保证进度，所以如果没有旅行路径离开X它仍然会继续调用travel_to；和
不能保证我们不会运行进入循环。

我们可以通过引入谓词step/2来解决第一个问题，例如：

step(X,Y) :-
    by_car(X,Y).
step(X,Y) :-
    by_train(X,Y).
step(X,Y) :-
    by_plane(X,Y).

接下来我们可以创建一个 travel_to/2 谓词，它是 step:

的传递闭包

travel_to(X, X).
travel_to(X, Z) :-
    step(X, Y),
    travel_to(Y, Z).

这个谓词解决了保证进度的问题，因为对 step/2 的调用会强制 Prolog 选择一条路径，从而进行跳跃。但是还是可以运行进入循环

我们可以通过维护一个已经访问过的节点列表来解决第二个问题，并拒绝第二次访问同一个节点：

travel_to(X, Y) :-
    travel_to(X, Y, [X]).

travel_to(X, X, _).
travel_to(X, Z, L) :-
    step(X, Y),
    \+ member(Y, L),
    travel_to(Y, Z, [Y|L]).

在序言中思考困难。无限递归问题

Having trouble thinking in prolog. Infinite recursion problem

prolog

transitive-closure