黄金搜索算法 黄金分割优化算法

描述

黄金搜索算法，黄金分割数是 5 − 1 2 frac{sqrt{5}-1}{2} 25 ​−1​

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

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

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

代码 1. 一维黄金搜索 #include #include // 黄金搜索// 参数意义: 搜索范围最小值，搜索范围最大值，搜索值，允许的误差值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) 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 if (abs(t1 - t0) 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) a = c; } t = (b - a) / gr; c = b - t; d = a + t; } return (a + b) * 0.5;}