algorithm - Prolog递归和递归调用的构建输出

Question

我正在通过 http://www.learnprolognow.org 学习 Prolog并且我在理解如何根据实践类(class) 3.4 的问题 3 中的另一个递归调用的结果递归构建变量时遇到了一些困难。最初的问题是直接递归调用以确定路由是否可行。但后续问题要求您显示到达路线终点的实际路径。

我们得到以下旅游信息知识库:

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). 

Write a predicate travel/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(valmont,raglan).

我用下面的代码解决了这个问题:

travel(From,To) :-
 byCar(From,To).

travel(From,To) :-
 byTrain(From,To).

travel(From,To) :-
 byPlane(From,To).

travel(From,To) :-
  byCar(From,NewTo),
  travel(NewTo,To).

travel(From,To) :-
  byTrain(From,NewTo),
  travel(NewTo,To).

travel(From,To) :-
  byPlane(From,NewTo),
  travel(NewTo,To).

后续问题是:

So, by using travel/2 to query the above database, you can find out that it is possible to go from Valmont to Raglan. If you are planning such a voyage, that’s already something useful to know, but you would probably prefer to have the precise route from Valmont to Raglan. Write a predicate travel/3 which tells you which route to take when travelling from one place to another. For example, the program should respond

X  =  go(valmont,metz,go(metz,paris,go(paris,losAngeles)))

to the query travel(valmont,losAngeles,X)

我一直在努力用一系列显示旅程连续步骤的 go(From,To) 来填充 X。它看起来像一个递归问题，但我不知道应该如何解决它。这项技术似乎是 Prolog 编程的基础，我对解决这个问题的思考过程非常感兴趣，我期待您能提供任何见解。

Answer 1

我试了一下。我对您的第一个解决方案做了一个更改，只是为了删除一些冗余。我使用谓词 connected/2 概括出现在 by_car/2、by_train/2 和 中的所有连接的公共(public)关系>by_plane/2 事实:

connected(From, To) :- by_car(From, To).
connected(From, To) :- by_train(From, To).
connected(From, To) :- by_plane(From, To).

然后我将 travel/2 定义为 connected/2 的递归关系:

travel(From, To) :-
    connected(From, To).
travel(From, To) :-
    connected(From, Through),
    travel(Through, To).

转到 travel/3，注意嵌套的 go... 项中的最终连接是结构 go/2，但其余的是 go/3。因此，我们需要使用一系列嵌套的 go/3 结构填充 X，这些结构终止于 go/2。最后一个是我们的基本条件。然后只需重复 travel/2 的第二个子句，但在第三个参数中包含一个 go/3 ，它将捕获实例化到 的值From 和 Through 每次迭代:

travel(From, To, go(From, To)) :-
    connected(From, To).
travel(From, To, go(From, Through, Route)) :-
    connected(From, Through),
    travel(Through, To, Route).