c++ - 近似搜索的工作原理

Question

【序言】

此 问答 旨在更清楚地解释我在此处首次发布的近似搜索类的内部工作

Increasing accuracy of solution of transcendental equation

已经有几次要求我提供关于这方面的更详细信息(出于各种原因)，所以我决定写 问答 关于这个的风格主题，我以后可以很容易地引用，不需要一遍又一遍地解释。

[问题]

如何在实域 ( double) 中近似值/参数以实现多项式、参数函数的拟合或求解(困难的)方程(如超越方程)？

限制

真实域(double 精度)

C++ 语言

近似值的可配置精度

已知搜索间隔

拟合值/参数不是严格单调的或根本没有函数

Answer 1

近似搜索
这类似于二分搜索，但没有限制搜索的函数/值/参数必须是严格的单调函数，同时共享 O(log(n))复杂。
例如假设以下问题
我们已知函数 y=f(x)并想找 x0使得 y0=f(x0) .这基本上可以通过反函数来完成 f但是有很多函数我们不知道如何计算它的逆函数。那么在这种情况下如何计算呢？
已知

y=f(x) - 输入函数

y0 - 通缉点y值(value)

a0,a1 - 解决方案 x区间范围

未知数

x0 - 通缉点x值必须在 x0=<a0,a1> 范围内

算法

探查一些点 x(i)=<a0,a1>沿着范围均匀地分散一些步骤 da
例如 x(i)=a0+i*da哪里i={ 0,1,2,3... }

每个x(i)计算距离/误差 ee的y=f(x(i))
例如，这可以像这样计算:ee=fabs(f(x(i))-y0)但也可以使用任何其他指标。

记住点 aa=x(i)距离/误差最小ee

停止时 x(i)>a1

递归提高精度
所以首先限制范围只搜索找到的解决方案，例如:

a0'=aa-da;
a1'=aa+da;

然后通过降低搜索步长来提高搜索精度:

da'=0.1*da;

如果 da'不是太小，或者如果未达到最大递归计数，则转到 #1

找到的解决方案在 aa

这就是我的想法:

左侧是图示的初始搜索(项目符号 #1,#2,#3,#4 )。在右侧下一个递归搜索(项目符号 #5 )。这将递归循环，直到达到所需的精度(递归次数)。每次递归都会增加准确度 10次 ( 0.1*da )。灰色竖线代表探测到的 x(i)点。
这里的 C++ 源代码:

//---------------------------------------------------------------------------
//--- approx ver: 1.01 ------------------------------------------------------
//---------------------------------------------------------------------------
#ifndef _approx_h
#define _approx_h
#include <math.h>
//---------------------------------------------------------------------------
class approx
    {
public:
    double a,aa,a0,a1,da,*e,e0;
    int i,n;
    bool done,stop;

    approx()            { a=0.0; aa=0.0; a0=0.0; a1=1.0; da=0.1; e=NULL; e0=NULL; i=0; n=5; done=true; }
    approx(approx& a)   { *this=a; }
    ~approx()           {}
    approx* operator = (const approx *a) { *this=*a; return this; }
    //approx* operator = (const approx &a) { ...copy... return this; }

    void init(double _a0,double _a1,double _da,int _n,double *_e)
        {
        if (_a0<=_a1) { a0=_a0; a1=_a1; }
        else          { a0=_a1; a1=_a0; }
        da=fabs(_da);
        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)                                       // increase accuracy
            {
            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
            }
        }
    };
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

这是如何使用它:

approx aa;
double ee,x,y,x0,y0=here_your_known_value;
//            a0,  a1, da,n, ee  
for (aa.init(0.0,10.0,0.1,6,&ee); !aa.done; aa.step())
    {
    x = aa.a;        // this is x(i)
    y = f(x)         // here compute the y value for whatever you want to fit
    ee = fabs(y-y0); // compute error of solution for the approximation search
    }

在上面的 rem for (aa.init(...是命名的操作数。 a0,a1是 x(i) 的区间被探测到， da是 x(i) 之间的初始步骤和 n是递归次数。所以如果 n=6和 da=0.1 x 的最终最大误差合身将是 ~0.1/10^6=0.0000001 . &ee是指向将计算实际错误的变量的指针。我选择指针，因此在嵌套它时不会发生冲突，并且由于将参数传递给大量使用的函数会造成堆垃圾，因此速度也是如此。
【备注】
这种近似搜索可以嵌套到任何维度(但粗略的你需要注意速度)看一些例子

Approximation of n points to the curve with the best fit

Curve fitting with y points on repeated x positions (Galaxy Spiral arms)

Increasing accuracy of solution of transcendental equation

Find Minimum area ellipse enclosing a set of points in c++

2D TDoA Time Difference of Arrival

3D TDoA Time Difference of Arrival

在非函数拟合和需要获得“所有”解决方案的情况下，您可以在找到解决方案后使用搜索间隔的递归 segmentation 来检查另一个解决方案。见示例:

Given an X co-ordinate, how do I calculate the Y co-ordinate for a point so that it rests on a Bezier Curve

你应该注意什么？
您必须仔细选择搜索间隔 <a0,a1>所以它包含解决方案但不是太宽(否则会很慢)。也是初始步骤 da非常重要，如果它太大，您可能会错过局部最小/最大解决方案，或者如果太小，事情会变得太慢(特别是对于嵌套的多维拟合)。