近似検索を使用して実ドメインの値を効率的に近似するにはどうすればよいでしょうか?

近似検索の仕組み

プロローグ

この記事は、次のことを包括的に理解することを目的としています。近似検索クラスの内部動作。次のようなタスクの実領域の値とパラメータを近似するように設計されています。多項式フィッティングと方程式の解法。

質問

フィッティングなどのタスクで、実領域 (倍精度浮動小数点数を使用) で値またはパラメータを近似するにはどうすればよいですか?多項式、パラメトリック関数のパラメーターの検索、または (難しい) 方程式の解決 (例:超越論)?

制限事項

• 実領域 (倍精度)
• C 言語
• 設定可能な近似精度
• 既知の間隔search
• 近似値またはパラメーターが厳密には単調ではないか、まったく関数ではない可能性があります

近似検索

近似検索は類似しています二分検索に移行しますが、検索される関数、値、またはパラメーターが厳密に単調関数でなければならないという制限が削除されます。この緩和にもかかわらず、同じ O(log(n)) の複雑さを維持します。

アルゴリズム

次の問題を考えてみましょう。

既知の関数 y = f(x) と目的の点 y0 から、 y0 = となるような x0 を見つけることを目指します。 f(x0).

既知の情報

• y = f(x) - 入力関数
• y0 - 目的の点 y 値
• a0、a1 - 解 x 間隔範囲

不明:

• x0 - 範囲

アルゴリズム手順:

1. プローブポイント x(i) = 一定のステップ da を使用して範囲に沿って等間隔に配置されます。

   例: x(i) = a0 i * da、i = 0, 1, 2, ...

2. 各 x(i) について、距離/誤差 ee を計算します。 y = f(x(i)) と y0 の間。

   この誤差は、ee = fabs(f(x(i)) - y0) などのメトリックを使用して計算できます。
3. 最小距離/誤差を持つ点 aa = x(i) を覚えておいてくださいee.
4. x(i) > のときに停止a1.

5. 再帰的に精度を高めます。

   • 検索範囲を、見つかった解の近傍に制限します:
     a0' = aa - da
     • a1' = aa da
   • 検索ステップを減らすことで検索精度を高めます:
     da' = 0.1 * da
   もし da' があれば小さすぎない、または最大再帰回数に達していない場合は、ステップ
   • 1 に戻ります。
6. 見つかった解は aa に保存されます。

C での実装

提供されている C コードは、近似検索アルゴリズムの実装を示しています。

#include "approx.h"
int main() {
    // Initialize the approx object with parameters
    approx aa;
    aa.init(0.0, 10.0, 0.1, 6, &ee);

    // Loop until a solution is found
    for (; !aa.done; aa.step()) {
        // Retrieve current x
        x = aa.a;

        // Compute y
        y = f(x);

        // Compute error
        ee = fabs(y - y0);
    }
}

以上が近似検索を使用して実ドメインの値を効率的に近似するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。