1

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要素のサブセットを反復処理して、m個の制約を満たすサブセットを見つけることはできません。

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

このようなCSPには、どのような手法が一般的に使用されていますか？誰かが私にこのような問題について話している良い本や記事の方向を示すことができますか（一般的なCSPだけでなく、離散値ではなく連続的な値を含むCSP）？

4

4 に答える 4

1

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

の形状について詳しく知らなければf、時間が多項式であるかどうかを保証することはできません（または、制約を満たすスポットをヒットする方法についてのアイデアさえありません）。結局のところ、f_1 = (x^2 + y^2 - 1)andf_2 = (1 - x^2 - y^2)と制約がf_1 < 0andf_2 < 0である場合、これを完全に満たすことはできません（そして、関数の分析形式にアクセスできなければ、確実に知ることはできません）。

于 2010-09-08T19:23:08.950 に答える
1

独自のアプリケーションを作成し、既存のライブラリを使用してこれを行うことを検討していると仮定すると、 Python制約、Javaの場合はCreamまたはChoco、C ++の場合はCSPなど、多くの言語で選択肢があります。問題を説明した方法では、汎用のCSPソルバーを探しているように聞こえます。単調であるなど、複雑さを軽減するのに役立つ可能性のある関数のプロパティはありますか？

于 2010-09-08T19:23:10.943 に答える
0

これは非常に難しい問題のように見えます。線形関数を使用する最も単純なケースでは、線形計画法を見ることができます。

于 2010-09-08T19:37:25.857 に答える
0

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

検討：

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

さて、平均で10から50を生成する、{1...100}のサブセットをいくつ思いつくことができますか。

于 2010-09-08T19:24:20.600 に答える