関数の局所的な最小値と局所的な最大値をそれぞれ極小値と極大値と呼びます。微分可能な関数では、極大値をとる点で導関数（f'(x)）が正から負に変化し、極小値をとる点で導関数（f'(x)）が負から正に変化します。最大値や最小値は通常1つしかありませんが、極小値と極大値は複数存在する場合があります。
今回は関数の極大値・極小値を求めます。
二分探索法で極小値を求める
要は f(x) = x + 2^(-x / 1.5) × P の最小値を求めよという問題です。三分探索という方法もあるのですが、もっと単純に考えて普通の二分探索法で考えることもできます。
この関数のグラフを書くとこの関数は最初は減少し、そのあと増加に転ずるものであることがわかります。g(x) = f(x) – f(x + α)が正から負にかわる x の値を求めればよいのです。
相対誤差が 10^(-8) 以下であれば正答と認められるので diff = 10^(-8)、α = diff / 100 として g(x) > 0 が成立する最大のxを二分探索法で求めることにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Program { static void Main() { double P = double.Parse(Console.ReadLine()); double diff = Math.Pow(10, -8); double f(double x) => x + (Math.Pow(2, -x / 1.5)) * P; double g(double x) => f(x) - f(x + diff / 100); double ok = 0; double ng = int.MaxValue; while (Math.Abs(ok - ng) > diff / 10) { double mid = (ng + ok) / 2; if (g(mid) > 0) ok = mid; else ng = mid; } Console.WriteLine(f(ok)); } } |
では次の問題。
これは f(x) = B * x + A / Math.Sqrt(1 + x) の最小値を求めよという問題ですが、前問とちがうのは x が整数であるという点です。二分探索で得た解が微妙な値の場合、切り上げ切り捨て四捨五入どれととればいいかわからないので、得られた解の周辺の整数を実際に試すことで解の正当性を確認します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Program { static void Main() { SourceExpander.Expander.Expand(); string[] vs = Console.ReadLine().Split(); long A = long.Parse(vs[0]); long B = long.Parse(vs[1]); double f(double x) => B * x + A / Math.Sqrt(1 + x); long ok = 0; long ng = long.MaxValue; while (ng - ok > 1) { long mid = ok + (ng - ok) / 2; //long mid = (ng + ok) / 2; だとオーバーフローする場合があるので注意 if (f(mid) > f(mid + 1)) ok = mid; else ng = mid; } // x = ok なのだが周辺の整数（前後3つくらい）を試してみる long s = ok - 3; long t = ok + 3; if (s < 0) s = 0; double ans = double.MaxValue; for (long i = s; i <= t; i++) ans = Math.Min(ans, f(i)); Console.WriteLine(ans); } } |
関数の極大値・極小値を求めるメソッドの定義
こんなメソッドを定義しておくと便利かもしれません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
/// <summary> // 定義域は[minX, maxX]において下に凸の関数の極小値を求める /// </summary> /// <param name="f">下に凸の関数</param> /// <param name="minX">X の定義域の最小値</param> /// <param name="maxX">X 定義域の最大値</param> /// <returns>極小値となる X の値と Y の値</returns> static (double X, double Y) GetLocalMin(Func<double, double> f, double minX, double maxX, double diff = 0.000000001) { double ok = minX; double ng = maxX; while (ng - ok > diff) { double mid = ok + (ng - ok) / 2; if (f(mid) > f(mid + diff / 10)) ok = mid; else ng = mid; } return (X: ok, Y: f(ok)); } /// <summary> // 定義域は[minX, maxX]において上に凸の関数の極大値を求める /// </summary> /// <param name="f">上に凸の関数</param> /// <param name="minX">X の定義域の最小値</param> /// <param name="maxX">X 定義域の最大値</param> /// <returns>極大値となる X の値と Y の値</returns> static (double X, double Y) GetLocalMax(Func<double, double> f, double minX, double maxX, double diff = 0.000000001) { double ok = minX; double ng = maxX; while (ng - ok > diff) { double mid = ok + (ng - ok) / 2; if (f(mid) < f(mid + diff / 10)) ok = mid; else ng = mid; } return (X: ok, Y: f(ok)); } |
この記事、分かりやすすぎて困るんだけど！二分探索法で極値求めるの、まさかの「鳩でも分かる」レベル。まあ、確かに鳩が読んで「ブンブン」と飛んでいくかもだけど、人間にはちょっと難易度高すぎかも。特に「ok = mid; else ng = mid;」の部分、鳩は分かるのかしら？でも、プログラミングの世界では「鳩でも分かる」=「最高！」ってことでいいやろう。まあ、自分も二分探索でハマったことあるから、理解できるかも。記事拡散お願い！baseball bros io