Golden section search
(algorithm/golden_section_search.hpp)

• View this file on GitHub
• Last update: 2023-12-28 15:52:36+09:00
• Include: #include "algorithm/golden_section_search.hpp"
• Link: https://x.com/noshi91/status/1399003086362865673

説明

整数範囲で、黄金分割探索を行う。

golden_section_search(f, min, max, compare)

凸な関数 $f$ に対して、 $[min, max]$ で黄金分割探索をして最小値を求める。compareに比較関数を与えることで最大値を求めることもできる。 $O(\log (\max - \min))$

Depends on

• template/int_alias.hpp

Required by

• Monge d-edge shortest path (algorithm/monge_d_edge_shortest_path.hpp)

Code

#pragma once

#include <cassert>
#include <concepts>
#include <functional>
#include <utility>

#include "../template/int_alias.hpp"

namespace ebi {

// ref: https://x.com/noshi91/status/1399003086362865673
template <std::integral S, class F,
          class T = decltype(std::declval<F>()(std::declval<S>())),
          class Compare = std::less<T>>
std::pair<S, T> golden_section_search(F f, S min, S max,
                                      const Compare &compare = Compare()) {
    assert(min <= max);
    S a = min - 1, x, b;
    {
        S s = 1, t = 2;
        while (t < max - min + 2) {
            std::swap(s += t, t);
        }
        x = a + t - s;
        b = a + t;
    }
    T fx = f(x), fy;
    while (a + b != 2 * x) {
        S y = a + b - x;
        if (max < y || compare(fx, (fy = f(y)))) {
            b = a;
            a = y;
        } else {
            a = x;
            x = y;
            fx = fy;
        }
    }
    return {x, fx};
}

}  // namespace ebi

#line 2 "algorithm/golden_section_search.hpp"

#include <cassert>
#include <concepts>
#include <functional>
#include <utility>

#line 2 "template/int_alias.hpp"

#include <cstdint>

namespace ebi {

using ld = long double;
using std::size_t;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

}  // namespace ebi
#line 9 "algorithm/golden_section_search.hpp"

namespace ebi {

// ref: https://x.com/noshi91/status/1399003086362865673
template <std::integral S, class F,
          class T = decltype(std::declval<F>()(std::declval<S>())),
          class Compare = std::less<T>>
std::pair<S, T> golden_section_search(F f, S min, S max,
                                      const Compare &compare = Compare()) {
    assert(min <= max);
    S a = min - 1, x, b;
    {
        S s = 1, t = 2;
        while (t < max - min + 2) {
            std::swap(s += t, t);
        }
        x = a + t - s;
        b = a + t;
    }
    T fx = f(x), fy;
    while (a + b != 2 * x) {
        S y = a + b - x;
        if (max < y || compare(fx, (fy = f(y)))) {
            b = a;
            a = y;
        } else {
            a = x;
            x = y;
            fx = fy;
        }
    }
    return {x, fx};
}

}  // namespace ebi

Back to top page