问题标签 [constraint-satisfaction]

我知道上述两种算法都属于迭代解决方案以找到 MAXSAT 问题的最佳解决方案，但我想知道为什么从可满足方面开始同时为 MAXSAT 找到解决方案比从不可满足方面搜索更好？

同样在这里，可满足方面意味着放宽所有可能的软条款，直到我们达到 UNSAT 和不可满足方面意味着从不放宽条款开始增加数量，直到我们达到 SAT

我有一个任务，我应该解决一个摩天大楼难题，这个特定的问题。这是一个在 4x4 网格中制作的谜题，其中网格的每个字段在行和列中都有不同的值（类似于数独）。字段内的值向我们显示了在该字段上建造的 skyskcaper 的高度（1-4，4 是最高的建筑物）。网格外的数字是从该方向可见的摩天大楼数量。（例如，从这个方向您只能看到一栋摩天大楼，因为最高的（4 栋建筑）覆盖了其他建筑物的视野 -> 4312 <- 从这个方向您可以看到三栋建筑物（仅覆盖高度为 1 的建筑物））。只给出外面的数字，你必须填写网格。有关游戏规则的更多详细信息：这里

这是开始状态，也是可能的输出之一。

我正在尝试，但我想不出对建筑物秩序的良好约束。我刚刚为行和列中的不同值输入了约束。

我正在尝试运行这个约束问题，但内存用完了，S_{i}是 1975 名学生，需要分配到 188 个助教班级之一，每个助教必须TA_{j}为其班级选择一个时间段。每个教师助理和学生都有他们在 8 英寸dfTA和dfS数据帧中表达的时间段。

这个想法是为每个学生分配一个助教，并为每个助教分配一个时间段。当然，一个班级的所有学生都必须能够参加该课程以及助教。

如果有人知道如何解决或优化它，那将非常有用。

如果对于任何k - 1 个变量的集合以及对这些变量的任何一致分配，始终可以将一致的值分配给任何第 _k_th 个变量，则CSP 是k一致的。一个 CSP 是强 k 一致的，如果它是k一致的并且也是 ( k - 1)-一致的，( k - 2)-一致的，...一直到 1-一致。

从上面的定义中，我不明白 CSP 怎么可能只是k一致但不是强 k一致。

如果 CSP 是k一致的，它是否也必须是k -1 一致的？如果没有，你能举个例子吗？

这是AC-3算法的（伪）代码：

我正在研究《人工智能 - 现代方法》（第 4 版）一书，这就是它关于该算法的时间复杂度的说法：

假设一个具有n 个变量的 CSP ，每个变量的域大小最多为d，并且具有二进制约束（弧）。每个弧 (Xi, Xj) 只能在队列中插入d次，因为 X_i 最多有d个值要删除。检查弧的一致性可以在 O(d^2) 时间内完成，因此我们得到 O(cd^3) 总最坏情况时间。

• 我知道每条弧(Xi, Xj)只能在队列中插入d次（因为Xi最多有d个值要删除，在最坏的情况下可以一个一个删除）。
• 我不明白如何在O(d^2). 相反，我认为它可能是O(cd)，因为在最坏的情况下，它可以从所有变量的域中一一删除所有值。
• 我不明白它给出的最坏情况总时间，即O(cd^3). 在这种情况下，在我看来，它本来可以是O(cd^2).

您将如何计算该算法的时间复杂度？我哪里错了？

谢谢你。

运行代码时出现以下错误。该错误通常不会发生，因为代码在一个“相邻状态”txt 文件中运行良好。但是对于另一个“相邻状态”的 txt 文件，它会给出这个 IndexError。我被卡住了，因为我没有看到任何错误。

“相邻状态”txt文件如下：

代码如下：

我有一个问题要使用 Wolfram Mathematica 解决。有两个表“sigmas”和“deltas”，每个单元格都包含一个实数值，对应于输入对“r”和“t”。例如，它们可能看起来像这样

我希望找到两个近似公式 σ _aprx (r, t) 和 δ _aprx (r, t)但对它们的系数有一些一般限制。说，我正在寻找如下公式：

σ _aprx (r, t) = (s ₀ + s ₁ ∗r + s ₂ ∗t + s ₃ ∗r∗t) / (s ₄ + s ₅ ∗r + s ₆ ∗t + s ₇ ∗r∗t )

δ _aprx (r, t) = (d ₀ + d ₁ ∗r + d ₂ ∗t + d ₃ ∗r∗t) / (d ₄ + d ₅ ∗r + d ₆ ∗t + d ₇ ∗r∗t )

其中 s ₀ .. s ₇是 σ _aprx的未知系数，d ₀ .. d ₇是 δ _aprx的未知数。

我可以完美地运行 FindFit两次，一个接一个地首先计算未知数 s _i为 σ _aprx，然后 d _i为 δ _aprx。但我的目标是得到这样的系数 s _i和 d _j一起满足一些额外的条件，比如，

d ₀ *s ₆ + d ₂ *s ₄ - d ₄ *s ₂ - d ₆ *s ₀ > d ₁ *s ₁ - d ₃ *s ₃ + d ₅ *s ₅ - d ₇ *s ₇。

（保证这样的系数存在）。

有没有办法让 FindFit 结合这两个（三个？）问题？我正在考虑将“sigmas”和“deltas”表编写为复数（σ + δi）的新“融合”表，以使 FindFit 在我的额外条件下同时优化它们，但仍然没有运气。

我怎样才能实现这样的技巧？谢谢你。

这是一个简单的图形着色问题，我使用了预定义的图形。输出为节点“a”和“f”提供了相同的颜色。我如何让它们与众不同？

存储最终输出的字典

检查相邻顶点是否具有相同颜色的函数

将颜色分配给顶点的函数

驱动程序

我将首先通过一个示例来解释什么是密码算术问题：

我们必须为每个字母分配一个数字 [0-9]，这样没有两个字母共享相同的数字，并且满足上述等式。

解决上述问题的一种方法是：

有两种方法可以解决这个问题，一种是蛮力，这会起作用，但这不是最佳方法。另一种方法是使用约束满足。

使用约束满足的解决方案
我们知道 R 将永远是偶数，因为它的 2 * O
这将 O 的域缩小到 {0, 2, 4, 6, 8}
我们也知道 F 只能是 1，因为 F 是'不是两个字母的加法，它必须从T + T = O
生成的进位中获取它的值 这也意味着T + T > 9，只有这样它才能为 F 生成一个进位；
这告诉我们T > 4 {5, 6, 7, 8, 9}
当我们继续这样做时，我们会不断缩小域的范围，这有助于我们将时间复杂度大大降低。

这个概念似乎很简单，但我在用 C++ 实现它时遇到了麻烦。尤其是我们为每个变量生成约束/域的部分。请记住，也有进位。

编辑：我正在寻找一种使用我所说的概念为每个变量生成域的方法。

我正在研究以下 CSP，但在将其转换为 python 代码时遇到了困难：

问题：一个相邻有 4 个办公室的消防站需要容纳 7 名消防员，他们是：Phylis、Ann、Henry、Eva、Bill、Mark、Bob

限制条件：Mark 和 Bob 必须在同一个办公室 Henry 和 Eva 必须在同一个办公室 Ann 和 Bill 必须在同一个办公室 Ann 必须在 Phylis 或 Eva 附近的办公室

到目前为止我的代码：

我的问题是：我需要为每个办公室制定一份清单吗？如果是这样，我将在哪里将官员添加到列表中？在满意的方法上还是在添加约束时？

非常感谢任何愿意帮助的人