python - 约束满足问题公式

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()
• 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) 然而是一对有效的)。

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

Answer 1

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

• 我们可以使用 Neq 约束并进行一些修改，通过向其提供有效赋值的元组来确保正确排序。

• 我们可以再次使用 NValues 约束通过传递下限 1 和上限 K 来确保 k_assignment 要求> 使用域 K_assignments。

• 以同样的方式，我们可以使用 NValues 约束和域 problem.first_assignments() 进行第一次赋值。另一个用域 problem.valid_assignments() 来填充空白。