我得到了以下要求,需要通过定义一组变量以及对这些变量的一组约束来将其表述为 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() - A
NValues每个Var的约束其范围是[Var], 必填值problem.valid_assignments(Var), 下界0, 上限len(domain).
附加信息:
解决方案是每个
Var中的“分配列表”我们返回[Var, A1, A2, A3]其中Var是分配的变量和A1通过A3是满足给定约束的有效分配。确切的格式并不重要,因为我只是在寻找一个概念性的解决方案。另外A1, A2, A3(又名Var的所有分配)显然必须在该变量的域中。 (变量之间的域可以重叠)。valid_pairs()返回元组列表[(A1, A2), (A2,A3)].约束是这样的,即返回的解决方案列表(如上所述)必须具有形成此函数给出的有效对的连续分配。例如,如果解决方案是[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。以同样的方式,我们可以使用
NValues约束和域problem.first_assignments()进行第一次赋值。另一个用域problem.valid_assignments()来填充空白。
