Prolog 中的递归 - 寻找城市之间的路径

Question

我正在努力完成 this page 底部的练习。我发现自己对数字 3 完全困惑。

We are given the following knowledge base of travel information:

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

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

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

很容易确定是否可以在两个城市之间旅行。我只是这样做:

connected(X, Y) :- byCar(X, Y); byTrain(X, Y); byPlane(X, Y).
travel(X, Y) :- connected(X, Y).
travel(X, Z) :- connected(Y, Z), travel(X, Y).

但是，当我必须实际将路径与变量统一时，我感到非常困惑!

我是这样写的:

connected(X, Y) :- byCar(X, Y); byTrain(X, Y); byPlane(X, Y).
connected(Y, Z, Out) :- connected(Y, Z).
travel(X, Y, Out) :- connected(X, Y).
travel(A, Z, Out) :- connected(Y, Z),travel(A, Y, connected(Y, Z, Out)).

并叫 travel(valmont, losAngeles,X).
除了最后的匿名变量之外，在跟踪过程中还有一个点显示正确的路径:
travel(valmont, metz, connected(metz, paris, connected(paris, losAngeles, _17)))
但我实际上不知道如何将其与变量 X 统一起来!

我真的无法围绕这一点。谁能给我一个提示，以插入我朝着正确的方向前进？是否只有我缺少的终止条件或什么？

编辑:

我现在有:

connected(X,Y) :- byCar(X,Y);byTrain(X,Y);byPlane(X,Y).

go(X,Y) :- connected(X,Y).

travel(X,Y,go(X,Y)) :- connected(X,Y).
travel(A,Z,Path) :- travel(Y,Z,Path),go(A,Y,Path).

go(A,Y,Path) :- travel(A,Y,Path).

但它会像这样卡住:

4    4  Exit: byPlane(paris,losAngeles) ? 
3    3  Exit: connected(paris,losAngeles) ? 
2    2  Exit: travel(paris,losAngeles,go(paris,losAngeles)) ? 
5    2  Call: go(metz,paris,go(paris,losAngeles)) ? 
6    3  Call: travel(metz,paris,go(paris,losAngeles)) ? 
7    4  Call: travel(_217,paris,go(paris,losAngeles)) ? 
8    5  Call: travel(_242,paris,go(paris,losAngeles)) ? 
9    6  Call: travel(_267,paris,go(paris,losAngeles)) ? 
10    7  Call: travel(_292,paris,go(paris,losAngeles)) ? 

我玩过它，但我无法让它构建整个 go(a,b,go(b,c))等等...

Answer 1

我会给你递归的基本情况:

travel(X, Y, go(X, Y)) :- connected(X, Y).

递归情况看起来非常相似，除了 go/3您正在构建的术语必须将位置作为其前两个参数，并将路径(另一个 go/2 或 go/3 术语)作为其第二个参数。