黄金分割探索
(dp/golden-section-search.hpp)

• View this file on GitHub
• Last update: 2024-03-04 16:48:10+09:00
• Include: #include "dp/golden-section-search.hpp"
• Link: https://twitter.com/noshi91/status/1399003086362865673

Required by

• monge グラフ上の d-辺最短路 (dp/monge-d-edge-shortest-path.hpp)

Verified with

• verify/verify-yuki/yuki-0952.test.cpp

Code

#pragma once

#include <cassert>
#include <functional>
#include <utility>
using namespace std;

// reference：https://twitter.com/noshi91/status/1399003086362865673

namespace golden_section_search_impl {

using i64 = long long;

// [min, max] は閉区間を入力する
template <typename T, bool get_min = true>
pair<i64, T> golden_section_search(const function<T(i64)>& f, i64 min,
                                   i64 max) {
  assert(min <= max);
  i64 a = min - 1, x, b;
  {
    i64 s = 1, t = 2;
    while (t < max - min + 2) swap(s += t, t);
    x = a + t - s, b = a + t;
  }
  T fx = f(x), fy;
  while (a + b != 2 * x) {
    i64 y = a + b - x;
    if (max < y || (fy = f(y), get_min ? fx < fy : fx > fy)) {
      b = a;
      a = y;
    } else {
      a = x;
      x = y;
      fx = fy;
    }
  }
  return {x, fx};
}

}  // namespace golden_section_search_impl

using golden_section_search_impl::golden_section_search;

/*
  @brief 黄金分割探索
*/

#line 2 "dp/golden-section-search.hpp"

#include <cassert>
#include <functional>
#include <utility>
using namespace std;

// reference：https://twitter.com/noshi91/status/1399003086362865673

namespace golden_section_search_impl {

using i64 = long long;

// [min, max] は閉区間を入力する
template <typename T, bool get_min = true>
pair<i64, T> golden_section_search(const function<T(i64)>& f, i64 min,
                                   i64 max) {
  assert(min <= max);
  i64 a = min - 1, x, b;
  {
    i64 s = 1, t = 2;
    while (t < max - min + 2) swap(s += t, t);
    x = a + t - s, b = a + t;
  }
  T fx = f(x), fy;
  while (a + b != 2 * x) {
    i64 y = a + b - x;
    if (max < y || (fy = f(y), get_min ? fx < fy : fx > fy)) {
      b = a;
      a = y;
    } else {
      a = x;
      x = y;
      fx = fy;
    }
  }
  return {x, fx};
}

}  // namespace golden_section_search_impl

using golden_section_search_impl::golden_section_search;

/*
  @brief 黄金分割探索
*/

Back to top page