求解器的约束满足问题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实现一个简单的需求子集.然后,您将会感觉到哪些有效,哪些无效.一定要考虑长期维护.

完全免责声明:我上次与CSP的联系是几十年前在大学里作为我的主人的一部分(我实现了一个与choco不同的CSP搜索引擎,当然有点基础,并对该主题进行了一些研究).但从那时起,这个领域肯定会有所发展.