制約の満足度：特定の特性を持つ実数を選択します

Question

私はnの実数のセットを持っています。私も一連の関数を持っています、

f_1, f_2, ..., f_m.

これらの各関数は、数字のリストをその引数として採用しています。私も一連のm範囲を持っています、

[l_1, u_1], [l_2, u_2], ..., [l_m, u_m].

したい 繰り返し K要素のサブセット{r_1、r_2、...、r_k}を選択してください。

l_i <= f_i({r_1, r_2, ..., r_k}) <= u_i for 1 <= i <= m.

関数は滑らかであることに注意してください。 {r_1、r_2、...、r_k}の1つの要素を変更しても、F_i（{r_1、r_2、...、r_k}）は多く変更されません。平均と分散は、一般的に使用される2つのF_Iです。

これらは、私が満たすために必要なMの制約です。

さらに、私が選択したサブセットのセットが、これらのM制約を満たすサイズKのすべてのサブセットのセットに均一に分布するようにこれを行いたいと思います。それだけでなく、これを効率的にやりたいと思っています。実行される速さは、可能なすべてのソリューションの空間内のソリューションの密度に依存します（これが0.0の場合、アルゴリズムは永久に実行できます）。 （F_I（任意のIの場合）は、一定の時間で計算できると仮定します。）

nは十分に大きいため、問題に耐えることができないことに注意してください。つまり、すべてのK要素のサブセットを繰り返して、どのマンの制約を満たしているかを見つけることはできません。

これを行う方法はありますか？

このようなCSPには一般的にどのようなテクニックが使用されますか？誰かが私をこのような問題について話す良い本や記事の方向に私を向けてもらえますか（一般的なCSPだけでなく、離散的な値とは対照的に連続するCSP）？

Answer 1

独自のアプリケーションを作成し、既存のライブラリを使用してこれを行うと仮定すると、多くの言語に選択肢があります。 Python-Constraint, 、 また クリーム また チョコ Javaの場合、または CSP C ++の場合。問題を説明した方法は、汎用CSPソルバーを探しているように聞こえます。単調であるなど、複雑さを減らすのに役立つ可能性のある機能の特性はありますか？

Answer 2

あなたが説明したように問題を考えると、あなたは各範囲から選ぶことができます r_i 均一に、基準を満たすことができないm次元のポイントを捨てます。オリジナルが均一に分布し、サブセットのセットがオリジナル上のバイナリマスクであるため、均一に分布します。

の形についてもっと知らずに f, 、時間が多項式であるかどうかについて保証することはできません（または、制約を満たす場所を打つ方法についての考えさえあります）。結局のところ、if f_1 = (x^2 + y^2 - 1) と f_2 = (1 - x^2 - y^2) そして、制約はです f_1 < 0 と f_2 < 0, 、これをまったく満たすことはできません（そして、関数の分析形式にアクセスしないと、確実に知ることはできません）。

Answer 3

あなたのメッセージの情報を考えると、それがまったくできるかどうかはわかりません...

検討：

• 数字= {1 .... 100}
• m = 1（シンプルに保ちます）
• F1 =平均
• L1 = 10
• U1 = 50

さて、{1 ... 100}のサブセットはいくつあるのでしょうか。

Answer 4

これは非常に難しい問題のように見えます。線形関数を備えた最も単純なケースでは、線形プログラミングを見ることができます。