1

我目前正在研究 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)再次尝试（最后一条规则的第一个目标），从而循环。但我看不出另一条规则有什么更好的地方。

4

2 回答 2

4

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

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

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

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

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

false但是你可以在任何你想要的地方进一步添加目标1。这种修改后的程序称为。无论您如何插入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 实际上，这只适用于纯单调程序。你的程序就是其中之一

于 2019-03-04T18:06:42.923 回答
1

显然，在这种情况下，目标排序非常重要。如您所见，您的第一个公式允许通过假设的另一个城市 Z 找到从插肩到任何地方的另一个假设连接，该城市的不存在从未被证明，因为您一直在寻找它无限递归。真的，trace 是你最好的朋友，但要做到这一点并非易事。您还必须考虑其中一个、两个或没有一个论点被绑定的所有情况。

你的第二个公式一点也不好，它只是在不同的情况下失败了：

travel(losAngeles, valmont).
ERROR: Out of local stack

我建议通过区分直接连接和多站旅程来使您的逻辑更安全：

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

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

目标顺序现在无关紧要，因为travel总是需要存在一些物理连接（而不是递归）才能继续。

这也使得记录旅程变得更容易，这是您无论如何都想要的（对吧？）：

connection(X,Y, car(X,Y))   :- byCar(X,Y).
connection(X,Y, train(X,Y)) :- byTrain(X,Y).
connection(X,Y, plane(X,Y)) :- byPlane(X,Y).

travel(X,Y,[Part])       :- connection(X,Y,Part).
travel(X,Y,[Part|Parts]) :- connection(X,Z,Part), travel(Z,Y,Parts).

?- travel(valmont, losAngeles, Journey).
Journey = [car(valmont, saarbruecken), train(saarbruecken, paris), plane(paris, losAngeles)]

对于没有有效行程的情况：

travel(losAngeles, valmont, Journey).
false.
于 2019-03-04T15:25:05.687 回答