约束满足问题公式
Constraint Satisfaction Problem formulation
我得到了以下要求，这些要求需要通过定义一组变量和一组对这些变量的约束来表述为 CSP 问题。但是，我在为我的问题制定约束和变量时遇到了麻烦。
一些信息：
问题的解决方案是分配列表：[Var, A1, A2, A3]
其中 Var 是变量，A1、A2、A3 是有效赋值的有序序列。
要求：
- 每个变量在
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() 的变量
- 每个
Var 的 NValues 约束，其范围是 [Var]，需要值 problem.valid_assignments(Var)，下限 0，上限 len(domain).
附加信息：
解决方案是 "list of assignments"，因为对于每个 Var 我们 return [Var, A1, A2, A3] 其中 Var 是分配的变量并且A1 到 A3 是满足给定约束的有效分配。确切的格式并不重要，因为我只是在寻找一个概念性的解决方案。此外 A1, A2, A3（又名 Var 的所有赋值）显然必须在该变量的域中。 （变量之间的域可以重叠）。
valid_pairs() return 是一个元组列表 [(A1, A2), (A2,A3)]。约束是这样的 returned 解决方案列表（如上所述）必须具有形成此函数给出的有效对的连续分配。例如，如果解决方案是 [Var, A1, A2, A4, A3] 并且有效对是 [(A1, A2), (A2,A3)] 那么解决方案是不正确的，因为 (A2, A4) (A4, A3) 不在列表中（但是 (A1, A2) 是一个有效对）。
本质上我们正在寻找弧一致性。
我们可以使用一个NValues约束，其范围是所有变量，域是每个可能的赋值（为每个赋值创建一个约束）。这确保在设置为具有上限和下限 1 时分配所有值。
我们可以使用 Neq 约束并稍作修改，通过向其提供有效赋值的元组来确保正确排序。
我们可以再次使用 NValues 约束通过传递下限 1 和 K 的上限来确保 k_assignment 要求与域 K_assignments.
以相同的方式，我们可以使用域 problem.first_assignments() 的 NValues 约束进行第一次分配。另一个域 problem.valid_assignments() 用于填充空白。
我得到了以下要求，这些要求需要通过定义一组变量和一组对这些变量的约束来表述为 CSP 问题。但是，我在为我的问题制定约束和变量时遇到了麻烦。
一些信息：
问题的解决方案是分配列表：[Var, A1, A2, A3]
其中 Var 是变量，A1、A2、A3 是有效赋值的有序序列。
要求：
- 每个变量在
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() 的变量
- 每个
Var的NValues约束，其范围是[Var]，需要值problem.valid_assignments(Var)，下限0，上限len(domain).
附加信息：
解决方案是 "list of assignments"，因为对于每个
Var我们 return[Var, A1, A2, A3]其中Var是分配的变量并且A1到A3是满足给定约束的有效分配。确切的格式并不重要，因为我只是在寻找一个概念性的解决方案。此外A1, A2, A3（又名Var的所有赋值）显然必须在该变量的域中。 （变量之间的域可以重叠）。valid_pairs()return 是一个元组列表[(A1, A2), (A2,A3)]。约束是这样的 returned 解决方案列表（如上所述）必须具有形成此函数给出的有效对的连续分配。例如，如果解决方案是[Var, A1, A2, A4, A3]并且有效对是[(A1, A2), (A2,A3)]那么解决方案是不正确的，因为(A2, A4) (A4, A3)不在列表中（但是(A1, A2)是一个有效对）。本质上我们正在寻找弧一致性。
我们可以使用一个
NValues约束，其范围是所有变量，域是每个可能的赋值（为每个赋值创建一个约束）。这确保在设置为具有上限和下限 1 时分配所有值。我们可以使用
Neq约束并稍作修改，通过向其提供有效赋值的元组来确保正确排序。我们可以再次使用
NValues约束通过传递下限 1 和K的上限来确保k_assignment要求与域K_assignments.以相同的方式，我们可以使用域
problem.first_assignments()的NValues约束进行第一次分配。另一个域problem.valid_assignments()用于填充空白。