logo标签列表

Prolog回溯与Rete回溯

prologbacktrackingrule-enginerete
11

在我的课堂上，我学习了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)与规则的右侧进行模式匹配来解决它。该规则与R1、R2和R3匹配，因此首先会触发R1，并尝试解析子目标24fingers和antennas，但这将失败。
然后我们会回溯到开始并触发R2，最终会失败，最后回溯并触发R3，这将成功。
因此，在成功查询中，X绑定到venus，算法结束。
现在，我们如何使用rete backprop算法解决相同的练习？
我天真地认为，我们会使用一个子目标列表，从origin(X)开始，以触发其RHS与子目标匹配的规则。
但是我不清楚当某些子目标失败时，Rete算法如何处理回溯，或者它如何知道一旦解决了某个子目标集合就已经成功。
rete算法严格遵循前向链接。也许有一些基于rete的引擎也支持后向链接，但使用的算法不能是rete算法。你能否添加一些声称使用rete和后向链接的资源链接？ - CoronA
Prolog在演绎推理方面非常专业。它有一个知识库，可以推断某些事情是否为真，或者可以进行深度优先搜索以查找带有变量的问题的所有可能解。我想其他语言更擅长归纳推理，这涉及计算某些事情发生的概率，而这不是Prolog的主要设计目的。它试图基于已知事实通过反向链接为您提供答案，而其他语言则更擅长正向链接以为您提供概率树。演绎推理与预测不同。 - G_V
2
@Jsevillamol：我认为大多数基于RETE的系统支持反向链接查询，但这些查询不是使用RETE算法处理的，而是使用其他算法（如Prolog中的SLD-Resolution、Deductive Databases中的Semi-Naive-Bottom-Up-Evaluation或Magic-Sets-Evaluation）。 - CoronA
2
@G_V：RETE算法和SLD解析都是演绎算法。前向推理和后向推理都是演绎的。归纳推理是超出Rete和Prolog范围的主题。所有通过归纳推理得出的事实可能是错误的（这在演绎推理中并非如此）。 - CoronA
2
@G_V：正向链接允许您从其他事实中推导出事实。归纳推理让您猜测事实。这完全不同。规则“青蛙=>绿色”意味着所有的青蛙都是绿色的。在这个世界上没有棕色的青蛙。对这条规则的归纳推理会提出一个绿色物体可能（！）是一只青蛙的假设。然而，在这个世界上可能还有其他绿色的物体，而一个不是青蛙的绿色物体完全符合这个规则所基于的世界。 - CoronA
显示剩余3条评论
2个回答
3
2
在这里提供了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 PROLOG解释器的理论框架和实现 http://staff.um.edu.mt/mcam1/Files/Dissertation.pdf
2
好的资源，但这并没有回答我的问题。 - Jsevillamol
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接