问题标签 [constraint-satisfaction]

我在编程方面相当新，所以我希望有人能够在这方面为我指出正确的方向。

我有一个约 2400 人的列表，每个人至少有 23 个条件中的一个（如果他们有条件，每个人的条件是 1，如果没有，则为 0）。

EG 如果 Jon 有条件 1、5 和 6，Jon 的输出将是 {1,0,0,0,1,1,0,0...}。

然后，我将获得一份列表，列出每种条件需要多少人。因此，如果条件 1 的期望人数是 10 人，而条件 2 的期望人数是 5 人，我想要 10 人有条件 1 和 5 人有条件 2（如果两个人都有，一个人可以计入条件 1 和条件 2） .

此外，我必须准确选择 30 人，并尽量接近所需的条件数量，严格限制单个条件必须至少有 3 人且不超过 10 人。

有没有办法可以做到这一点，如果可以，我将如何去做？我尝试过暴力破解，但是大量的组合使我无法获得解决方案。

编辑：这是一个包含 5 个人和 4 个条件的小示例：

Person 1: {1,0,0,1} Person 2: {0,1,1,1} Person 3: {0,0,0,1} Person 4: {1,0,0,0} Person 5: {1,0,0,1}

所需的条件数 {2,1,1,2}。这个想法是我需要选择 3 个人并尽可能接近所需的条件数量。在此示例中，将选择人员 1、2 和 4。我必须将这个想法扩展到具有 23 个条件并选择 30 人的 2400 人列表（尽管它应该能够扩展到任何列表大小和任意数量的条件）并且不知道是否有 30 个成员的组合这将导致完全匹配。

这有助于澄清事情吗？

在 Choco Solver 中，在找到解决方案可能需要很长时间的情况下，如何获得最接近的解决方案（迄今为止满足最多约束但可能不满足所有约束的解决方案）？

例如，如果我正在运行 Model.getSolver().solve() 以获得解决方案，并且我已经决定尽管没有找到解决方案但它需要足够长的时间，那么我如何输出迄今为止最接近的解决方案？

如果在将值分配给变量 X 后，递归返回 X 处没有解决方案，则必须回溯。具体来说，这意味着对于剩余 d 个值的单个变量，最多可以回溯 d 次。对于以下每个约束图，如果每个变量都有一个大小为 d 的域，那么在最坏的情况下，对于每个指定的排序，您必须回溯多少次？

这是 CS188 Spring 人工智能的一个问题

这是图表

问题：C-B-D-E-A 回溯数：0

为什么这仍然被认为是线性排序？我不明白为什么 EA 仍然不被认为是从 E 到 A 的回溯，你将被迫返回并将通过 3 个变量。请帮忙。谢谢....

我正在使用 Gecode 来解决一个问题，即您标记多向图的弧，以便从单个源到单个接收器的每条路径中的弧标签的总和来自一个多重集。例如，我们可能有一个包含 8 条路径的图，并且希望路径弧和来自集合 {5,5,5,4,3,2,1,0}。所以我们必须恰好有 3 条路径之和为 5 和 5 条路径之和为 0..4。

您可以将此问题重新表述为询问 {5,5,5,4,3,2,1,0} 的某些排列是否在图的路径弧关联矩阵的列空间中。我用“计数”约束对这个多集匹配进行建模。弧和是线性方程。

我的图表有许多成对出现的平行边。使用对称性，我使用它对路径总和施加偏序。这也意味着存在具有相同差异的多对路径和。所以从我的例子中，如果路径是 b0...b7 我有以下对集：

b0 - b1 = b3 - b4 = b5 - b6，b0 - b2 = b5 - b7，b0 - b3 = b1 - b4，b0 - b5 = b1 - b6 = b2 - b7

b1 - b2 = b6 - b7，b3 - b5 = b4 - b6

将这些差异包含在模型中似乎将 Gecode 中的搜索空间减少了两个数量级。我对此感到满意，因为我认为它告诉我一些关于我正在研究的图表的重要信息，并且它符合我工作领域的一些猜想。

偏序现在告诉我们只有 b0,b2,b3,b5 和 b7 可以取值 5。现在可以证明这个系统不能满足。我对约束满足等技术感兴趣，这些技术可用于分析不等式系统（！=）以及“计数”。显然，Gecode 可以通过赋值和失败来证明这一点。我对一般技术感兴趣，既可以了解约束满足，也可以帮助改进模型，并可能对我正在调查的事情有所了解。

要看到这个问题是不可解的，我们可以证明 6 组对差系统中的每一个都不能有零差。如果他们这样做了，他们会生成错误值的重复项或太多的 5。

例如 b0 - b1 = b3 - b4 = b5 - b6 将有 b0 = b1 这是不可能的，因为 b1 不能是 5，这是唯一可以有重复的值。或者 b0 - b2 = b5 - b7 意味着 b0 = b2 和 b5 = b7 需要 4 个 5。

所以我们最终得到了一组路径上的不等式，其总和可能为 5：

b0 != b2, b0 != b3, b0 != b5, b2 != b7, b5 != b7

我们可以看到 b0 != 5 因为如果是，我们只能得到 2 个五。从剩下的 4 个值中，我们被迫最多可以设置 2 到 5，因此整个系统是不可解决的。

我对必须用 Numberjack 解决的这个问题感到抓狂，这是一个用于 CSP 的 python 库。我们有 nxm 个带有彩色边的正方形。这些方格必须以anxm 网格排列，使方格的相邻边具有相同的颜色。正方形可以旋转和移动。一个例子：

我考虑过使用 4 个矩阵（一个用于 nord，一个用于 sud，一个用于西，一个用于东侧）和一个颜色的数字。Nord(i,j)、West(i,j)、East(i,j)、Sud(i,j) 描述网格上的正方形 i,j。我必须考虑哪些限制？

我正在开发一个 python 程序来解决约束满足问题（CSP）。

这里我有变量列表['MI428', 'UL867', 'QR664', 'TK730', 'UL303']及其可能的分配['A1', 'A2', 'B1', 'B2', 'C1' ] .

我对此的限制是，第二个列表中的每个元素都有兼容性列表（可能的分配）。它的工作原理如下；

从第一个列表（变量列表）的元素中，有另一个索引来获取另一个键。通过该键，我可以访问列表中的一组兼容值（可能的分配）。为了更好地理解考虑这个例子：

对于变量'MI428'我有键'B320' ('MI428->'B320') ，然后我有B320的兼容值列表为['A1', 'A2']

在这里，我的任务是将['A1', 'A2', 'B1', 'B2', 'C1']中的兼容值分配给每个变量，例如'MI428'，以满足上述约束。

注意：为此，我使用的是python-constraint库。我需要使用它来实现。到目前为止，我立即创建了一个问题，如下所示，所以我真正想要的是为该问题添加约束。

我需要一个适当的 addConstraint 线约束..

我正在使用python-constraint库来解决 CSP 问题，以便为机场的每个航班预留舱位。我需要将Bays:('A1', 'A2', 'B1', 'B2', 'C1')分配给Flight :('MI428', 'UL867', 'QR664', 'TK730', 'UL303')变量集的地方。

将值分配给第二组时几乎没有约束。这是我的代码

上面的代码工作正常。我想要添加另一个约束，其中每个航班都与特定时间段相关联，称为到达和离开时间之间的时间段。

为此，我创建了另一个列表，如下所示：

注意：例如，这里的 (1,3) 表示 1.00 am 到 3.00 am

我需要分配舱位，以便同时没有两个航班获得相同的舱位。所以我问如何使用python-constraintaddConstraint()中的方法添加该约束？

以课程安排为例，假设一名教师只能教授 n 门课程。为了强制执行这一点，我的想法是找到给定讲师正在教授的所有课程，并通过负差异增加不良，如果低于则增加一半。我将如何去做（获得由给定教授教授的所有课程）？

给定产品的各种功能、功能选项以及功能之间的兼容性规则，我想生成所有可行产品配置的列表。

例如，我当前的用例类似于配置笔记本电脑。许多变量，如屏幕尺寸、内存、cpu、主板，每个变量都有多个有效值。我们也可以有限制，比如这个主板与这个 cpu 兼容等。我需要的输出是笔记本电脑所有有效配置的列表。

该场景看起来像一个典型的约束满足问题 (CSP)。我尝试了 Minion、Choco 等 CSP 库。不幸的是，它们只使用数字变量，并且兼容性规则也是一个数学函数。

我还尝试了http://labix.org/python-constraint，我在其中使用了功能约束，并将我的兼容性规则作为 If 语句提供。这适用于小场景。但根据我的要求，我将拥有 10 个功能，每个功能都有 4 到 5 个选项，从而产生数百万个配置。

有人可以建议我的要求的最佳方法吗？

我有以下问题：我必须将 K 个实验分配给 N 个实验室，同时尊重一些一般约束和一些特定约束。

一般的有：

1. 每个实验都必须准确分配给 R 实验室
2. 每个实验室的最大实验次数，M
3. 理想情况下，每个实验室的实验分布接近均匀（但可以稍微放松）
4. 没有实验室被遗漏

然后是具体的限制。由于并非所有实验室都拥有相同的设备和试剂，因此每个实验室都会有自己的一组可以/无法执行的实验。

在我看来，这似乎是一个满足约束的问题。我知道它们存在，但我没有与它们合作的经验。

我想知道是否有一种方法可以通过将其映射到已知图问题或存在足够好的算法的其他东西来解决这个问题，或者，如果失败了，是否有优化搜索的方法，是否需要蛮力-强迫。

谢谢！