1

我需要在 Java 或 .NET 中对约束满足 (CSP) 问题进行建模。该问题需要表示变量的层次结构。所以树的每个节点都是一个变量。

例如，如果变量 C1 是另一个变量 C2 的子变量，并且如果 C1 为真，那么 C2 应该为真，因为它是他的父变量。同时，如果一个分支中的一个变量节点为真，这意味着其他分支中的所有变量都是假的，因为在层次结构中只能选择一个分支。

我如何将其表示为 CSP 问题，我可以在 Java 或 .NET 中使用哪个工具？

我必须对其进行编辑以提供更多详细信息，因为还有更多：

在我的问题中，有 2 个部分：在第 1 部分中，有一个最大化函数 q1*x1+q2*x2+q3*x3.. 其中 qi 是系数（实数），xi 是变量（可以是 0或 1) 我必须选择一些最大化此功能的 xi。换句话说，节点只能是 0 或 1，我必须通过从层次结构中选择一个节点来最大化这个功能。

同样，这些 xi 变量是树的节点，所以当我选择一些 xi 时，它们必须来自树的同一分支，并且一次只能选择 1 个分支。因此我需要表示这些分层约束（第二部分）。最好的办法是将所有内容都表示为 lp 问题，但我不知道如何表示具有线性规划约束的树。

我不知道我是否可以同时使用最大化问题（第一部分）并施加 CSP 约束（而不是使用 LP 约束）。

4

3 回答 3

1

Choco is a constraint solver that is implemented in Java and offers a Java API. It sounds like you want to use reified constraints in your model, that is constraints of the form

reify(otherConstraint(...), variable)

where variable becomes true or false depending on whether otherConstraint is satisfied or not. You can model the tree hierarchy by introducing auxiliary variables and adding reification constraints. Then you can link the auxiliary variables with a set of additional constraints to achieve effects such as you describe.

Alternatively, you could use simple conjunctions and disjunctions of constraints to model the tree -- whether this is possible will depend on the other constraints that determine the assignments to your variables.

于 2013-02-27T16:57:09.253 回答
1

Java 中有许多用于约束满足问题 (CSP) 的求解器。这是一个不完整的列表：

也就是说，我认为在你的情况下使用 CSP 求解器是一种过度杀伤，除非你有一些你没有提到的其他限制。您所需要的只是将您的问题视为具有对应于变量的节点的图（树？）。然后取一个叶节点并一直到顶部设置变量，一路设置为 true 并将所有剩余变量设置为 false 将为您提供解决方案。为此，您只需要一个图形库，例如JGraphT

于 2013-02-28T03:55:03.203 回答
0

Drools Planner (open source, java)扩展了传统的 CSP 实现，并且在分数设计（非线性约束，多个分数权重和级别，...）方面也更加灵活，但在找到最佳解决方案时无法识别它.

于 2013-02-28T08:04:57.970 回答