Cómo funciona la búsqueda de aproximación

búsqueda de aproximación

Esto es una analogía con la búsqueda binaria, pero sin sus restricciones de que la función/valor/parámetro buscado debe ser una función estrictamente monótona y al mismo tiempo compartir la O(log(n))complejidad.

Por ejemplo, supongamos el siguiente problema.

Hemos conocido la función y=f(x)y queremos encontrar x0tal que y0=f(x0). Esto se puede hacer básicamente mediante una función inversa, fpero hay muchas funciones que no sabemos cómo calcularla inversamente. Entonces, ¿cómo calcular esto en tal caso?

sabe

• y=f(x)- función de entrada
• y0- yvalor del punto deseado
• a0,a1- xrango de intervalo de solución

Desconocidos

• x0- el valor del punto deseado xdebe estar dentro del rangox0=<a0,a1>

Algoritmo

1. Sondee algunos puntos x(i)=<a0,a1>uniformemente dispersos a lo largo del rango con algún paso.da

   Así por ejemplo x(i)=a0+i*dadondei={ 0,1,2,3... }

2. para cada uno x(i)calcular la distancia/error eedely=f(x(i))

   Esto se puede calcular, por ejemplo, de esta manera: ee=fabs(f(x(i))-y0)pero también se puede utilizar cualquier otra métrica.

3. recordar el punto aa=x(i)con distancia/error mínimoee

4. detenerse cuandox(i)>a1

5. aumentar recursivamente la precisión

   así que primero restrinja el rango para buscar solo alrededor de la solución encontrada, por ejemplo:

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

   luego aumente la precisión de la búsqueda reduciendo el paso de búsqueda:

   da'=0.1*da;
   

   si da'no es demasiado pequeño o si no se alcanza el número máximo de recursiones, vaya al n.° 1

6. la solución encontrada está enaa

Esto es lo que tengo en mente:

En el lado izquierdo se ilustra la búsqueda inicial (puntos #1,#2,#3,#4 ). En el lado derecho, la siguiente búsqueda recursiva (viñeta n.° 5 ). Esto se repetirá de forma recursiva hasta alcanzar la precisión deseada (número de recursiones). Cada recursión aumenta los 10tiempos de precisión ( 0.1*da). Las líneas verticales grises representan x(i)puntos sondeados.

Aquí el código fuente C++ para esto:

//---------------------------------------------------------------------------
//--- 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
//---------------------------------------------------------------------------

Así es como se usa:

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
    }

en el rem de arriba for (aa.init(...está el operando nombrado. Es a0,a1el intervalo en el que se x(i)prueba, daes el paso inicial entre x(i)y nes el número de recursiones. entonces si n=6y da=0.1el error de ajuste máximo final xserá ~0.1/10^6=0.0000001. Es &eeun puntero a la variable donde se calculará el error real. Elijo el puntero para que no haya colisiones al anidar esto y también para la velocidad, ya que pasar un parámetro a una función muy utilizada crea un montón de basura.

[notas]

Esta búsqueda de aproximación se puede anidar en cualquier dimensionalidad (pero, en general, hay que tener cuidado con la velocidad). Vea algunos ejemplos.

• Aproximación de n puntos a la curva con mejor ajuste
• Ajuste de curva con puntos y en posiciones x repetidas (brazos Galaxy Spiral)
• Aumento de la precisión de la solución de la ecuación trascendental.
• Encuentre una elipse de área mínima que encierre un conjunto de puntos en C ++
• 2D TDoA Diferencia horaria de llegada
• Diferencia horaria de llegada 3D TDoA

En caso de que no se ajuste la función y sea necesario obtener "todas" las soluciones, puede utilizar la subdivisión recursiva del intervalo de búsqueda después de encontrar la solución para buscar otra solución. Ver ejemplo:

• Dada una coordenada X, ¿cómo calculo la coordenada Y de un punto para que descanse sobre una curva de Bézier?

¿Qué debes tener en cuenta?

hay que elegir cuidadosamente el intervalo de búsqueda <a0,a1>para que contenga la solución pero no sea demasiado amplio (o sería lento). Además, el paso inicial daes muy importante, si es demasiado grande, se pueden perder las soluciones locales mínimas y máximas o, si es demasiado pequeño, el proceso se volverá demasiado lento (especialmente para ajustes multidimensionales anidados).

Mar 22 '2016 19:03 Spektre