近似検索で非単調関数の値とパラメータを効率的に見つけるにはどうすればよいですか?-C++-php.cn

近似検索で非単調関数の値とパラメータを効率的に見つけるにはどうすればよいですか?

DDD

リリース： 2024-12-30 22:54:10

オリジナル

626 人が閲覧しました

How Can Approximation Search Efficiently Find Values and Parameters for Non-Monotonic Functions?

関数フィッティングおよび方程式解法のための値とパラメーターの近似

近似検索の内部動作を理解することは、多項式、パラメトリック関数、および超越関数のフィッティングに関連する問題を解決する上で非常に重要です。方程式。このアプローチにより、厳密には単調ではない関数を扱う場合でも、値とパラメーターを効果的に推定できます。

近似検索の仕組み

近似検索は二分探索の概念を模倣しますが、そうではありません。検索関数が厳密に単調であるという制約を課さないでください。その仕組みは次のとおりです:

既知の間隔に均等に分散されたサンプルポイントを調べます。
関数値 f(x) 間の誤差または距離を計算します。各サンプルポイントとターゲット値 y0.
最小誤差を持つサンプルポイントを特定します (次のように表されます)。 aa).
精度を高めるために、aa を中心とした狭い間隔でステップ 1 ～ 3 を繰り返します。
必要な精度が達成されるか、最大再帰回数に達するまで再帰を続けます。

主な機能

非単調関数または単調関数を処理する機能は厳密な関数ではありません。
複雑度 O(log(n)) の信頼性が高く効率的なアルゴリズムを提供します。
ユーザー定義の精度と誤差の計算が可能です。

実装

これは近似の簡略化された C 実装です。 search:

class approx {
public:
    void init(double a0, double a1, double da, int n, double *e) {
        a0 = min(a0, a1); a1 = max(a0, a1); // Ensure a0 < a1
        da = abs(da);
        this->n = n; e = e;
        e0 = -1.0; i = 0; a = a0; aa = a0;
        done = false; stop = false;
    }
    void step() {
        if ((e0 < 0.0) || (e0 > *e)) { e0 = *e; aa = a; }  // Better solution
        if (stop) {
            i++;
            if (i >= n) { done = true; a = aa; return; }  // Final solution
            a0 = aa - fabs(da);
            a1 = aa + fabs(da);
            a = a0; da *= 0.1;
            a0 += da; a1 -= da;
            stop = false;
        } else {
            a += da;
            if (a > a1) { a = a1; stop = true; }  // Next point
        }
    }
};

ログイン後にコピー

使用例

y = f(x) が y0 に最も近くなるような x の値を見つけたいとします。近似クラスの使用方法は次のとおりです。

approx aa;
double ee, x, y, x0, y0 = your_target_value;
for (aa.init(0.0, 10.0, 0.1, 6, &ee); !aa.done; aa.step()) {
    x = aa.a;
    y = f(x);
    ee = abs(y - y0);
}

ログイン後にコピー