Prolog 回溯 VS Rete 回溯
Prolog backtracking VS Rete backtracking
在我的 class 中,我学习了 Prolog 回溯算法和 Rete forprop 算法,但也有人告诉我 Rete 可以用来做反向传播。
这是如何运作的?它在哪些方面与 Prolog 回溯相似/不同?
例如,这是我得到的练习之一:
(R1) 24fingers and antennas => origin(mars)
(R2) shy and 5feet => origin(mars)
(R3) shy and 4arms => origin(venus)
(R4) looksDownWhenTalking => shy
(R5) fleesWhenSeen => shy
目标是根据以下事实找到外星人的起源:
(F1) fleesWhenSeen
(F2) 4arms
在 Prolog 中,我们将通过将目标 origin(X)
与规则的 RHS 进行模式匹配来解决它。该规则与 R1、R2 和 R3 相匹配,因此首先会触发 R1,然后我们将尝试解决会失败的子目标 24fingers and antennas
。
然后我们会回溯到开始并触发 R2,最终会失败,最后回溯并触发 R3,它会成功。
因此 X
在成功查询中最终绑定到 venus
,算法结束。
现在,我们如何使用 rete backprop 算法解决相同的问题?
我天真地假设我们将使用子目标列表,从 origin(X)
开始触发其 RHS 匹配子目标的规则。
但我不清楚 Rete 算法如何在某些子目标失败时处理回溯,或者它如何知道一旦解决了某个目标子集就成功了。
此处提供 Rete 算法 的说明:http://www.drdobbs.com/architecture-and-design/the-rete-matching-algorithm/184405218 .
在 Prolog 中,使用 统一算法,与模式匹配不同的是,模式匹配的两边都有模式(目标/规则头)。
编辑
这里有很多关于 Rete 和 Prolog 的信息。
在 Prolog 中构建专家系统
http://www.amzi.com/distribution/files/xsip_book.pdf
http://www.oopweb.com/Prolog/Documents/XSIP/Volume/08performance.htm
理论框架
和
序言解释器的实现
在正向链接系统中支持反向链接没有标准实现。混合工具使用不同的技术实现了这个功能。此处描述了一种技术,即数据驱动的反向链接:http://haleyai.com/wordpress/2008/03/11/goals-and-backward-chaining-using-the-rete-algorithm/. Some additional information: JESS vs DROOLS : Backward chaining 和
http://herzberg.ca.sandia.gov/docs/70/rules.html.
在我的 class 中,我学习了 Prolog 回溯算法和 Rete forprop 算法,但也有人告诉我 Rete 可以用来做反向传播。
这是如何运作的?它在哪些方面与 Prolog 回溯相似/不同?
例如,这是我得到的练习之一:
(R1) 24fingers and antennas => origin(mars)
(R2) shy and 5feet => origin(mars)
(R3) shy and 4arms => origin(venus)
(R4) looksDownWhenTalking => shy
(R5) fleesWhenSeen => shy
目标是根据以下事实找到外星人的起源:
(F1) fleesWhenSeen
(F2) 4arms
在 Prolog 中,我们将通过将目标 origin(X)
与规则的 RHS 进行模式匹配来解决它。该规则与 R1、R2 和 R3 相匹配,因此首先会触发 R1,然后我们将尝试解决会失败的子目标 24fingers and antennas
。
然后我们会回溯到开始并触发 R2,最终会失败,最后回溯并触发 R3,它会成功。
因此 X
在成功查询中最终绑定到 venus
,算法结束。
现在,我们如何使用 rete backprop 算法解决相同的问题?
我天真地假设我们将使用子目标列表,从 origin(X)
开始触发其 RHS 匹配子目标的规则。
但我不清楚 Rete 算法如何在某些子目标失败时处理回溯,或者它如何知道一旦解决了某个目标子集就成功了。
此处提供 Rete 算法 的说明:http://www.drdobbs.com/architecture-and-design/the-rete-matching-algorithm/184405218 .
在 Prolog 中,使用 统一算法,与模式匹配不同的是,模式匹配的两边都有模式(目标/规则头)。
编辑
这里有很多关于 Rete 和 Prolog 的信息。
在 Prolog 中构建专家系统
http://www.amzi.com/distribution/files/xsip_book.pdf
http://www.oopweb.com/Prolog/Documents/XSIP/Volume/08performance.htm
理论框架 和 序言解释器的实现
在正向链接系统中支持反向链接没有标准实现。混合工具使用不同的技术实现了这个功能。此处描述了一种技术,即数据驱动的反向链接:http://haleyai.com/wordpress/2008/03/11/goals-and-backward-chaining-using-the-rete-algorithm/. Some additional information: JESS vs DROOLS : Backward chaining 和 http://herzberg.ca.sandia.gov/docs/70/rules.html.