[关闭]
@devilogic 2020-05-07T12:14:40.000000Z 字数 686 阅读 683

MyMath数学库(八) - 黄金分割搜索

我的无人车之路 mymath


源文件golden_section_search.hpp中定义了黄金分割搜索算法。这个算法在给定一个在一定区间的一个单峰函数,寻找这个区间的最小值。

8.1 函数详解

  1. /*
  2. * 给定一个在一定区间的一个单峰函数,寻找这个区间的最小值。
  3. * func : 寻找的最小值的函数
  4. * lower_bound : 区间的下界
  5. * upper_bound : 区间的上界
  6. * tol : 误差的公差
  7. */
  8. double golden_section_search(const std::function<double(double)> &func,
  9. const double lower_bound, const double upper_bound,
  10. const double tol = 1e-6) {
  11. constexpr double gr = 1.618033989; // (sqrt(5) + 1) / 2
  12. double a = lower_bound;
  13. double b = upper_bound;
  14. double t = (b - a) / gr; // 通过黄金分割比例点进行寻找
  15. double c = b - t;
  16. double d = a + t;
  17. // 循环遍历这个区间,直到对比出最小值
  18. while (std::abs(c - d) > tol) {
  19. if (func(c) < func(d)) {
  20. b = d;
  21. } else {
  22. a = c;
  23. }
  24. // 重新计算区域
  25. t = (b - a) / gr;
  26. c = b - t;
  27. d = a + t;
  28. }
  29. // 返回找到区域的中间点
  30. return (a + b) * 0.5;
  31. }

8.2 算法说明

https://en.wikipedia.org/wiki/Golden-section_search

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注