私は頭の中にプロジェクトがあり、似たようなことが以前に行われたかどうかに興味があります。さまざまなタイプの制約のセットがあり、これらの制約を一緒に満たすことはできないとします。
C = {c1、c2、c3、...、cn}
(c1 and c2 and c3 ... cn) : 満足できない
私の目的は、このセットを k 個のセット (おそらく k は非常に小さい) に分割して、すべての制約セットが個別に満たされるようにすることです。
基本的な解決策は、貪欲なアプローチを使用することです。制約は最初の制約として選択され、最初のグループとしてラベル付けされます。次に、2 番目の制約が選択され、最初の制約で解けるかどうかがチェックされます。それらが解決可能である場合、2 番目の制約も最初のグループに含まれます。それ以外の場合は、2 番目のグループとしてラベル付けされます。このプロセスは、セットに制約がなくなるまでこの方法で続行されます。これを行う別の方法は、制約を 2 つのセットに分割し、これらのセットが個別に解決可能かどうかを確認することです。そうでない場合は、再帰的に分割を続けます。これら 2 つのアプローチはどちらもサイズが大きくなり、制約セットを非常に小さなセットに分割します。
k が最適値 (最小の k 値) に近い k セットに制約セットを分割する効率的な方法を探しています。ここには 2 つの課題があります。1) スケーラビリティの問題と 2) 制約の構造が事前にわかっていないことです。