一个prolog程序优化绿色削减和红色切割

Question

我有一个prolog程序.但现在我对prolog不是很熟悉.所以从这里寻求帮助.

以下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)用Green Cuts优化程序.b)通过删除不需要的谓词,将绿色更改为红色削减.程序的行为应该是相同的.

我已经理解了prolog程序,但可以通过优化绿色削减来解决.谢谢,任何人都可以用细节解释a,b.谢谢

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可能会肯定它永远不会产生的计算.

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