3

我有一个有趣的小问题，我遇到了这样的逻辑子句：

Rule 1. A, B and C are unique, and are numbers from 1 to 3 (so every number is used).
Rule 2. B < 2
Rule 3. C > 2

现在（假设我刚刚提出的这个快速示例实际上验证了：P），很容易看到

A = 2
B = 1
C = 3

但这是一个非常人为的例子。

如果你有 20 条（或 1 万条）规则，并且它们重叠了怎么办。假设有一个有效的单一答案，并且您可以以某种方式访问​​规则（例如谓词列表）。

有没有一个很好的、通用的、直观的解决方案？我知道 Prolog 可以使用某些库来解决它，但我的尝试证明是徒劳的。我知道我可以蛮力排列范围内的所有数字，然后手动检查它们是否符合规则。但这似乎很蹩脚。

4

3 回答 3

4

蛮力解决方案

首先，我根据规则 1 创建所有可能的输入，这恰好是所有排列：

val all = (1 to 3).permutations

然后我定义剩余的规则：

val rule2 = (a: Int, b: Int, c: Int) => b < 2
val rule3 = (a: Int, b: Int, c: Int) => c > 2

我只是过滤掉不符合所有规则的解决方案：

val solutions = all.
  filter(i => rule2(i(0), i(1), i(2))).
  filter(i => rule3(i(0), i(1), i(2))).
  toList

solutions.toList打印一个也是唯一有效的解决方案：

List(Vector(2, 1, 3))

请注意，因为排列是延迟生成的，所以这个实现并不是真的那么无效（例如rule3，仅应用于通过的解决方案rule2）。

您可以使用foldLeft()任意数量的谓词：

val rules = List(rule2, rule3)

rules.
  foldLeft(all)((solutionsSoFar, rule) => 
    solutionsSoFar.filter(s => 
      rule(s(0), s(1), s(2))
    )
  )

流口水

看看Drools业务规则引擎。只需将所有可能的解决方案作为知识库并使用漂亮的 DSL 定义规则。

于 2012-05-14T06:56:43.333 回答
3

这是一项有约束力的工作。java有几个约束求解器。我最喜欢的是JaCoP。它有一个很好的 scala DSL，所以它几乎看起来像 Prolog 约束。这是典型的 SENDMOREMONEY 示例：http ://www.hakank.org/jacop/SendMoreMoney.scala

于 2012-05-14T07:14:27.483 回答
2

您可能会对这个博客感兴趣，作者在一篇由三部分组成的文章中展示了如何在 Scala 中进行逻辑编程：

http://ambassadortothecomputers.blogspot.com/feeds/posts/default?alt=rss

于 2012-05-14T19:26:34.910 回答