新・アルゴリズムとデータ構造入門 Java編15:黄金分割探索

import java.util.function.Function;
import java.lang.Math;

public class Main {
    static double phi = (1 + Math.sqrt(5)) / 2;

    static double goldenSectionSearch(double l_init, double r_init, double precision,
            Function<Double, Double> f) {
        // 初期化
        double l = l_init;
        double r = r_init;
        double m1 = (l + (phi - 1) * r) / phi;
        double m2 = ((phi - 1) * l + r) / phi;
        double f_m1 = f.apply(m1);
        double f_m2 = f.apply(m2);

        // 終了条件まで繰り返し
        while (r - l > precision) {
            // 更新
            if (f_m1 < f_m2) {
                r = m2;
                m2 = m1;
                f_m2 = f_m1;
                m1 = (l + (phi - 1) * r) / phi;
                f_m1 = f.apply(m1);
            } else {
                l = m1;
                m1 = m2;
                f_m1 = f_m2;
                m2 = ((phi - 1) * l + r) / phi;
                f_m2 = f.apply(m2);
            }
        }
        return r;
    };

    static double f(double x) {
        return (x - 2) * (x - 2) + 3;
    }


    public static void main(String[] args) {
        double x = goldenSectionSearch(-100, 100, 0.0001, Main::f);
        System.out.printf("%.3f\n", f(x));
    }
}

import java.util.function.Function;
import java.lang.Math;

public class Main {
    static double phi = (1 + Math.sqrt(5)) / 2;

    static double goldenSectionSearch(double l_init, double r_init, double precision,
            Function<Double, Double> f) {
        // 初期化
        double l = l_init;
        double r = r_init;
        double m1 = (l + (phi - 1) * r) / phi;
        double m2 = ((phi - 1) * l + r) / phi;
        double f_m1 = f.apply(m1);
        double f_m2 = f.apply(m2);

        // 終了条件まで繰り返し
        while (r - l > precision) {
            // 更新
            if (f_m1 < f_m2) {
                r = m2;
                m2 = m1;
                f_m2 = f_m1;
                m1 = (l + (phi - 1) * r) / phi;
                f_m1 = f.apply(m1);
            } else {
                l = m1;
                m1 = m2;
                f_m1 = f_m2;
                m2 = ((phi - 1) * l + r) / phi;
                f_m2 = f.apply(m2);
            }
        }
        return r;
    };

    static double f(double x) {
        return (x - 2) * (x - 2) + 3;
    }


    public static void main(String[] args) {
        double x = goldenSectionSearch(-100, 100, 0.0001, Main::f);
        System.out.printf("%.3f\n", f(x));
    }
}

import java.util.function.Function;
import java.util.Scanner;
import java.lang.Math;

public class Main {
	static double phi = (1 + Math.sqrt(5)) / 2;

	static double ternarySearch(double l_init, double r_init, double precision,
			Function<Double, Double> f) {
		double l = l_init;
		double r = r_init;

		while (r - l > precision) {
			double m1 = (l * 2 + r) / 3;
			double m2 = (l + r * 2) / 3;

			if (f.apply(m1) < f.apply(m2)) {
				r = m2;
			} else {
				l = m1;
			}
		}
		return r;
	}

	static int count = 0;
	static int a, b, c;

	static double f(double x) {
		count++;
		return a * x * x + b * x + c;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();

		double x = ternarySearch(-100, 100, 0.0001, Main::f);
		System.out.printf("%.3f\n", f(x));
		System.err.println(count);
	}
}

import java.util.function.Function;
import java.util.Scanner;
import java.lang.Math;

public class Main {
	static double phi = (1 + Math.sqrt(5)) / 2;

	static double ternarySearch(double l_init, double r_init, double precision,
			Function<Double, Double> f) {
		double l = l_init;
		double r = r_init;

		while (r - l > precision) {
			double m1 = (l * 2 + r) / 3;
			double m2 = (l + r * 2) / 3;

			if (f.apply(m1) < f.apply(m2)) {
				r = m2;
			} else {
				l = m1;
			}
		}
		return r;
	}

	static int count = 0;
	static int a, b, c;

	static double f(double x) {
		count++;
		return a * x * x + b * x + c;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();

		double x = ternarySearch(-100, 100, 0.0001, Main::f);
		System.out.printf("%.3f\n", f(x));
		System.err.println(count);
	}
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「黄金分割探索による高速化」

右側のコードエリアには、ある関数の最小値を求める三分探索プログラムが実装されています。
このコードを黄金分割探索に変えて、より高速に計算するプログラムを作成してみましょう。
なお、このコードでは実行時エラーのところに関数の呼び出し回数が出力されるようにしてあります。
また、この演習課題はデフォルトコードでも正解になりますが、より高速に計算するプログラムを作成した場合でも正解になるように取り組んでみてください。

入力される値

7 1 3

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

2.964

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃04:黄金分割探索

このチャプターでは、三分探索をより高速におこなう黄金分割探索について学習します。

黄金分割

・黄金比 φ = (1 + √5) / 2 = 1.6180339887...
・この φ を用いて、φ : 1 : φ の比率で区間を分割することを黄金分割という
・区間 l, r に対する左側の分割点: m1 = (l + (φ - 1) × r) / φ
・区間 l, r に対する右側の分割点: m2 = ((φ - 1) × l + r) / φ
・黄金比を用いることで、以下のように分割点を使いまわすことができる
・■□□□□□□□□□□■□□□□□□■□□□□□□□□□□□■
・↓
・■□□□□□□■□□□■□□□□□□■
・↓
・■□□□■□□■□□□■

黄金分割を使って関数 f の最小値を探索するアルゴリズム

・ l, r, m1, m2, f_m1, f_m2 を初期化
・ m1, m2 ← l と r の黄金分割点, f_m1, f_m2 ← f(m1), f(m2)
・
・探索範囲が小さくなるまで以下の処理を繰り返す
・
・ 1. f_m1 < f_m2 の場合
・ 1.1 右側の区間を削除する: r ← m2, m2 ← m1, f_m2 ← f_m1
・ 1.2 新しい分割点 m1 を求める: m1 ← 左分割点, f_m1 ← f(m1)
・
・ 2. f_m1 ≧ f_m2 の場合
・ 2.1 左側の区間を削除する: l ← m1, m1 ← m2, f_m1 ← f_m2
・ 2.2 新しい分割点 m2 を求める: m2 ← 右分割点, f_m2 ← f(m2)

プログラミング学習 > Java > 新・アルゴリズムとデータ構造入門 Java編 > 新・アルゴリズムとデータ構造入門 Java編15: 二分探索関連アルゴリズム・三分探索 > 黄金分割探索

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：

7 1 3