近似搜索的工作原理

How approximation search works(近似搜索的工作原理)

问题描述

[序言]

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

• 左侧是图示的初始搜索(项目符号#1、#2、#3、#4).在右侧下一个递归搜索(bullet #5).这将递归循环，直到达到所需的精度(递归次数).每次递归都会将准确度提高 10 倍 (0.1*da).灰色垂直线代表探测的 x(i) 点.

  这里是 C++ 源代码:

  //----------------------------------------------------------------------------//--- 大约版本:1.01 ------------------------------------------------------//---------------------------------------------------------------------------#ifndef _approx_h#define _approx_h#include <math.h>//---------------------------------------------------------------------------类约{民众:双 a,aa,a0,a1,da,*e,e0;int i,n;布尔完成，停止；近似(){a=0.0;aa=0.0;a0=0.0;a1=1.0；da=0.1;e=空；e0=空；我=0;n=5；完成=真；}近似(近似& a){ *this = a;}〜约(){}approx* operator = (const approx *a) { *this=*a;返回这个；}//approx* operator = (const approx &a) { ...copy... return this;}void init(double _a0,double _a1,double _da,int _n,double *_e){如果 (_a0<=_a1) { a0=_a0;a1=_a1;}否则 { a0=_a1;a1=_a0;}da=fabs(_da);n =_n ;e =_e ;e0=-1.0;我=0;a=a0;aa=a0;完成=假；停止=假；}无效步骤(){if ((e0<0.0)||(e0>*e)) { e0=*e;aa=a;}//更好的解决方案if (stop)//提高准确度{我++;如果(i>=n){完成=真；a=aa;返回;}//最终解决方案a0=aa-fabs(da);a1=aa+fabs(da);a=a0;da*=0.1;a0+=da;a1-=da;停止=假；}别的{a+=da;如果 (a>a1) { a=a1;停止=真；}//下一点}}};//---------------------------------------------------------------------------#万一//---------------------------------------------------------------------------

  使用方法如下:

  大约 aa;双 ee,x,y,x0,y0=here_your_known_value;//a0, a1, da,n, eefor (aa.init(0.0,10.0,0.1,6,&ee); !aa.done; aa.step()){x = aa.a;//这是 x(i)y = f(x)//这里计算任何你想要拟合的 y 值ee = fabs(y-y0);//计算近似搜索解的误差}

  在上面的rem for (aa.init(... 是命名的操作数.a0,a1 是x(i) 被探测，da 是 x(i) 之间的初始步骤，n 是递归次数.所以如果 n=6 and da=0.1 x 拟合的最终最大误差为 ~0.1/10^6=0.0000001>. &ee 是指向将计算实际错误的变量的指针.我选择指针，因此在嵌套时不会发生冲突，并且为了提高速度，因为将参数传递给大量使用的函数会造成堆垃圾.

  [注释]

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

  • 最适合曲线的 n 个点的近似值
  • 在重复的 x 位置(银河螺旋臂)上使用 y 点进行曲线拟合
  • 提高超越方程求解的精度
  • 在 C++ 中求包围一组点的最小面积椭圆
  • 2D TDoA 到达时间差
  • 3D TDoA 到达时间差

  在非功能拟合和需要获取全部"的情况下您可以在找到解决方案后使用搜索间隔的递归细分来检查另一个解决方案.见示例:

  • 给定一个 X 坐标，我如何计算一个点的 Y 坐标，使其位于贝塞尔曲线上

  您应该注意什么?

  您必须仔细选择搜索间隔 以便它包含解决方案但不要太宽(否则会很慢).此外，初始步骤 da 非常重要，如果它太大您可能会错过局部最小/最大解决方案，或者如果太小则会变得太慢(特别是对于嵌套的多维拟合).

  [Prologue]

  This Q&A is meant to explain more clearly the inner working of my approximations search class which I first published here

  • Increasing accuracy of solution of transcendental equation

  I was requested for more detailed info about this few times already (for various reasons) so I decided to write Q&A style topic about this which I can easily reference in the future and do not need to explain it over and over again.

  [Question]

  How to approximate values/parameters in Real domain (double) to achieve fitting of polynomials,parametric functions or solve (difficult) equations (like transcendental) ?

  Restrictions

  • real domain (double precision)
  • C++ language
  • configurable precision of approximation
  • known interval for search
  • fitted value/parameter is not strictly monotonic or not function at all
  解决方案

  Approximation search

  This is analogy to binary search but without its restrictions that searched function/value/parameter must be strictly monotonic function while sharing the O(log(n)) complexity.

  For example Let assume following problem

  We have known function y=f(x) and want to find x0 such that y0=f(x0). This can be basically done by inverse function to f but there are many functions that we do not know how to compute inverse to it. So how to compute this in such case?

  knowns

  • y=f(x) - input function
  • y0 - wanted point y value
  • a0,a1 - solution x interval range

  Unknowns

  • x0 - wanted point x value must be in range x0=<a0,a1>

  Algorithm

  1. probe some points x(i)=<a0,a1> evenly dispersed along the range with some step da

     So for example x(i)=a0+i*da where i={ 0,1,2,3... }

  2. for each x(i) compute the distance/error ee of the y=f(x(i))

     This can be computed for example like this: ee=fabs(f(x(i))-y0) but any other metrics can be used too.

  3. remember point aa=x(i) with minimal distance/error ee

  4. stop when x(i)>a1

  5. recursively increase accuracy

     so first restrict the range to search only around found solution for example:

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

     then increase precision of search by lowering search step:

     da'=0.1*da;
     

     if da' is not too small or if max recursions count is not reached then go to #1

  6. found solution is in aa

  This is what I have in mind:

  On the left side is the initial search illustrated (bullets #1,#2,#3,#4). On the right side next recursive search (bullet #5). This will recursively loop until desired accuracy is reached (number of recursions). Each recursion increase the accuracy 10 times (0.1*da). The gray vertical lines represent probed x(i) points.

  Here the C++ source code for this:

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

  This is how to use it:

  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
      }
  

  in the rem above for (aa.init(... are the operand named. The a0,a1 is the interval on which the x(i) is probed, da is initial step between x(i) and n is the number of recursions. so if n=6 and da=0.1 the final max error of x fit will be ~0.1/10^6=0.0000001. The &ee is pointer to variable where the actual error will be computed. I choose pointer so there are not collisions when nesting this and also for speed as passing parameter to heavily used function creates heap trashing.

  [notes]

  This approximation search can be nested to any dimensionality (but of coarse you need to be careful about the speed) see some examples

  • 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

  In case of non-function fit and the need of getting "all" the solutions you can use recursive subdivision of search interval after solution found to check for another solution. See example:

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

  What you should be aware of?

  you have to carefully choose the search interval <a0,a1> so it contains the solution but is not too wide (or it would be slow). Also initial step da is very important if it is too big you can miss local min/max solutions or if too small the thing will got too slow (especially for nested multidimensional fits).

  这篇关于近似搜索的工作原理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！