时间戳

首页 > 解决方案 > 需要递归循环退出语句

search - 需要递归循环退出语句

问题描述

这是一个简单的递归序言示例。我不知道在哪里以及或多或少如何声明退出语句。test flight(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）飞行（都柏林，都柏林）？蠕变。任何想法如何解决这一问题？

标签： searchprolog

解决方案

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

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

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

直飞航班

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

所以你必须问自己，我什么时候flight/2在两个原子之间有边A？B

有两种情况：

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

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

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

上面的程序可以阅读：

  • “从LEFT :- 到 RIGHT ”（正如 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连接。

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

推荐阅读