0

私は28の変数でこの方程式を解こうとしています：

y =（a1 * x1）+（a2 * x2）+ .... +（a28 * x28）

1）yは既知であるため、a1、a2からa28までも既知です。

2）x1、x2 ..... x28は未知の変数であり、0.1刻みで[-4、4]の範囲にあります。

ここで使用するのに最も効率的なアルゴリズムについて、誰かが私の困惑した脳に光を当てることができますか？

4

3 に答える 3

2

これは整数線形計画法と同等ですが、28 個の単純な制約 (連立方程式ではなく境界) を持つ方程式は 1 つしかないため、より適切に実行できる可能性があります。一般に、これは NP 困難になります ( https://en.wikipedia.org/wiki/Linear_programming#Integer_unknownsを参照してください) が、使用できる可能性のある実装がいくつかあります (たとえば、整数線形を選択する方法を参照してください)。プログラミングソルバー？）

于 2012-12-14T03:44:55.587 に答える
1

あなたはそれをプロローグでプログラムすることができます（SICStusプロローグエンジンと例えばEclipse上のSPIDERIDE）。この問題は状態空間探索の問題です。そして、clpfdライブラリ（有限ドメイン上の制約論理プログラミング）を使用します。次に、1つの制約を実行するだけで、X1からX28はドメイン変数になり、制約y＃= a1 * X1 + ... + a28*X28が与えられます。状態空間の検索を最適化する方法もいくつかあります。

/ edit：または、任意の命令型言語でそれを試すことができます。また、いくつかのヒューリスティックを使用します。たとえば、現在の結果を確認できる実行ポイントを選択します（たとえば、いくつかのtmp。sumがあり、28個の値から15個ですでにカウントされています。yからtempsumを引いた値がMIN_VARIABLE_VALUE未満の場合* i、iはインデックスであり、x_iは残りの変数に属している場合、続行しないことを安全に決定できます。bcs。等式を取得することはできません）。このヒューリスティックが最初に頭に浮かびます。使用は、これでいくつかの置換を使用することもできます。しかし、それがどれほど効率的であるかについて、いくつかのテストデータについて「調査」を行う必要があります。

于 2012-12-14T07:29:28.957 に答える
1

まず、整数計算にとどまることができるように、すべてに 10 を掛けます。また、両側に sum(40*a_u) を追加すると、x_i の範囲が [0,80] に変更されます。

次に、指数関数的な数の回答が存在する可能性があるため、アルゴリズムには指数関数的な時間がかかる必要があります。

80^28 (約 2^177) の可能な答えがあることを考えると、これは一般的に不可能です。

x_i の範囲が [0,1] ([0,80] ではない) で、y に等しい余分な項を追加する (y を 0 に変更する) 場合、問題はセットのサブセットを見つけることになります。合計がゼロになる整数。これはよく知られた NP 完全問題であり、あなたのものよりもさらに簡単に思えます (ただし、明確な還元はありません)。

動的プログラミングの解決策があるかもしれませんが、遅すぎるかもしれません:

set<float> X;

X.insert(0)

for i = 1 to 28
    for f = -4.0 to 4.0 step 0.1
        for x in X
            X.insert(x + a_i * f)

for x in X
    if (x == y)
        return true;

return false;

実行可能な範囲 ([y + a_i*(-4.0), y + a_i*4.0]) を返し、それらの範囲外の実行不可能な部分解を取り除くことで、これよりもうまくいくことができます。

于 2012-12-14T03:51:12.250 に答える