需要递归循环退出语句

Question

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

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）航班（都柏林，都柏林）？蠕变。任何想法如何解决这一问题？

Answer 1

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

您从由一组边（关系）连接的节点网络开始。

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

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

所以，你要问自己，当我有一flight/2两个原子之间的边缘A和B

有两种情况：

1. 如果directFlight/2它们之间有一个（基本情况）
2. 如果有一个中间节点I，使得有一个flight/2from AtoI和 a directFlight/2between I and B。
3. 或者，如果有一个中间节点I，使得directFlight/2在A 和之间有I一个flight/2fromI到B。

flight/2当被要求时，Prolog 会自己找到边缘

flight(sofia, dublin).

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

这是flight/2（第一张图片）的基本情况，所有都是flight/2通过 1 次调用深度flight/2的递归推导出来的，所有都是通过 2 次调用深度的递归推导出来的。

所以：

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

上面的程序可以阅读：

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

逻辑读物是一个（或两个）语句（“程序”），它给出了关于flight/2应该如何结构的约束：

?(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)成立：封闭世界假设。

附录 2

人们经常忘记的是根本不需要递归调用。递归可以“展开”并且边缘到边缘的链接变得明确：

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连接。

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