问题标签 [constraint-programming]

我正在 Mac OS X 10.7 上编写一个 Objective C 应用程序，我需要解决一个算术约束问题。例如，我有两个矩形方程，a 和 b 是边长：

我将此问题确定为约束满足问题。用户应该能够指定 a 和 A，并让求解器计算 b 和 P。我在http://mitpress.mit.edu/sicp/full-text/book/book-ZH-中找到了一个实现22.html#%_idx_3516，但我不确定是否有一种干净的方法可以从Objective C调用LISP程序。我正在寻找可以为求解器提供Objective C接口的东西，或者编译LISP编程到Objective C库中。否则，一个极简的开源约束求解器将满足我的需求。

我无法理解eclipse 约束编程框架中的 search/6 函数的文档。

我知道选择参数基本上会影响值排序。

选择方法似乎也选择了变量排序，但我并不完全理解它的所有选项。

我不太了解其他参数，所以我想知道是否有人可以用语言解释它们。我对约束逻辑编程的理论有很好的理解，所以请随意参考这些概念。我只是不明白该文档中的很多 CS 术语（arity 等）

谢谢

SMT-Solver 可用于约束求解。众所周知，CSP 求解器多年来也用于约束求解。那么 SMT 求解器相对于 CSP 求解器的优势是什么？

在 Microsoft Solver Foundation 中，我想知道是否可以添加一个参数，其值取决于决策值。

即我想要 TSP 模型的一些东西，但它也应该考虑从一个点到另一个点的流量。请注意：交通取决于销售人员在该路线上行驶的时间。

这是模型：

我有一个城市之间所有可能组合的矩阵。

决策变量是Order销售人员的路线。0 是第一个，1 秒，...

我有一个属性timeToTravel，该属性绑定到一个属性，该属性从该值计算路线发生的时间，Order并返回行程时间，包括当天该时间的交通量。

在我看来，参数值在Solve调用函数时被读取一次并缓存，我正确吗？如果是，有没有人有任何建议来解决这个问题？

最初我在 MSF 论坛上问了这个问题，但我认为它会在 Stack Overflow 上得到更多关注。此外，我对 MSF 以外的其他求解器持开放态度，但我更愿意留在 .NET 环境中。

我得到了一个练习来使用我选择的约束求解器来解决斑马难题，我使用Prolog clpfd library进行了尝试。

我知道在 Prolog 中还有其他更惯用的方法来解决这个问题，但这个问题是专门关于clpfd包的！

因此，我试图解决的难题的具体变体（鉴于其中有很多）是这个：

有五间房子

1. 英国人住在红房子里
2. 瑞典人养狗
3. 丹麦人喜欢喝茶
4. 绿房子留给白房子
5. 温室的主人喝咖啡
6. 抽 Pall Mall 的人拥有一只鸟
7. 中间屋喝牛奶
8. 黄房子的主人抽登喜路
9. 挪威人住在第一所房子里
10. 万宝路吸烟者住在猫主人旁边
11. 马主住在抽登喜路的人旁边
12. 温菲尔德吸烟者喜欢喝啤酒
13. 挪威人住在蓝屋旁边
14. 德国人抽罗斯曼烟
15. 万宝路吸烟者有一个喝水的邻居

我试图用以下方法解决它：

房子可以拥有的每个属性都被建模为一个变量，例如“British”、“Dog”、“Green”等。属性可以取 1 到 5 的值，具体取决于它们所在的房子，例如，如果变量“狗”取值3，狗住在第三宫。

这种方法可以很容易地模拟这样的邻居约束：

但不知何故，clpfd即使（IMO）问题被正确建模（我使用与Choco 约束求解器完全相同的模型，结果是正确的），该包也没有产生解决方案。

这是完整的代码：

我是否误解了 中的概念clpfd，或者我只是在这里遗漏了一些明显的东西？如果有帮助，您可以在这里找到使用 Choco 和 Scala 实现的相同方法。

编辑：我认为求解器无法解决问题的原因在于它从来没有为变量提供明确的值，而只是提供范围，例如“Fish 1..3\/5”。

问题陈述

我们有一个雇主想要面试 N 个人，因此安排了 N 个面试名额。每个人都有这些时段的闲忙时间表。如果可能，请给出一个算法，将 N 人安排到 N 个插槽中，如果不可能，则返回标志 / 错误 / 等。最快的运行时复杂度是多少？

到目前为止我的方法

天真：有N个！安排N个人的方法。遍历所有这些，对于每个排列，检查它是否可行。在！ ）

回溯：

1. 寻找任何只能有 1 人的面试时间段。安排此人，将其从候选人列表中删除并删除空档。
2. 寻找任何只能进入 1 个位置的候选人。安排此人，将其从候选人列表中删除并删除空档。
3. 重复 1 和 2，直到不再有类似的组合。
4. 选择一个人，将他们随机安排到他们可用的位置之一。记住这个操作。
5. 重复 1、2、3，直到我们有时间表或出现无法解决的冲突。如果我们有时间表，请将其退回。如果存在无法解决的冲突，请回溯。

这是 O(n!) 最坏的情况，我认为 - 这也好不到哪里去。

也可能有一个 DP 解决方案 - 但我还没有看到它。

其他想法

问题可以用 NxN 矩阵表示，其中行是“槽”，列是“人”，值为“1”表示空闲，“0”表示忙碌。然后，我们在这个矩阵中寻找一个行列交换的单位矩阵。步骤 1 和 2 正在寻找只有一个“1”的行或列。（如果矩阵的秩=N，则表示有解。但反之不成立）另一种看待它的方法是将矩阵视为未加权的有向图边矩阵。然后，每个节点代表 1 个候选和 1 个槽。然后，我们正在寻找一组边，以便图中的每个节点都有一条出边和一条入边。或者，如果有 2 个节点，它将是一个二分图。

矩阵示例：

我有这个功能

当我运行查询时

我能够获得 X 的值，但如果我这样做

我收到类似于每个查询的错误

未处理的异常：未知消息：type_error(nf(_G353**1,_G351),1,a numeric expression,_G353**1)

我尝试了其他运算符，它们都可以工作，我猜 ** 是特殊的，但我们具体如何处理呢？

下面的不等式系统在整数上求解 x1 和 x2。

x1 + x2 = l

x1 >= y1

x2 >= y2

x1 <= z1

x2 <= z2

l - z1 <= x2

l - z2 <= x1

l,y1,y2,z1,z2 是任意但固定且 >= 0。

使用示例值

l = 8

y1 = 1

y2 = 2

z1 = z2 = 6

我求解系统并得到以下方程：

2 <= x1 <= 6

x2 = 8 - x1

当我告诉 WolframAlpha 它应该对整数求解时，它只输出所有可能的值。

我的问题是我是否可以以编程方式为任何给定的 l,y1,y2,z1,z2 推导出 x1 和 x2 的方程/范围。这个问题与约束规划有关，我发现了一篇关于这个问题的旧论文： Harvey 等人的“Compiling Constraint Solveving using Projection”。

这种方法是否用于任何现代约束求解库？

我问这个的原因是我需要用不同的参数来解决像上面这样的系统几千次，如果整个系统被一遍又一遍地读取/优化/解决，这需要很长时间。因此，如果我可以编译一次我的参数化系统，然后只使用编译后的版本，我预计会有巨大的速度提升。

我在java中编程以下问题时遇到问题，这是一个约束满足问题：

如果我有这样的限制：

1. x1 + x2 > x3
2. x2 - x4 = 2
3. x1 + x4 < x5

每个x1tox5都在域中{0,1,2}

我如何对不同的组合进行编程，以便我将一组元组作为：{(0,0,0), (0,0,1), (0,1,0),(0,1,1),(1,0,0), ......}对于每个约束

这是即时的约束 1 具有元组域，例如{(0,0,0), (0,0,1), (0,1,0),(0,1,1),(1,0,0),(0,1,2),(2,0,1) ......}

我需要任何语言的回复，但最好是java。

我有一个 minizinc 模型，我想找到所有解决方案（我使用 gecode）然后打印统计信息，这很容易：

但是这个模型会生成数千个解决方案，并为每个解决方案打印一个分隔符：

我需要删除这些分隔符，只打印统计信息。有办法吗？

==更新==

我能够通过更改 Gecode 源来解决这个问题

我删除的地方

也许有更好的解决方案，但这对我很有用。