Prolog 回溯 VS Rete 回溯

Question

在我的 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 算法如何在某些子目标失败时处理回溯，或者它如何知道一旦解决了某个目标子集就成功了。

Answer 1

此处提供 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://staff.um.edu.mt/mcam1/Files/Dissertation.pdf

Answer 2

在正向链接系统中支持反向链接没有标准实现。混合工具使用不同的技术实现了这个功能。此处描述了一种技术，即数据驱动的反向链接：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.

Prolog 回溯 VS Rete 回溯

Prolog backtracking VS Rete backtracking

prolog

backtracking

rule-engine

rete