三項検索
セグメント
[l, r] 上の単峰関数の最大値または最小値を見つけるには、三項検索が必要です。セグメント上に 1 つの極値がある関数は単峰性です。
関数の最大値の検索は、最適化問題でよく使用されます。たとえば、面積が最大になる直角三角形の可能な最大角度を見つける必要があります。これを行うには、
0 から
90 までの角度を通過し、このセグメント上で最初に増加し、次に減少する領域を探します。関数は単峰性になります。
仕組み
動作原理は二分探索と似ていますが、セグメントを半分に分割する場合、セグメントの中央がちょうど極値に当たる場合、および & nbsp; が発生する場合があります。明確な結果は得られません
が。
したがって、このようなケースを避けるためには、セグメントを2つに分割するのではなく、3つに分割し、極値のない部分などを破棄して境界が結果に収束するまで処理する必要があります。
double f( ダブル ハイポ、ダブル アルファ ) {
alpha = (alpha *M_PI)/180;
return 0.5 * ハイポ * ハイポ * cos(アルファ) * sin(アルファ);
}
int main() {
double l = 0;
double r = 90;
倍の EPS = 1e-6;
ダブルハイポ = 100;
while (r - l >=EPS) {
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(hypo, m1)
三項検索は、 黄金分割法、これにより収束率が約2倍に向上します。
ソース
1) 三分探索と黄金比
2) 三項検索