0

制約充足問題で割り当てられた変数の数を最大化する割り当てを見つけるための既知のアルゴリズム (またはアルゴリズムを見つけるためのリソース) は何ですか (満足のいく割り当てが存在しない場合)?

4

2 に答える 2

0

割り当てられた変数ではなく、満たされた制約の数を最大化したいのではないでしょうか? 割り当てられた変数の数を最大化することで何が得られるかを考えました (少なくとも 1 つの制約違反が自明に見られるまで)。満足できる制約の最大のサブセットの線に沿って何かが必要なようです。そうでなければ、あなたの最適化基準をおそらく理解できません。

満足できる制約のこの最大のサブセットが必要な場合は、問題を制約最適化問題に変換し、違反した制約の数を最小限に抑える割り当てを見つけてから、この割り当てが満たすすべての制約を選択して最大の制約を構築するというアイデアがあります。充足可能な制約のサブセット。

以下では、重み付き制約充足問題 (WCSP) のフレームワークを使用します。

制約を許可または不許可の部分代入のテーブルとして表すとすれば、許可された代入のコスト 0 と不許可の代入のコスト 1 を割り当てるだけで、制約を変換できます。コスト。結果として、コストを最小化する割り当ては、違反する制約の数を最小化します。これは、満たされる制約の数を最大化することと同じです。このような割り当てがあれば、すべての制約を反復処理して、割り当てがそれらを満たすかどうかを確認することで、満足できる制約の最大のサブセットを簡単に構築できます。WCSP の優れたソルバーは toulbar2 です。これは、指定された WCSP へのそのような最小コストの割り当てを計算します。

制約充足問題 (CSP) から WCSP を作成するのは、制約をテーブルとして表現する場合は簡単です。重み付けされた制約は、フォームの単なるテーブルです

X_1 X_2 … X_n   c

1    1 …   1    0 

1    2 …   1    0 

... 

2    2 …   3    1

2    2 …   4    1

ここでは、n 個の変数 X_1、…、X_n に対する制約があり、変数は有限ドメイン {1,2} および {1,2,3,4} からの値を受け入れることができます。許可されたタプルを「T」でマークし、許可されていないタプルを「F」でマークすると仮定すると、変換すると、「T」をコスト 0 に、「F」をコスト 1 に置き換えることになります。

これは実際の WCSP 形式ではないことに注意してください。形式については、上記のリンク先の toulbar2 パッケージで詳しく説明されています。

もちろん、制約をよりコンパクトに表現するには、より精巧な変換が必要になります。これは、表現によっては任意に複雑になる可能性があります。それはあなたが何か他のものを調べたいと思うかもしれないポイントです.

于 2013-03-01T16:48:36.340 に答える
0

線形方程式の場合、線形代数を使用して自由度の数、つまり割り当て可能な独立変数の数を見つけることができます。

編集：

あなたの問題をよく考えてみると、Simplex Algorithmがあなたを助けるかもしれないと思います。線形最適化問題の最適な整数解を見つけるための最適化アルゴリズムです。

編集2：

実行可能な領域を提供されたデポとします。

例：

X と Y の 2 つのデポ タイプがあるとします。

X には 5 オイルと 7 鋼が必要です。

Y には 8 オイルと 2 鋼鉄が必要です。

提供されるデポの数を最大化したい場合:

最大化する関数 = X + Y

条件：

X <= タイプ X のデポの総数 Y <= タイプ Y のデポの総数 5X + 8Y < 総石油供給量 7X + 2Y < 総鋼鉄供給量

シンプレックス アルゴリズムを適用すると、出来上がりです。

于 2013-02-21T09:08:26.417 に答える