使用绿色和红色裁剪优化程序

Question

下面的Prolog程序确定保险费。保险费取决于车辆的马力和驾驶员的年龄。

calculateCarInsurance(PS, Insurance) :- PS < 60, Insurance = 100.
calculateCarInsurance(PS, Insurance) :- PS >= 60, PS < 100, Insurance = 200.
calculateCarInsurance(PS, Insurance) :- PS >= 100, Insurance = 300.

isInRiskyGroup(Age) :- Age < 25.

calculateCarInsurance(PS, Age, _) :- Age < 18 , fail.

calculateCarInsurance(PS, Age, Insurance) :-
    Age >= 18,
    isInRiskyGroup(Age),
    calculateCarInsurance(PS, I2),
    Insurance is I2 * 2.

calculateCarInsurance(PS, Age, Insurance) :-
    not(isInRiskyGroup(Age)),
    calculateCarInsurance(PS, Insurance).

现在，我需要: a)优化程序与绿色削减，b)改变绿色为红色削减，删除不必要的谓词。程序的行为应该是相同的。

由于我对Prolog中的裁剪一无所知，我将如何处理这个问题？

Answer 1

让我们从基础开始。裁剪操作符是!，并且总是成功。切割不能被回溯过去--就像一个单向的大门。另一种看待它的方法是，它使你致力于到目前为止所做的决定。

裁剪的用法分为几个类别。根据定义，绿色剪切根本不改变程序的运行时语义。绿色切割只是程序员告诉Prolog的一种方式，您已经知道您已经没有解决方案了。如果Prolog不知道没有更多的解决方案，它会问您是否需要另一个解决方案，然后每次都失败。例如，查看min/3的这个实现

min1(X, Y, X) :- X < Y.
min1(X, Y, Y) :- Y <= X.

?- min1(3, 4, X).
X = 3 ;
false.

看看Prolog是如何问我是否想要另一个解决方案，然后失败了？这就是堆栈上有一个额外的选择点的证据。我们可以剪掉它：

min2(X, Y, X) :- X < Y, !.
min2(X, Y, Y) :- Y =< X.

现在，当我们询问Prolog关于min2/3的问题时，我们只会得到一个答案：

?- min2(3, 4, X).
X = 3.

看，没有提示，只有一个解决方案。

现在，这是一个绿色的削减，而不是一个红色的削减，是没有真正的改变行为或推理。只是Prolog无法知道X < Y和Y =< X是相互排斥的--绿色切割是我们告诉Prolog的方法，一旦确定X小于Y，就没有必要检查Y是否小于X。这就从堆栈中删除了选择点，以获得技术上的好处。这有时是一个重要的优化，因为Prolog花费了大量的时间回溯，而花费在处理不可能的案例上的时间是浪费的。

红色的伤口是一种有点不同的动物。红色剪裁是指以一种额外的方式改变行为的任何剪裁。为了给您展示一个红色剪切的示例，您可以尝试完全消除min/3中的第二个测试：

min3(X, Y, X) :- X < Y, !.
min3(_, Y, Y).

你可能会这样想，“当我们到达第二个子句时，我们知道X不小于Y，所以没有必要检查Y是否小于或等于X。”乍一看，这似乎是合理的，而且您可以看到，它似乎具有与min2/3相同的行为，因为您知道有一个解决方案和以前一样：

?- min3(3, 4, X).
X = 3.

?- min3(4, 3, X).
X = 3.

然而，因为我们已经消除了一些逻辑，所以我们对涉及回溯的微妙错误敞开了大门。将min/3看作三个实体之间的关系，我们可以使用min3/3来产生min1/3和min2/3没有的错误：

?- min1(3, 100, 100).
false.

?- min2(3, 100, 100).
false.

?- min3(3, 100, 100).
true.

100不是3和100的最小值，但如果第三个值不是变量，min3/3将确认具有相同的第二个值的任何值。换句话说，我们在使用min3/3中的红色裁剪时假设，我们永远不会在第三个位置显示值。我们假设我们将使用第三个参数作为"out“参数。

让我们利用这些知识，看看你的作业。第一件事是，在前两条规则中有同样的重叠条件逻辑：

calculateCarInsurance(PS,Insurance) :-
   PS < 60, ...
calculateCarInsurance(PS,Insurance) :-
   PS >= 60, ...

至少，我们可以在PS < 60之后添加一个绿色削减来提交给我们:如果PS小于60，那么它也不能超过60，所以在那里的绿色切割是绝对无害的。

我要提醒的是，一个人从来不想增加红色削减。当你需要用Prolog的推理来使它像你想的那样工作时，它们有时是必要的。在这种情况下，您可以注意到calculateCarInsurance可能返回多个解决方案。你可能不想要这种行为，你可能想要承诺你得到的第一个行为。在这种情况下，您可以在calculateCarInsurance规则的所有主体的末尾添加一个切分。那么，无论Prolog能找到多少个解决方案，您都会得到一个解决方案。这会改变程序的逻辑行为，但根据您的需求可能是可取的。这也可能有同样的负面副作用的min3/3，尽管，如果我们想验证一个保险结果，calculateCarInsurance可能会肯定的计算，它永远不会产生。

我希望这足以让你走上正轨。