问题标签 [constraint-programming]

我现在正在学习一些 CSP（约束满足）理论的东西，并且正在使用这个库来解析 XML 文件。我使用 Xcode 作为 IDE。

我的程序编译得很好，但是当它链接文件时，XMLParser_libxml2.hh 文件出现重复符号错误。我的文件是这样分开的：

包含上述 XMLParser 文件的类头文件 包含
类头文件的类实现文件 包含类头文件
的主文件

重复符号出现在 main.o 和 classfile.o 中，但据我所知，我实际上并没有将该 .hh 文件添加两次。

完整错误：

将类的实现复制到主文件中并将类实现文件从编译目标中取出会消除错误，但这样会变得杂乱无章，我很快就会添加更多类（如果将它们放在单独的文件中）。

据我了解，这是由文件（XMLParser_libxml2.hh）在一个文件中同时具有类和函数定义和实现引起的（由于在那个'头'文件）。关于如何绕过将所有类文件粘贴在 main.cpp 中的任何想法？（我试过了#ifdefs，它们不起作用）。

尝试对以下内容进行一些研究，但没有成功。以为我会在这里问，以防有人以前遇到过。

我帮助一个志愿者经营的广播电台满足他们的技术需求。出现的主要事情之一是他们希望以编程方式安排他们的广告。

有很多简洁而复杂的广告规则引擎，但我们所需要的只是一些非常简单的东西（以及任何值得思考的经验）。

如果可能的话，我想用 SQL 写一些东西来处理这些实体。理想情况下，如果有人为其他广告媒体（网络等）写过类似的东西，那将非常有帮助。

实体：

• 广告（包括类别、每天播放次数、开始日期、结束日期或永久播放）
• 广告类别（餐厅、健康、食品店等）

为了过度简化问题，这将是一个优雅的 sql 语句。到达那里... ：）

我希望能够使用上述两个实体每天生成一个播放列表，其中：

• 在彼此的 x 个广告内没有播放同一类别的两个广告。
• （很高兴）可以推送高促销广告

此时，没有“广告位”可以填充。没有“一天中的时间”考虑。

我们将当天的广告排成队列，并在歌曲/节目之间浏览它们等。我们知道每小时必须填充多少，等等。

任何想法/想法/链接/示例？我将继续寻找并希望能遇到一些东西，而不是长期学习。

我有许多可变大小的列表，其中包含具有属性 foo 的同一类的实例，并且对于每个列表，我必须应用以下规则：

• 如果有一个元素 foo=A 则 [B,C,D] 中不能有带有 foo 的元素
• 如果有一个元素 foo=X 必须至少有一个 foo 在 [Y,Z]
• 可以在 MIN 和 MAX 元素之间存在 foo=BAR

结合以上三个规则可能足以表达我需要的任何类似约束。这有点像软件包中的依赖项检查，但我有数量并且缺少版本:)

一种天真的方法是：

这是约束编程的问题吗？我实际上不需要解决某些问题来获得结果，我需要根据一些约束验证我的列表并检查它们是否满足。你会如何分类这个问题，你会如何解决它？

对于它的价值，我正在用 Python 进行编码，但我欢迎一个通用的编程答案:) 如果事实证明我必须深入研究约束编程，我可能会从尝试python-constraint开始。

我有一组 n 个实数。我还有一组函数，

这些函数中的每一个都将数字列表作为其参数。我也有一组 m 范围，

我想重复选择 k 个元素的子集 {r_1, r_2, ..., r_k} 使得

请注意，函数是平滑的。更改 {r_1, r_2, ..., r_k} 中的一个元素不会使 f_i({r_1, r_2, ..., r_k}) 发生太大变化。平均值和方差是常用的两个f_i。

这些是我需要满足的 m 个约束。

此外，我想这样做，以便我选择的子集集均匀分布在满足这些 m 个约束的所有大小为 k 的子集的集上。不仅如此，我还想以一种有效的方式做到这一点。它运行的速度取决于所有可能解决方案空间内的解决方案密度（如果这是 0.0，那么算法可以永远运行）。（假设 f_i（对于任何 i）可以在恒定时间内计算。）

请注意，n 足够大，我不能蛮力解决这个问题。也就是说，我不能只遍历所有 k 元素子集并找出满足 m 个约束的子集。

有没有办法做到这一点？

什么样的技术通常用于这样的 CSP？有人可以向我指出谈论此类问题的好书或文章的方向（不仅仅是一般的 CSP，而是涉及连续的 CSP，而不是离散值）？

我已经开始学习约束编程，我觉得它可以很好地与 Haskell 一起使用（我也喜欢使用 Haskell）。

Haskell 有成熟的约束框架吗？

PHP 是否有任何约束编程库？能够处理这种情况的东西。

我有一个可能很愚蠢的问题。我目前正在测试 CSP 求解器 choco 和 jacop。当我运行应用程序分析（图形着色，大约 3000 个节点）时，我不完全理解结果。

profiler 声明的已用堆空间约为 1GB 内存。创建的所有对象的总和小于 100MB。其他 900MB 的 RAM 在哪里？

我认为方法调用（求解器可能使用大量回溯）被分配在堆栈上，所以这不应该是问题所在。当我使用 Xmx 参数减少最大内存时，应用程序失败并出现异常：

线程“主”java.lang.OutOfMemoryError 中的异常：超出 GC 开销限制

所以看起来，其余的不是未使用的未收集内存（因为在这种情况下，GC 会释放它（并且不会失败））。

谢谢你的帮助。

我对 SMT Z3 使用（如 DbC）的实际示例感兴趣并寻找该工具的代码和开源替代品。所以，其实我对类似的Z3形式求解工具很感兴趣，但是：

• 它必须是开源的
• 提供低级（API）和高级（文本脚本）交互
• 支持 SMT-LIB
• 适用于（可用）工具/编写/用于 Java、python、ruby、Vala 等语言，而不是Haskell
• 有基于它的稳定（在实践中可用）工具，如按合同设计（DbC）、静态类型验证等。

根据 SMT-LIB 主页（详见 bit.ly bundle），2010 年 SMT 求解器列表为：“Alt-Ergo、Barcelogic、Beaver、Boolector、CVC3、DPT、MathSAT、OpenSMT、SatEEn、Spear、STP、SWORD、 UCLID、veriT、Yices、Z3。”

请就在实践中使用它们提供任何反馈（代码示例是最好的）？

最后，将它与 GHC 可能性进行比较的任何信息都是有用的，但前提是存在实现示例（不是语言“功能”）。

更多关于 Z3 的快速信息在这里http://bit.ly/bundles/ewiger/1

我正在制作一个函数，该函数接收司机和乘客及其位置的列表，并将乘客分配列表返回给司机，以最大限度地增加分配给司机的乘客数量，但受以下约束：

1. 一名乘客只能乘坐一辆车

2. 每节车厢分配的乘客人数不能超过车厢规定的座位数

3. 每个司机接载所有乘客的行程距离不能超过某个任意常数

我遇到的问题是添加第一个约束。我一直在关注http://uswaretech.com/blog/2009/03/constraint-programming-in-python/上的教程，并且我使用了与他们解决幻方问题类似的风格：乘客的分配to a car 存储为元组（司机，乘客），这些元组存储在列表中。驾驶员和乘客的实际详细信息存储在包含他们的 ID、纬度和经度以及每个驾驶员车内有多少座位的类中。这是我用来构建问题的代码，从文件中提取了测试数据：

以交互方式运行后，我发现我可以在添加约束之前运行 getSolutions() ，但是在运行整个过程时出现以下错误：

似乎在 getSolutions() 方法中的某个时候它会尝试查找 (2,0)，即使第一个元组的最大值是 1（我的数据集中只有 2 个驱动程序）。我运行了教程中的代码，它运行良好，我只是不确定我的代码有什么不同会导致错误，除了我使用 MaxSumConstraint 而不是 ExactSumConstraint。

我正在写一门描述人工智能几个主题的课程。目前我正在研究“约束处理”部分。为了说明约束处理，我想举一个简单的例子。这个例子应该具有以下品质：

• 我想画一个 OR-tree 所以这个例子不能有那么多的变量和选项
• 说明节点一致性、回溯、回跳、回标、弱松弛和弧一致性。（这些例子应该说明这些方法是有意义的，并为约束处理增加了一些价值）。
• 易于理解和表示。（不是两页长的约束数组）。

我已经浏览了一段时间的网络，但现在所有的例子都不符合这些品质。（我也试图简化现有的问题）。

有没有典型的例子来说明这些方法/技术？给出两个不同的示例并在这两个示例之间分配技术也不是问题。