问题标签 [constraint-satisfaction]

我只是希望有人验证以下问题是否是 NP 完全的，或者实际上是否有比简单的蛮力组合检查更好/更容易的解决方案。

我们的软件中存在某种资源分配问题，我将用一个例子来解释它。

假设我们需要 4 个人在白班期间工作。这个数字，以及它是“白班”的事实都记录在我们的数据库中。

但是，我们不要求任何人来填补这些空缺，为了满足要求，需要满足一些要求。

在这 4 人中，假设其中 2 人必须是护士，其中 1 人必须是医生。

其中一名医生还必须作为特定团队的一员工作。

所以我们有这组信息：

白班：4
   1医生
   1医生，需要在A组工作
   1护士

以上不是问题。当我们开始挑选人员进行白班工作并试图弄清楚我们迄今为止挑选的人员是否真的能够满足标准时，问题就出现了。

例如，假设我们选择 James、John、Ursula 和 Mary 工作，其中 James 和 Ursula 是医生，John 和 Mary 是护士。

Ursula 也在 A 队工作。

现在，根据我们尝试满足要求的顺序，我们最终可能会推断出我们是否有合适的人，除非我们开始尝试不同的组合。

例如，如果从列表中首先选择 Ursula，我们可以将她与“1 位医生”标准进行匹配。然后我们到了 James，我们注意到，由于他不在 A 队工作，所以关于“1 位医生，需要在 A 队工作”的其他条件，不能由他填写。由于另外两个人是护士，他们也不符合这个标准。

所以我们回溯并首先尝试詹姆斯，他也可以满足第一个标准，然后厄休拉可以满足需要该团队的标准。

所以问题对我们来说是因为我们需要尝试不同的组合，直到我们全部尝试过，在这种情况下，我们有一些标准尚未满足，即使工作的正面总数与总数相同需要的磁头数量，或者我们找到了一个有效的组合。

这是唯一的解决方案，有人能想到更好的解决方案吗？

编辑：一些澄清。

对这个问题的评论提到，对于这几个人，我们应该使用蛮力，我同意，这可能是我们可以做的，我们甚至可以这样做，在同一条车道上，某种优化着眼于如果数据量小，则选择不同的排序算法，初始开销较小。

但问题是，这是一个名册规划系统的一部分，其中可能有很多人参与其中，既是“我们需要 X 人上白班”，又是“我们有这个 Y 人池那将是这样做的”，以及一个大型“我们为那些必须以某种方式与这些 Y 人匹配的那些 X 人的 Z 标准列表”，然后你补充说我们将拥有当领导者调整花名册时，需要在几天内实时进行相同的计算，然后就需要快速解决方案。

基本上，领导者会在屏幕上看到一个实时总和信息，说明还有多少人仍然失踪，无论是在整个白班，还有多少人符合各种标准，以及我们实际上有多少人除了我们拥有的那些。当领导者用“如果詹姆斯上白班而不是乌苏拉，乌苏拉上夜班怎么办”来调整名单时，这个显示将不得不更新半直播。

但是非常感谢到目前为止已经回答这个问题的人，约束满足问题听起来像是我们需要走的路，但我们肯定会仔细研究这里的所有链接和算法名称。

这就是我喜欢 StackOverflow 的原因 :)

我必须使用Java Constraints Library解决CSP逻辑问题。现在我已经设法表示了问题的一些约束，其中大多数基于“等于”和“不等于”二元约束。我的疑问是，如何表示基于加法的约束？例子：

• variable1 属于 DomainA
• 变量2属于域B
• variable3 属于 DomainA
• 变量4属于域B

现在的约束：

• variable1 和 variable2 之和大于 variable3 和 variable4 之和。

观察：这些变量代表金钱，所以可以相加。

我有一组 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，而不是离散值）？

在性能和用例方面，模拟退火（使用 bean 搜索）和遗传算法之间有哪些相关差异？

我知道 SA 可以被认为是人口规模只有一个的 GA，但我不知道两者之间的关键区别。

此外，我正在尝试考虑 SA 将优于 GA 或 GA 将优于 SA 的情况。一个简单的例子可以帮助我理解就足够了。

我对 CSP 比较陌生，我试图根据变量之间施加的 ==、>、< 和 != 约束从它们各自的域中找到所有变量的值。我查看了 Choco 和 Jacop，但我找不到更多关于解决这类问题的信息。你能指出我可以找到这个例子的实现的地方吗？我已经使用 Prolog 解决了这个问题，但我想使用 OOP 来完成它。

谢谢你。

我有一个经典的时间表问题，由变量 classes(~100)、rooms(20)、terms(8) 和 weekdays(5) 组成。

为了简化问题，以下是减少的约束。

一天是9个小时。

有些课程是学生必修课，1、3、5、7（以及 2、4、6、8）的必修课不得相互重叠。

课程在小时数方面有不同的权重，有些是 2 小时，有些是 3 小时。

有些课程应该在特定的房间。

同一堂课不能同时开两节课。

我将使用 logilabs python 约束模块。而且我知道明智地选择变量和域将减少解决问题的时间。问题是我以前从未做过约束编程，并且很难建立问题来找出从哪里开始以及从什么开始。例如：

我可以设置一个约束，例如“同一个房间没有两个班级，同一天可以重叠彼此的时间段”。或者从“没有房间可以在同一天预订超过 9 小时”开始，然后继续减少解决方案域。我估计（没有尝试）第一个约束将比另一个约束需要更长的时间来解决。但它也需要（我猜）改变变量和解决方案域或重建一个较小的问题。我已经对变量、域、间隔、实现等有点迷失了。

长话短说，我需要一些指针来构建问题、解决方案域、明智地选择变量等。

谢谢

更新

使用 logilab-constraint 包，我制作了一个基本应用程序并将其上传到github

我已经解决了以下约束处理任务。你能验证它是否正确吗？

这是我的解决方案，希望你们帮我检查哪里做错了：

我的约束
我以这样一种方式声明了约束，即每次当时间为偶数时，摄像机的视图交替改变，但当时间为偶数时，只有囚犯可以移动。

伙计们，我知道我做错了什么，所以请帮助我纠正它。

谢谢你的帮助。我昨天发布了一个类似的问题，所以如果你想知道变量和约束的语法，那么这是链接： 这篇文章中的变量和约束语法

谢谢你的帮助

所以我的目标是编写解决数独难题的方法，我们得到了方法存根“public int[][] solve(int[][] board)”。我们应该使用弧一致性和域分割来找到解决方案。

- 我开始这样做的方式是在板上（键）及其当前域（初始化为 1..9，除非给定）上制作点的 hashMap ->HashMap<Point, ArrayList<Integer>> curDomains = new HashMap<Point, ArrayList<Integer>>();虽然我不确定这是否是最好的数据结构利用。

-我的问题是如何表示弧和约束？我有算法的伪代码，但我不知道如何在 java 中表示约束/弧。表示C 的最佳方法是什么：要满足的一组约束（它们是数独板上的有效位置）以及我的弧 A < X, c> 其中 X 是一个点，c 是约束。

我提前感谢您的有益评论。

抽象问题描述：

在我看来，解解析意味着从 AST 创建一个令牌流，当再次解析时会产生一个相等的 AST。

所以 parse(unparse(AST)) = AST成立。

这等于找到会产生相同 AST 的有效解析树。

该语言由使用eBNF变体的上下文无关 S 属性语法描述。

因此，解解析器必须通过遍历所有语法约束的节点找到有效的“路径”。这基本上意味着找到AST节点到语法产生规则的有效分配。这通常是一个约束满足问题 (CSP)，可以像解析一样通过O(exp(n)) 中的回溯来解决。

对于解析来说幸运的是，这可以使用GLR（或更好地限制语法）在 O(n³) 中完成。因为AST结构与语法生成规则结构如此接近，我真的很惊讶看到运行时比解析更糟糕的实现：XText使用ANTLR进行解析，回溯用于反解析。

问题

1. 上下文无关的 S 属性语法是解析器和非解析器需要共享的所有内容，还是存在进一步的限制，例如解析技术/解析器实现？
2. 我感觉这个问题一般不是 O(exp(n)) - 有天才能帮我解决这个问题吗？
3. 这基本上是一种上下文相关的语法吗？

示例 1：

所以如果我有一个 AST 包含

AnyObject -> AnyObject -> Vehicle [name="Car"] 我知道根可以是区域，我可以解决它

所以 (Highway | Pedestrian) 决策取决于子树决策。当叶子乍一看可能是几种类型中的一种时，问题会变得更糟，但必须是特定的叶子才能在以后形成有效路径。

示例 2：

因此，如果我有返回无类型对象的 S 属性规则，只需分配一些属性，例如

因此，如果 AST 包含

我可以将其解析为

就在我可以将“C”解析为C之后。

在遍历 AST 时，我可以从语法生成的所有约束都满足规则 A 和 X，直到我点击“C”。这意味着对于

树的两种解决方案

是有效的，并且认为它们具有相同的语义，例如句法糖。

更多信息：

• 在 XText 中解析

• 用于反解析的语法约束，请参阅 Serializer: Concrete Syntax Validation

嗨，我需要一个非确定性约束满足问题工具，因为我需要具有相同问题输入的不同解决方案。有人知道具有这种特性的工具吗？

我只知道像 Gecode (c++)、Choco (Java) 和 Curry (Haskell) 这样的工具，我认为它们以确定性的方式工作。