需要递归循环退出语句 [英] Recursive loop exit statement needed

问题描述

这是一个简单的递归序言示例.我不知道在哪里，或多或少地如何声明退出语句.试飞(sofia, dublin) 应该返回true，但它会在最后一步不断检查你是否可以directFlight(dublin, dublin).代码如下:

this is a simple prolog example of recursion. I cannot figure out where, and more or less how, to declare the exit statement. The test flight(sofia, dublin) should return true, but it keeps checking at the last steps if you can directFlight(dublin, dublin). Here is the code:

directFlight(sofia, varna).
directFlight(sofia, paris).
directFlight(sofia, london).
directFlight(london, edinburg).
directFlight(paris, new_york).
directFlight(new_york, seattle).
directFlight(london, dublin).

flight(City1, City2) :- 
   directFlight(City1, City3),      
   flight(City3, City2).

输出:

 [trace]  ?- flight(sofia, dublin).
   Call: (8) flight(sofia, dublin) ? creep
   Call: (9) directFlight(sofia, _878) ? creep
   Exit: (9) directFlight(sofia, varna) ? creep
   Call: (9) flight(varna, dublin) ? creep
   Call: (10) directFlight(varna, _878) ? creep
   Fail: (10) directFlight(varna, _878) ? creep
   Fail: (9) flight(varna, dublin) ? creep
   Redo: (9) directFlight(sofia, _878) ? creep
   Exit: (9) directFlight(sofia, paris) ? creep
   Call: (9) flight(paris, dublin) ? creep
   Call: (10) directFlight(paris, _878) ? creep
   Exit: (10) directFlight(paris, new_york) ? creep
   Call: (10) flight(new_york, dublin) ? creep
   Call: (11) directFlight(new_york, _878) ? creep
   Exit: (11) directFlight(new_york, seattle) ? creep
   Call: (11) flight(seattle, dublin) ? creep
   Call: (12) directFlight(seattle, _878) ? creep
   Fail: (12) directFlight(seattle, _878) ? creep
   Fail: (11) flight(seattle, dublin) ? creep
   Fail: (10) flight(new_york, dublin) ? creep
   Fail: (9) flight(paris, dublin) ? creep
   Redo: (9) directFlight(sofia, _878) ? creep
   Exit: (9) directFlight(sofia, london) ? creep
   Call: (9) flight(london, dublin) ? creep
   Call: (10) directFlight(london, _878) ? creep
   Exit: (10) directFlight(london, edinburg) ? creep
   Call: (10) flight(edinburg, dublin) ? creep
   Call: (11) directFlight(edinburg, _878) ? creep
   Fail: (11) directFlight(edinburg, _878) ? creep
   Fail: (10) flight(edinburg, dublin) ? creep
   Redo: (10) directFlight(london, _878) ? creep
   Exit: (10) directFlight(london, dublin) ? creep
   Call: (10) flight(dublin, dublin) ? creep
   Call: (11) directFlight(dublin, _878) ? creep
   Fail: (11) directFlight(dublin, _878) ? creep
   Fail: (10) flight(dublin, dublin) ? creep
   Fail: (9) flight(london, dublin) ? creep
   Fail: (8) flight(sofia, dublin) ? creep
false.

问题在这里:失败:(10)飞行(都柏林，都柏林)?蠕变.任何想法如何解决这个问题?

The issue is here at: Fail: (10) flight(dublin, dublin) ? creep. Any ideas how to fix this?

推荐答案

不要考虑需要退出语句的循环.事实上，根本不要使用调试器，即使您知道 Prolog 处理器中发生的事情，它也会非常令人困惑.

Do not think in terms of loops needing exit statements. In fact, don't use the debugger at all, it's mightily confusing even if you DO know what is going on in the Prolog Processor.

您从由一组边(关系)连接的节点网络开始.

You start off with a network of nodes connected by a set of edges (the relation).

在这种情况下，节点由原子(表示城市)表示，边的集合称为 directFlight/2.

In this case, the nodes are represented by atoms (denoting cities), the set of edges the relation called directFlight/2.

现在您要覆盖另一组边，称为 flight/2.

Now you want to overlay another set of edges, called flight/2.

所以你必须问自己什么时候在两个原子 A 和 B

So you have to ask yourself when do I have a flight/2 edge between two atoms A and B

有两种情况:

1. 如果它们之间存在 directFlight/2(基本情况)
2. 如果有一个中间节点 I 使得有一个 flight/2 从 A 到 I以及 I 和 B 之间的 directFlight/2.
3. 或者，如果有一个中间节点 I 使得 A 和 I 之间有一个 directFlight/2code> 和从 I 到 B 的 flight/2.

1. If there is a directFlight/2 between them (the base case)
2. If there is an intermediate node I such that there is a flight/2 from A to I and a directFlight/2 between I and B.
3. Alternatively, if there is an intermediate node I such that there is a directFlight/2 between A and I and a flight/2 from I to B.

Prolog 会在被请求时自行找到 flight/2 边

Prolog will find the flight/2 edge by itself when asked for

flight(sofia, dublin).

(与关系数据库查找SQL查询的结果相同)但您必须注意终止.上面的替代情况 (3) 将导致成功搜索或错误".情况 (2) 将导致非终止 - 完全是由于 Prolog 的搜索策略(必须对真实世界的机器如何通过网络进行搜索做出决定，在这种情况下，深度优先，最左优先).

(same as a relational database finds the result of an SQL query) but you have to pay some attention to termination. The alternative case (3) above will lead to a successful search or "false". The case (2) will lead to non-termination - entirely due to Prolog's search strategy (where decisions have to be taken on how a real-world machine searches through a network, in this case, depth-first, leftmost first).

这是 flight/2(第一张图片)的基本情况，所有 flight/2 由 1 次调用深度的递归推导出，以及所有 flight/2 由 2 次深度调用的递归推导出.

Here is the base case for flight/2 (first image), all the flight/2 deduced by recursion of 1 call deep, and all the flight/2 deduced by recursion of 2 calls deep.

所以:

directFlight(sofia, varna).
directFlight(sofia, paris).
directFlight(sofia, london).
directFlight(london, edinburg).
directFlight(paris, new_york).
directFlight(new_york, seattle).
directFlight(london, dublin).

flight(City1, City2) :- directFlight(City1, City2).
flight(City1, City2) :- directFlight(City1, City3), flight(City3, City2).

然后:

?- flight(sofia,dublin).
true ;
false.

?- flight(sofia,X).
X = varna ;
X = paris ;
X = london ;
X = new_york ;
X = seattle ;
X = edinburg ;
X = dublin ;
false.

?- flight(X,sofia).
false.

附录 1

以上程序可以阅读:

Addendum 1

The above program can be read:

• 从 LEFT :- 到 RIGHT"(正如 Prolog 所做的那样).这是一种确定 flight/2 事实是否成立或是否可以找到使其为真的值的搜索.
• 从右-:到左".心理意象是不断积累关于 flight/2 的新事实，直到将它们全部收集起来，不再添加任何内容:自下而上的搜索(这对大脑来说更容易，至少对我而言).比搜索更安全，因为您不会因为子句以不幸的方式排列而冒着遇到无限递归陷坑的风险，而某些 Datalog 实现就是这样做的.

• "from LEFT :- to RIGHT" (as Prolog does). It is a search to ascertain whether a flight/2 fact holds or whether values can be found that make it true.
• "from RIGHT -: to LEFT". The mental image is of continually accumulating new facts about flight/2 until one has collected them all and nothing is added anymore: bottom-up search (this is somehow easier on the brain, at least for me). Safer than search as you don't risk hitting an infinite recursion sinkhole just because the clauses are arranged in an unfortunate way, and is what some Datalog implementations do.

逻辑读物是一个(或两个)语句(程序")，它给出了关于 flight/2 应该如何构建的约束:

The logical reading is of a (or two) statement ("the program") that gives constraints about how flight/2 is supposed to be structured:

∀(City1, City2) : 
  (flight(City1, City2) <= 
     directFlight(City1, City2))
∧

∀(City1, City2) :
  (flight(City1, City2) <= 
     (∃City3: directFlight(City1, City3) ∧ flight(City3, City2))

请注意，上面没有任何内容可以排除 flight(X,Y) 可能出于其他原因而不是所述原因.然而，我们假设我们知道 flight(X,Y) 何时成立:封闭世界假设.

Note that there is nothing in the above that precludes that flight(X,Y) might hold for OTHER reasons than the one stated. We assume, however, that we know everything about when flight(X,Y) holds: Closed-World Assumption.

人们经常忘记的一点是根本不需要递归调用.递归可以展开"并且边缘到边缘的链接变得明确:

Something one often forgets is that there need not be a recursive call at all. The recursion can be "unrolled" and the edge-to-edge linking made explicit:

directFlight(sofia, varna).
directFlight(sofia, paris).
directFlight(sofia, london).
directFlight(london, edinburg).
directFlight(paris, new_york).
directFlight(new_york, seattle).
directFlight(london, dublin).

flight(City1, City2) :- directFlight(City1, City2).
flight(City1, City2) :- directFlight(City1, Ia),
                        directFlight(Ia, City2).
flight(City1, City2) :- directFlight(City1, Ia),
                        directFlight(Ia, Ib), 
                        directFlight(Ib, City2).
flight(City1, City2) :- directFlight(City1, Ia),
                        directFlight(Ia, Ib),
                        directFlight(Ib, Ic),
                        directFlight(Ic, City2).

没有一个城市相距超过 3 跳，因此上述程序将找到所有 flight/2 连接.

None of the cities are more than 3 hops apart, so the above program will find all flight/2 connections.

事实上，另一个练习是生成上述程序，将其作为要考虑的最大深度"作为参数.

In fact, another exercise would be to generate the above program, giving it as argument the "max depth" to consider.

这篇关于需要递归循环退出语句的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！