描述

黄金搜索算法，黄金分割数是$\frac{\sqrt{5}-1}{2}$

挺简单的一个小算法，算法原理简要说一下：

1. 假设我们要在范围[a, b]内寻找距离c最近的一个点。
2. 由于黄金分割率的特性$\frac{1}{1+\frac{\sqrt{5}-1}{2}}=\frac{\sqrt{5}-1}{2}$
3. 我们把 $b-a$ 的差算是1份，0.618份可以算出两个值，c= b-0.618(b-a)，d=a+0.618(b-a),
4. 接下来看一下，c和d哪一个距离c更近，c更近的话搜索范围从[a, b]变为[a, d]，d更近的话搜索范围从[a, b]变为[c, b]。之后继续迭代进行

多提一句，查了一下别人的分析。要速度选二分法，要寻找更优的极值点选黄金分割法 。感兴趣的自行学习，不多赘述

代码

1. 一维黄金搜索

#include <iostream>
#include <math.h>
// 黄金搜索
// 参数意义: 搜索范围最小值，搜索范围最大值，搜索值，允许的误差值
double goldenSectionSearch(double min, double max, double value, double tol) 
{
    double gr = (sqrt(5) + 1) / 2; // 1.618033989

    double lower_bound = min;
    double upper_bound = max;
    double a = lower_bound;
    double b = upper_bound;

    double t = (b - a) / gr;
    double c = b - t;
    double d = a + t;

    while (abs(c - d) > tol) 
    {
        if ( abs(c-value)< abs(d-value)) 
        {
            b = d;
        } 
        else 
        {
            a = c;
        }
        t = (b - a) / gr;
        c = b - t;
        d = a + t;
    }
    return (a + b) * 0.5;
}


int main()
{ 
    double nearest_value = goldenSectionSearch1(1, 8, 3, 0.001); // 搜索范围最小值，搜索范围最大值，搜索值，允许的误差值
    std::cout<<"closet point of 3 in [1,8] : "<<nearest_value<<std::endl;

    return 1;
}

2. 黄金搜索用于路径点搜索

这部分代码只能说，赐予有缘人了哈哈
算法思路来源于apollo代码，我自己重新总结了一下。只看这段代码应该只能说，知道黄金搜索算法在二维路径点的搜索上可以使用。具体的不介绍

typedef struct PathPoint
{
    double x; // 在地图上slam返回的x
    double y; // 在地图上slam返回的y
    double theta; // 在地图上slam返回的theta
    double s; // 在frenet轨迹上的s
    double d; // 在frenet轨迹上的d
    double kappa; // 在frenet轨迹上的弧度kappa
    
}PathPoint;
// 距离插值
double lerp(double x0, double t0, double x1, double t1, double t) 
{
    if (abs(t1 - t0) <= 1.0e-6) 
    {
    return x0;
    }
    double r = (t - t0) / (t1 - t0);
    double x = x0 + r * (x1 - x0);
    return x;
}

double dist_square(PathPoint &p0, PathPoint &p1, double s, double x, double y)
{
    double px = lerp(p0.x, p0.s, p1.x, p1.s, s);
    double py = lerp(p0.y, p0.s, p1.y, p1.s, s);
    double dx = px - x;
    double dy = py - y;
    return dx * dx + dy * dy;
}
// 黄金搜索
double goldenSectionSearch(PathPoint &p0, PathPoint &p1, double x, double y) 
{
    double tol = 0.1;

    double gr = (sqrt(5) + 1) / 2; // 1.618033989

    double lower_bound = p0.s;
    double upper_bound = p1.s;
    double a = lower_bound;
    double b = upper_bound;

    double t = (b - a) / gr;
    double c = b - t;
    double d = a + t;

    while (abs(c - d) > tol) 
    {
        if (dist_square(p0, p1, c, x, y) < dist_square(p0, p1, d, x, y)) 
        {
            b = d;
        } 
        else 
        {
            a = c;
        }
        t = (b - a) / gr;
        c = b - t;
        d = a + t;
    }
    return (a + b) * 0.5;
}