prolog - Prolog 在目标重新​​排序后不会终止

Question

我目前正在研究 Learn Prolog Now 示例，对于一个练习，如果我对一条规则进行微小更改，我的 KB 会用完本地堆栈。这是知识库：

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

travel(X,Y) :- byCar(X,Y).
travel(X,Y) :- byTrain(X,Y).
travel(X,Y) :- byPlane(X,Y).

和相关规则：

travel(X,Y) :- travel(X,Z), travel(Z,Y).

这是有问题的查询，它用完了堆栈：

?- travel(valmont,losAngeles).

但是，如果我将规则更改为

travel(X,Y) :- travel(Z,Y), travel(X,Z).

然后它工作。

如果我跟踪查询，我会很快陷入这样的困境：

   Redo: (17) travel(raglan, _6896) ? creep
   Call: (18) byPlane(raglan, _6896) ? creep
   Fail: (18) byPlane(raglan, _6896) ? creep
   Redo: (17) travel(raglan, _6896) ? creep
   Call: (18) travel(raglan, _6896) ? creep
   Call: (19) byCar(raglan, _6896) ? creep
   Fail: (19) byCar(raglan, _6896) ? creep
   Redo: (18) travel(raglan, _6896) ? creep
   Call: (19) byTrain(raglan, _6896) ? creep
   Fail: (19) byTrain(raglan, _6896) ? creep
   Redo: (18) travel(raglan, _6896) ? creep
   Call: (19) byPlane(raglan, _6896) ? creep
   Fail: (19) byPlane(raglan, _6896) ? creep
   Redo: (18) travel(raglan, _6896) ? creep
...

但我不明白为什么。难道它不应该只了解 raglan 是一个终端站，因此它必须再回溯一个级别吗？

谢谢！

编辑：我使用 SWI Prolog

编辑：我一步步解决后发现了问题。在插肩的情况下，任何地方都没有规则。因此，在尝试之后byPlane, byTrain, byCar，它travel(raglan, X)再次尝试（最后一条规则的第一个目标），从而循环。但我看不出另一条规则有什么更好的地方。

标签： prologbacktrackingfailure-slicenon-termination

Answer 1

您需要澄清“它有效”的含义。事实上，谓词的两个版本travel/2都不会终止。但是碰巧找到了针对高度特定查询的解决方案。

现在询问?- travel(hamilton, losAngeles).两者的循环。

因此，您的修复仅适用于某些查询，但不适用于其他查询。没有更可靠的出路吗？

一般来说，Prolog 产生的非常精确的答案替换序列很难预测。您将不得不模拟 Prolog 采取的每一个微小步骤。

另一方面，有一个非常相关的概念称为（通用）终止，它更容易预测，因为它独立于程序中的许多细节，例如事实出现的顺序。查询通用终止的最简单方法是在false查询末尾添加目标。

false但是你可以在任何你想要的地方进一步添加目标¹。这种修改后的程序称为故障片。无论您如何插入false以下保持：

如果故障片没有终止，那么您的原始程序也不会终止。

现在考虑 的两个变体的故障切片travel/2：

travel(X,Y) :- false , byCar(X,Y)。
travel(X,Y) :- false , byTrain(X,Y)。
travel(X,Y) :- false , byPlane(X,Y)。
旅行（X，Y）：-旅行（X，Z），假，旅行（Z，Y）。

还有你的另一个版本：

travel(X,Y) :- false , byCar(X,Y)。
travel(X,Y) :- false , byTrain(X,Y)。
travel(X,Y) :- false , byPlane(X,Y)。
旅行（X，Y）：-旅行（Z，Y），假，旅行（X，Z）。

两者都没有，也X没有Y被考虑！所以这两个参数不影响终止。因此两个版本都不会终止。也就是说，它们永远不会终止。

现在将此结论与查看迹线的更传统方法进行比较。虽然故障切片允许我们做出一般性结论（“...永不终止”），但特定跟踪只能向您显示特定执行的详细信息。

为了解决这个问题，您需要更改可见部分中的某些内容。我的建议是使用closure/3. 那是：

travel(X, Y) :-
   closure(connexion, X, Y).

connexion(X,Y) :- byCar(X,Y).
connexion(X,Y) :- byTrain(X,Y).
connexion(X,Y) :- byPlane(X,Y).

还是用比较通用的path/4。

---

_{1 实际上，这只适用于纯单调程序。你的程序就是其中之一}