问题标签 [constraint-programming]

这是一个纯粹的编程问题。我有一个单词数组。单词后面有不同长度的停顿（大部分为零）。每个单词也有一个确定性分数。我想从前瞻窗口中选择最佳的单词跨度。

• 总体确定性越低越好（或者说确定性的第 33 个百分位数越低越好）。
• 边缘上的停顿时间越长越好（有一个硬的最小值）。
• 会有一个最佳长度（如 5 秒）。离它越近越好。最小和最大长度会有硬性限制。

注意，这是在 JavaScript 中，所以我不能使用支持向量机或类似的东西。:-) 对于性能想法，它可能会在 2 分钟长度（250 个字左右）的窗口上每分钟计算一次。

对于感兴趣的人来说，第二个好处是：这是选择自动语音识别生成的单词范围进行手动转录（主动学习）。

你会如何处理这个问题？

我正在关注 Ivan Bratkos 的“人工智能第四版 Prolog 编程”，我目前正在阅读有关约束逻辑编程的内容。

书中有一个用于任务调度的小型优化示例，如下所示：

在 swi-prolog 中导致

结果很好（尽管如果它像书中那样写 {Tc =< 4} {Tc >= 2} 会更漂亮），但我不明白为什么它添加了 '_G377=2- _G371'部分，-似乎很没必要……

为什么将这个额外的变量 (_G377) 添加到结果中？

如果其他人正在阅读这本书：我已将“Ta =< 0”更改为“Ta >= 0”，因为我认为“Ta =< 0”是书中的错误。

我正在开发一个求解器来解决递归约束。求解器的工作原理就是这样，例如给定一个递归定义为的序列a(n) = a(n-1)*2 + 2。然后求解器将找到表示a(n)基于的确切公式n。您可以在 wolfram alpha 中查看此示例以获得更多理解

在编程中。计算序列的程序是这样的：

然后通过使用我们的求解器，我可以表示a[n]并将n这个特征添加到约束中。但是，我正在寻找现实世界的例子，其中包括像这样的递归序列或线性递归关系。你知道任何可以作为我的测试台的代码吗？

我正在阅读文档中的矛盾内容。

一方面，这段话似乎表明连续的计划变量是可能的：

计划值范围是计划变量的一组可能的计划值。该集合可以是离散的（例如第 1、2、3 或 4 行）或连续的（例如 0.0 和 1.0 之间的任何双精度）。

另一方面，在定义计划变量时，您必须ValueRangeProvider在字段上指定注释以用于值集：

解决方案实现具有返回集合的方法。该集合中的任何值都是此计划变量的可能计划值。

这两个片段都在文档的同一部分（http://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/#d0e2518）

那么，它是什么？我可以使用完整double的作为我的计划变量，还是需要将其范围限制为特定的值Collection？

查看所提供的实际算法，我没有看到任何真正适合优化连续变量的算法，所以我怀疑它是否可能，但最好能澄清并明确说明。

C++ 或 C# 中的 optaplanner/drools planner 是否有类似的替代方案？我只找到了 2007 年的一个非常古老的 C# 移植。或者你如何解决 C++/C# 中的 NP-hard 优化问题？

如何在约束编程中陈述以下约束？（最好在 Gurobi 或 Comet 中）。

S 是一个大小为 n 的整数数组。我可以用来填充数组的整数集在 1-k 范围内。每个可以使用的整数都有一个约束ci 。ci表示连续整数i的最小数量。

例如，如果 c1 = 3, c2 = 2，则 1112211112111 不是有效序列，因为必须有两个连续的 2，而 1112211122111 是有效序列。

我遇到了一个令人惊讶的具有挑战性的问题，即安排受以下约束（或决定不可能）的值的类似矩阵（列表列表）：

一个由 m 个随机生成的行组成的矩阵，最多具有 n 个不同的值（行内没有重复），排列矩阵使得以下内容成立（如果可能）：

1）矩阵必须是“下三角”；行必须按升序排列，因此唯一的“间隙”位于右上角

2) 如果一个值出现在多行中，则它必须在同一列中（即允许重新排列一行中的值的顺序）。

用函数式语言（例如 Scala）表达问题/解决方案是可取的。

示例 1 - 有一个解决方案

AB
CED
驾驶室

变成（作为一种解决方案）

AB
EDC
ABC

因为 A、B 和 C 都分别出现在第 1、2 和 3 列中。

示例 2 - 没有解决方案

ABC
ABD
BCD

没有解决方案，因为约束要求第三行在第三列中有 C 和 D，这是不可能的。

我正在实现一个随机 CSP 生成器，用于对两种不同的弧一致性算法（AC3 和 AC2001）进行比较测试。实例的生成参数包括变量数量、所有变量的域大小 8 相同）、约束数量和每个约束拒绝的值对的数量（所有约束都相同）。

我的实现构建了变量（具有两个字段的结构，名称和域（列表）），约束 8 具有两个字段的结构，涉及的变量和约束函数））。它创建一个哈希表，其中包含每个约束中涉及的变量作为键，作为值是所述约束拒绝的对的列表。使用时，每个约束都会检查变量的给定值是否包含在拒绝值列表中。

此实现“有效”，但生成的实例很少需要弧缩减，因此它们对于测试目的大多无用。这是代码：

此函数创建限制和拒绝值

此函数创建拒绝值哈希表

以及创建全局参数供求解器使用的主函数

函数“pertenece”检查一个元素是否在 我希望可以理解的列表中，即使是西班牙语名称。如果不是，我可以完全翻译。

所以，抛开我可怕的 lisp 编码技能不谈，有没有我可以修复或改进的错误，以使生成的实例质量更高？

clpfd 是 SWI Prolog 中整数的约束编程库。有没有类似的集合库？如果没有，您是否知道任何对实现此类库有用的文章？

它完全可行吗？我真的在寻找任何类型的输入，因为我的谷歌搜索没有返回任何感兴趣的内容。

编辑：搜索时使用引号可以得到更好的结果（doh！）。嗯……无论如何，很高兴收到反馈。

编辑：有一个包含 B-Prolog (clpset) 的库正是这样做的。

任何或多或少实用的编程语言和编译器都必须处理约束。最常见的约束是类型。通常类型推导和统一是通过一个简单的算法（例如Hindley-Milner）完成的，最终程序中的所有项都被分配了唯一的类型。如果没有发生，则有错误指示。

编译器中可能存在更复杂的约束，其中不可能完全统一，并且解决方案仅在某些限制下存在。可能的例子是

• 数据流分析。仿射等式约束的解可用于循环向量化。

• 内存管理。如果我们对引用和数据访问模式有一些限制，编译器可以从优化引用计数和垃圾收集中受益。

另一方面，约束求解器，如 Z3 或 Yices，在为不同类型的约束寻找可满足模型方面非常强大。

我正在寻找有关编译器如何从 SMT 求解器的强大功能中受益以及它们正在解决什么样的任务的成功案例。我列出了一些领域，但我没有找到任何具体的例子。你能提出任何建议吗？