python - 约束满足问题公式化

Question

通过定义一组变量和一组对这些变量的约束，我得到了以下需要将其表述为 CSP 问题的要求。但是，我在为我的问题制定约束和变量时遇到了麻烦。

一些信息： 问题的解决方案是一个赋值列表：变量[Var, A1, A2, A3] 在哪里，,是有效赋值的有序序列。VarA1A2A3

要求：

• 每个变量都被赋予一个值problem.valid_assignments()
• 每个变量的第一个赋值在problem.first_assignments()
• 每个变量的赋值顺序都在problem.valid_pairs()（有些赋值不能跟随其他）
• 给定一个整数K，最多只能有K一个连续赋值，其中至少有一个不在problem.k_assignment()
• 给定分配列表中的每个值：problem.assignment必须使用。

可用约束：

• NValues约束：给定一个列表required_values，一个上限和下限，确保其值在其中的变量的数量required_values在边界之间。
• AllDifferent约束：给定一组变量，强制它们的不等式。也就是说，集合中没有两个变量是相等的。
• NotEqual约束：给定Var1, Var2, 强制执行：Var1!=Var2

至今：

• 每个Var域的变量problem.valid_assignments()
• 每个Var域的变量problem.first_assignments()
• NValues每个Var范围的约束[Var]，要求的值problem.valid_assignments(Var)，下限0，上限len(domain)。

附加信息：

• 解决方案是一个“分配列表”，因为对于每个Var我们返回的变量是在[Var, A1, A2, A3]哪里分配的，并且通过是满足给定约束的有效分配。确切的格式并不重要，因为我只是在寻找一个概念性的解决方案。此外（也就是 a 的所有赋值）显然必须在该变量的域中。（域可以在变量之间重叠）。VarA1A3A1, A2, A3Var

• valid_pairs()返回一个元组列表[(A1, A2), (A2,A3)]。约束是这样的，即返回的解决方案列表（如上所述）必须具有连续的分配，这些分配形成由该函数给出的有效对。例如，如果解决方案是[Var, A1, A2, A4, A3]并且有效对是，[(A1, A2), (A2,A3)]则解决方案不正确，因为(A2, A4) (A4, A3)不在列表中（(A1, A2)但是是有效对）。

• 本质上，我们正在寻找弧一致性。

标签： pythonsearchconstraintsbacktrackingconstraint-programming

Answer 1

• 我们可以使用一个NValues范围是所有变量的约束，域是每个可能的赋值（为每个赋值创建一个约束）。这可确保在设置为上限和下限为 1 时分配所有值。

• 我们可以使用 useNeq约束并稍作修改，通过为其提供有效分配的元组来确保正确的排序。

• 我们可以通过传递 1 的下限和domain的上限来再次使用NValues约束来确保需求。k_assignmentKK_assignments

• 以同样的方式，我们可以将NValues约束与域一起problem.first_assignments()用于第一次分配。另一个用域problem.valid_assignments()来填补空白。