1

Javaまたは.NETのいずれかで制約充足（CSP）問題をモデル化する必要があります。この問題では、変数の階層を表す必要があります。したがって、ツリーのすべてのノードは変数です。

たとえば、変数C1が別の変数C2の子であり、C1がtrueの場合、C2はその親であるため、C2はtrueである必要があります。同時に、ブランチ内の変数ノードがtrueの場合、階層内で選択できるブランチは1つだけであるため、他のブランチ内のすべての変数がfalseであることを意味します。

CSPの問題としてどのように表現できますか？また、Javaまたは.NETでどのツールを使用できますか？

これ以上のものがあるので、詳細を提供するために編集する必要があります。

私の問題には2つの部分があります。最初の部分には、最大化関数q1 * x1 + q2 * x2 + q3 * x3 ..があります。ここで、qiは係数（実数）、xiは変数（0にすることができます）です。または1）そして私はこの関数を最大化するxiのいくつかを選択する必要があります。つまり、ノードは0または1のみであり、階層からノードを選択してこの機能を最大化する必要があります。

繰り返しますが、これらのxi変数はツリーのノードであるため、いくつかのxiを選択する場合、それらはツリーの同じブランチからのものである必要があり、一度に1つのブランチのみを選択できます。したがって、これらの階層的制約を表す必要があります（第2部）。すべてをlp問題として表現するのが最善かもしれませんが、線形計画法の制約を使用してツリーを表現する方法がわかりません。

同時に、最大化問題（前半）を使用してCSP制約を課すことができるかどうか（LP制約を使用しないかどうか）はわかりません。

4

3 に答える 3

1

Java には、制約充足問題 (CSP) のソルバーが多数あります。以下は不完全なリストです。

そうは言っても、言及していない他の制約がない限り、CSPソルバーを使用するのはやり過ぎだと思います。必要なのは、問題を変数に対応するノードを持つグラフ (ツリー?) として扱うことだけです。次に、リーフ ノードを取得し、途中で変数を true に設定し、残りのすべての変数を false に設定すると、解決策が得られます。これに必要なのは、JGraphTなどのグラフ ライブラリだけです。

于 2013-02-28T03:55:03.203 に答える
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 に答える
0

Drools Planner (オープン ソース、Java)は、従来の CSP 実装を超えてスケ​​ーリングし、スコア設計 (非線形制約、複数のスコアの重みとレベルなど) もより柔軟ですが、最適なソリューションを見つけたときに認識しません。 .

于 2013-02-28T08:04:57.970 に答える