近似搜索如何工作

Question

[序幕]

这个Q&A旨在更清楚地解释我在这里首次发表的近似搜索类的内部工作

• 提高超越方程解的精度

我已经被要求提供关于这几次的更多详细信息(由于各种原因)所以我决定写关于这个的Q&A风格主题,我将来可以很容易地参考这个主题并且不需要一遍又一遍地解释它.

[题]

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

限制

• 真实域名(double精确)
• C++语言
• 可配置的近似精度
• 已知的搜索间隔
• 拟合值/参数不是严格单调的或根本不起作用

Answer 1

近似搜索

这类似于二分搜索,但没有其限制,搜索的函数/值/参数必须是严格单调的函数,同时共享O(n.log(n))复杂性.

例如,假设以下问题

我们已经知道了功能,y=f(x)并希望找到x0这样的功能y0=f(x0).这基本上可以通过反函数来完成,f但是有许多函数我们不知道如何计算它的逆.那么在这种情况下如何计算呢？

的已知,

• y=f(x) - 输入功能
• y0- 想要的点y值
• a0,a1- 解决方案x间隔范围

未知数

• x0- 想要的点x值必须在范围内x0=<a0,a1>

算法

1. x(i)=<a0,a1>通过一些步骤探测沿着该范围均匀分散的一些点da

   所以例如x(i)=a0+i*da在哪里i={ 0,1,2,3... }

2. 为每个x(i)计算的距离/错误ee的y=f(x(i))

   这可以像这样计算: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

这就是我的想法:

在左侧是图示的初始搜索(子弹#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是指针变量,其中实际的错误将被计算.我选择指针,因此在嵌套时没有碰撞.

[笔记]

这种近似搜索可以嵌套到任何维度(但是粗略的,你需要注意速度)参见一些例子

• n点与最佳拟合曲线的近似
• 重复x位置上的y点曲线拟合(Galaxy螺旋臂)
• 提高超越方程解的精度
• 查找包含c ++中一组点的最小区域椭圆

在非功能适合的情况下以及需要获得"全部"解决方案的情况下,您可以在找到解决方案后检查其他解决方案时使用搜索间隔的递归细分.见例子:

• 给定一个X坐标,如何计算一个点的Y坐标,使其依赖于Bezier曲线

你应该注意什么？

你必须仔细选择搜索间隔,<a0,a1>因此它包含解决方案,但不是太宽(或者它会很慢).初始步骤da非常重要,如果它太大,你可能会错过本地最小/最大解决方案,或者如果太小,那么事情将变得太慢(特别是对于嵌套的多维拟合).