Prolog回溯与Rete回溯

Question

在我的课堂上，我被教过Prolog回溯算法和Rete算法，但我也被告知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反向支持算法来解决相同的问题呢？

我天真地假设我们将使用一个子目标列表，从origin(X)开始，开始触发规则，其RHS与子目标匹配。

但我不清楚Rete算法在某些子目标失败时将如何处理回溯，或者它如何知道一旦解决了某个目标子集，它就成功了。

Answer 1

在前向链接系统中没有支持反向链接的标准实现。混合工具使用不同的技术实现了这一功能。这里描述了一种技术，数据驱动的后向链接：http://haleyai.com/wordpress/2008/03/11/goals-and-backward-chaining-using-the-rete-algorithm/。一些附加信息：JESS vs DROOLS : Backward chaining和http://herzberg.ca.sandia.gov/docs/70/rules.html。

Answer 2

对Rete算法的解释如下：http://www.drdobbs.com/architecture-and-design/the-rete-matching-algorithm/184405218。

在Prolog中，使用了统一算法，与模式匹配算法不同的是，该算法两边都有模式(目标/规则头)。

编辑

这里有很多关于Rete和Prolog的信息。

在Prolog中构建专家系统

book.pdf

http://www.oopweb.com/Prolog/Documents/XSIP/Volume/08performance.htm

-- PROLOG解释器的理论框架与实现

http://staff.um.edu.mt/mcam1/Files/Dissertation.pdf