时间戳

首页 > 解决方案 > 求解器与系统搜索的约束满足问题

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

问题描述

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

我们最初开始使用约束满足问题算法（使用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)

标签： algorithmsearchcomplexity-theoryconstraint-programming

解决方案

CSP 允许您将值的确定性生成（通过规则）与启发式搜索相结合。当您针对您的问题定制这两者时，美丽就会发生。规则只是其中的一部分。同样重要的是搜索算法/生成器的选择。您可以剔除很多搜索空间。

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

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

完全免责声明：我与 CSP 的最后一次接触是几十年前在大学攻读硕士学位的时候（我实现了一个与 choco 不同的 CSP 搜索引擎，当然更初级，并对该主题进行了一些研究）。但从那时起，该领域肯定会发生变化。

推荐阅读