我们如何使用近似搜索有效地近似实域值？

近似搜索的工作原理

序言

本文旨在提供对近似搜索类的内部工作原理，旨在近似任务实域中的值和参数例如多项式拟合和方程求解。

问题

我们如何近似任务的实域中的值或参数（使用双精度浮点数）例如拟合多项式、在参数函数中查找参数或求解（困难）方程（例如超越数）？

限制

• 实数域（双精度）
• C 语言
• 可配置的近似精度
• 已知间隔搜索
• 拟合值或参数不是严格单调的或者根本不是函数

近似搜索

近似搜索是类似的到二分搜索，但删除了搜索函数、值或参数必须是严格单调函数的限制。尽管有这种放松，它仍保持相同的 O(log(n)) 复杂度。

算法

考虑以下问题：

给定一个已知的函数 y = f(x) 和所需的点 y0，我们的目标是找到 x0 使得 y0 = 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)，计算 y = 之间的距离/误差 ee 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中文网其他相关文章！