algorithm - 求解器 VS 系统搜索的约束满足问题

Question

我们必须解决一个难题，即我们需要针对系统检查来自多个来源的大量复杂规则，以便确定系统是否满足这些规则或应该如何更改以满足这些规则。

我们最初开始使用 Constraint Satisfaction Problems 算法(使用 Choco )来尝试解决它，但由于规则和变量的数量会比预期的少，我们希望在数据库上构建所有可能配置的列表并根据规则使用多个请求来过滤此列表并以这种方式找到解决方案。

与针对合理数量的规则和变量使用 CSP 求解器算法相比，进行系统搜索是否存在限制或缺点？它会显着影响性能吗？它会减少我们可以实现的约束类型吗？

例如:

你必须用更多的变量、更大的定义域(但总是离散的)和更多的规则(还有一些更复杂)来想象它，而不是将问题描述为:

x in (1,6,9)
y in (2,7)
z in (1,6)
y = x + 1
z = x if x < 5 OR z = y if x > 5

然后将其提供给求解器，我们将构建一个表:

X | Y | Z
1   2   1
6   2   1
9   2   1
1   7   1
6   7   1
9   7   1
1   2   6
6   2   6
9   2   6
1   7   6
6   7   6
9   7   6

并使用类似的查询(这只是一个帮助理解的示例，实际上我们将针对语义数据库使用 SPARQL):

SELECT X, Y, Z WHERE Y = X + 1 
INTERSECT 
SELECT X, Y, Z WHERE (Z = X AND X < 5) OR (Z = Y AND X > 5)

Answer 1

CSP 允许您将确定性的值生成(通过规则)与启发式搜索相结合。当您为您的问题自定义这两个时，美丽就会发生。规则只是一方面。同样重要的是搜索算法/生成器的选择。您可以挑选很多 搜索空间。

虽然我无法预测您的 SQL 解决方案的性能，但我必须说它让我觉得有些迂回。如果您的规则发生变化，就会出现一个特定问题——您可能会发现您必须从头开始。此外，RDBMS 将完全生成所有子查询，这可能会爆炸。

我建议使用 CSP 和 SQL 实现一个工作原型(prototype)，以满足您需求的一个简单子(monad)集。然后你会很好地感觉到什么有效，什么无效。一定要考虑长期维护。

完全免责声明:我最后一次接触 CSP 是几十年前在大学攻读硕士学位时(我实现了一个 CSP 搜索引擎，与 choco 类似，当然更简单一些，并且对该主题进行了一些研究)。但从那时起，该领域肯定会有所发展。