约束满足问题公式化

Question

我得到了以下要求，这些要求需要通过定义一组变量和一组对这些变量的约束来表述为 CSP 问题。但是，我无法为我的问题制定约束和变量。

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

要求：

• 每个变量都被赋予一个值 problem.valid_assignments()

• 每个变量的第一个赋值在 problem.first_assignments()

• 每个变量的赋值顺序都在problem.valid_pairs()（有些赋值不能跟在其他的后面）

• 给定一个整数K，最多只能有K连续的赋值，其中至少有一个不存在问题。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]哪里Var是可变分配，并且A1通过A3是满足给定约束的有效分配。确切的格式并不重要，因为我只是在寻找一个概念性的解决方案。此外A1, A2, A3（又名 a 的所有赋值Var）显然必须在该变量的域中。（域可以在变量之间重叠）。

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

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

Answer 1

我们可以使用一个NValues约束，其范围是所有变量，域是每个可能的赋值（为每个赋值创建一个约束）。这确保在设置为具有 1 的上限和下限时分配所有值。我们可以使用Neq带有一些修改的use约束，通过提供有效分配的元组来确保正确的排序。我们可以再次使用NValues约束k_assignment通过传递下限 1 和K域上限来确保需求K_assignments。以同样的方式，我们可以将NValues约束与域problem.first_assignments()用于第一次分配。另一个用域problem.valid_assignments()来填空。