三分探索 - 忘れても大丈夫

三分探索 (Ternary search) は 単峰関数の大域最適解 ~~連続関数の極小値~~ を求める反復解法である．次の問題を三分探索で解く．

＊「連続関数の極小値」ではなく「単峰（たんほう）関数の大域最適解」と修正しました．詳細は一番下に書きました．（2020年11月26日修正）

ARC054 B問題. ムーアの法則

現代のコンピュータで答えを求めるのに $P$ 年かかる問題を解きたい．ムーアの法則より， $x$ 年後のコンピュータの計算速度は現在の $2^{x / 1.5}$ 倍高速になる．答えを求めるまでの最短の時間を求めよ．

制約： $0 < P \le 10^{18}$

解法．三分探索

$x$ 年後（ $0 \le x$ ）に計算を初めたときに答えが求まる時間を $f(x)$ とおくと，
　　 $f(x) = x + \frac{P}{2^{x / 1.5}}$
となる．この関数の最小値が答えとなる．

関数 $f(x)$ は凸関数である．なぜならば，線形関数と指数関数は凸関数であり，凸関数の和は凸関数となるからである．したがって，関数 $f$ は凸関数なので極小値と最小値が一致するので一階微分の根が最適解となる．ただし，最適解が負数の場合がありえるので注意が必要である．そのときは， $x$ が 0 のとき最適解となり答えは $P$ となる．

ここからは三分探索を用いて答えを求める．三分探索は二分探索の様に探索範囲を狭めながら最小解を探索するが，分割する領域は二等分ではなく下の図のように三等分で行う．最小解が存在する区間を $[lb, ub]$ とする．この区間を三等分する．このとき， $t_1 = \frac{2 lb + ub}{3}, t_2 = \frac{lb + 2 ub}{3}$ となる．最小解が含まれる場所によって次の探索区間を $[lb, t_2]$ または $[t_1, ub]$ に定める．

　1. 最小解が $[lb, t_1]$ に含まれる（赤色の関数）
　　・判定方法： $f(t_1) \le f(t_2)$ （区間 $[t_1, ub]$ で関数は単調増加している）
　　・次の探索区間： $[lb, t_2]$
　2. 最小解が $[t_2, ub]$ に含まれる（黄色の関数）
　　・判定方法： $f(t_1) \ge f(t_2)$ （区間 $[lb, t_2]$ で関数は単調減少している）
　　・次の探索区間： $[t_1, ub]$
　3. 最小解が $[t_1, t_2]$ に含まれる（青色の関数）
　　・判定方法：なし
　　・次の探索区間： $[lb, t_2]$ または $[t_1, ub]$

青色の関数の場合は1番目と2番目のどちらの次の探索区間にも含まれるので，上の場合分けで必ず正しい最小解の含まれる区間を狭めることが可能である．

　　 f:id:tatanaideyo:20190426034514p:plain

今回の許容解は実数なので境界の判定は適当にしている．初めの探索区間は $[0, P]$ である（ $\because f(0) = P$ ）．また，1回の遷移で区間の大きさが $2 / 3$ になり，答えの絶対誤差または相対誤差の精度は $10^{-8}$ 以下を満たす必要があるので，遷移回数を $k$ とすると，条件を満たす遷移回数は $\left(\frac{2}{3} \right)^k \times 10^{18} \le 10^{-8}$ から $k \ge 148$ となる（200回ぐらい行うと精神的にも安定する）．

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ld = long double;

inline ld f(const ld x, const ld p) {
    return x + p * pow(0.5, x / 1.5);
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    ld p;
    cin >> p;

    ld lb = 0, ub = p;
    for (int i = 0; i < 148; ++i) {
        ld t1 = (2.0 * lb + ub) / 3.0;
        ld t2 = (lb + 2.0 * ub) / 3.0;

        if (f(t1, p) > f(t2, p)) lb = t1;
        else ub = t2;
    }

    cout << setprecision(10) << setiosflags(ios::fixed);
    cout << f(lb, p) << endl;

    return 0;
}

三分探索のメリットとして微分を行わないで済む（解析的に解くのが難しい問題の微分したくなーい）以外にあるのかな．
ちなみに，今回の問題を解析的に解くと $a = 2^{1 / 1.5}$ としたとき，最小解は $\frac{\log P + \log \log a}{\log a}$ で，最小値は $\frac{\log P + \log \log a + 1}{\log a}$ です．

追記：単峰関数とは？

関数 $f \colon \mathbb{R} \to \mathbb{R}$ が単峰関数であるとは，ある $m$ が存在して，定義域が $\left[-\infty, m \right)$ に制限されているとき狭義単調減少，かつ，定義域が $\left( m, +\infty \right]$ に制限されているとき狭義単調増加しているものです．すなわち， $f(m)$ が唯一の大域最小解となります．上の定義は下に凸のようなひとつの峰がある関数の定義をしましたが，上に凸のようなひとつの峰がある関数も単峰関数です．
1変数の単峰関数ならここで紹介した三分探索は大域最適解を求めます．また，狭義凸関数は単峰関数であり，今回紹介した問題は狭義凸関数なので三分探索で最適解を求めることができます．ただし，逆の単峰関数は狭義凸関数ではないので注意が必要です．単峰関数の定義で単調減少や単調増加に狭義であるという制限をしているのは，平らな部分があると大域最適解が見つからない入力を作ることができるからです．あと，大域最適解を求めるために関数の連続性の条件は必要ないと思います．