1

我正在开发一个推理引擎，这意味着基本上我有一定数量的“事实”，这些“事实”基本上代表了某个时刻的世界。连同事实（通常只有两个，起始状态和目标状态），我有许多规则（对于某些问题，实际上可能是数百个）。推理引擎的目标是，给定一个起始状态和一组规则，找到到达可接受目标状态的最短路径。这可以通过多种算法来完成，例如 DFS、BFS 或 A*。该程序的基本结构是：

事实事实名称
  属性1 =“价值”；
  属性 2 = [ 1, 2, 3];
  属性3 = 4；
  属性4 = 7；
  ...
最终事实

规则规则一
  等于（属性，“值”）或
  大于（属性，5）
  >
  删除（属性）；
结束规则

规则规则二
  isprimeinteger（属性）
  >
  添加（属性，1）
结束规则

在规则中，LHS（> 之前的部分）匹配事实中等于“值”的每个属性。factname在这种情况下，它只有一个，但可能有很多。这意味着我必须解析变量（通常为同一事实多次解析），并且规则的 LHS 可能有多个条件放入和/或具有适当的优先级解析。

问题是：有没有办法有效地解决这种变量？我现在正在做的是迭代事实中的每个属性，基本上我正在生成一个非常大的 n-ary 树，它甚至是不平衡的，这非常慢，特别是考虑到上述条件。

我喜欢这种模式匹配的论文指针

4

3 回答 3

2

我注意到您在帖子中的任何地方都没有使用统一一词。这就是你试图实现的算法通常被称为。查看维基百科的文章；底部有一些参考资料.. 包括 70 年代空间和周期很重要的参考资料。

于 2009-06-11T17:59:55.547 回答
0

这并不奇怪，您使用的是 O(N) 算法，其中简单的哈希表将是 O(1)。哈希表将为每个属性值存储相应的属性。

于 2009-06-11T08:48:50.700 回答
0

eduffy 有它：这叫做统一。Prolog 是一种编程语言，在一般情况下，它旨在完全按照您的要求做，它使用统一来完成其繁琐的工作。

然而，任何尝试在 Prolog 中使用 Peano 公理来实现算术的人都会告诉你，它并不总是以最快的方式到达那里。有一些“约束编程”语言可以做大致相同的事情，但强调提供启发式方法以帮助求解器尽快找到最佳解决方案。其中之一是彗星。

于 2009-06-12T15:45:19.590 回答