Prolog递归和递归调用的构建输出 [英] Prolog recursion and building output from recursive calls

问题描述

我正在通过 http://www.learnprolognow.org 学习Prolog，但在理解如何根据实践会议3.4，问题3，使用另一个递归调用的结果来递归地构建变量。最初的问题是直接递归调用，以确定路由是否可行。但是后续问题要求您显示到达路线终点的实际路径。

I am learning Prolog via http://www.learnprolognow.org and I am having some trouble understanding how to recursively build up a variable with results from another recursive call, as per Practical Session 3.4, question 3. The initial problem is a straight-forward recursive call to determine if a route is feasible. But the follow-on problem asks you to show the actual path to get to the end of the route.

我们为您提供以下旅行信息知识库：

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

写一个谓词旅行/ 2，确定是否有可能
通过将汽车，火车和
飞机旅行链接在一起，从一个地方到另一个地方。例如，您的程序应该对
查询travel（valmont，raglan）回答是。

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

后续问题是：

因此，通过使用travel / 2来查询上述数据库，您可以发现
可以从瓦尔蒙特飞往拉格伦。如果您计划
这样的航程，那已经是一件有用的事情了，但是您可能会希望
拥有从Valmont到Raglan的确切路线。
写一个谓词travel / 3，它告诉您
从一个地方旅行到另一个地方时该走哪条路线。例如，程序应
响应

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

到查询travel（valmont，losAngeles，X）

to the query travel(valmont,losAngeles,X)

我一直在努力用一系列go（从（到），显示出旅程的后续步骤。它看起来像一个递归问题，但我不知道应该如何解决。这项技术对于Prolog编程而言似乎很基础，并且我对解决该问题的思考过程非常感兴趣，并且希望您能提供任何见识。

I have been struggling to populate X with a series of go(From,To) that show the successive steps of the journey. It looks like a recursive problem but I do not know how one should go about tackling it. This technique seems fundamental to Prolog programming, and I am quite interested in the thinking process to solve this problem and I look forward to any insight you can provide.

推荐答案

我对此很满意。我对您的第一个解决方案进行了更改，只是为了消除一些冗余。我用谓词 connected / 2 概括了 by_car / 2 ， by_train / 2 和 by_plane / 2 事实：

I had a go at this. I made one change to your first solution, just to remove some redundancy. I used the predicate connected/2 to generalize the relationship common to all connections appearing in the by_car/2, by_train/2, and by_plane/2 facts:

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 上的递归关系：

Then I defined travel/2 as a recursive relationship over connected/2:

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

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

Turning to travel/3, notice that the final connection in the nested go... terms is a structure go/2, but the rest are go/3s. So we need to populate X with a series of nested go/3 structures that terminate in a go/2. This last is our base condition. Then it is simply a matter of repeating the second clause of travel/2, but including a go/3 in the third argument that will capture the values instantiated to From and Through on each iteration:

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

这篇关于Prolog递归和递归调用的构建输出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！