19.三分

发表于 更新于 分类于 ，

三分

三分是一种用于求解单峰/单谷函数极值的搜索算法，通过每次将区间分成三份并比较两个分点的函数值来缩小搜索范围。

对于一个单峰函数，在区间 \([l,r]\) 上有唯一的极大值点。可以取两个三分点：

  • \(mid1 = l + \frac{r-l}{3}\)
  • \(mid2 = r - \frac{r-l}{3}\)

比较 \(f(mid1)\) 和 \(f(mid2)\) 的大小:

  • 如果 \(f(mid1) < f(mid2)\)，说明极大值点在 \([mid1,r]\) 区间内，令 \(l = mid1\)
  • 如果 \(f(mid1) > f(mid2)\)，说明极大值点在 \([l,mid2]\) 区间内，令 \(r = mid2\)
  • 如果 \(f(mid1) = f(mid2)\)，说明极大值点在 \([mid1,mid2]\) 区间内，令 \(l = mid1, r = mid2\)

每次迭代可以将区间长度缩小为原来的 \(\frac{2}{3}\)。

对于单谷函数，只需要将比较符号反向即可求出极小值点。

三分的基本框架如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 三分求单峰函数极大值点
double TrisectionMax(double l, double r) {
    double mid1, mid2;
    for(int i = 0; i < 100; i ++) {
        mid1 = l + (r - l) / 3;
        mid2 = r - (r - l) / 3;
        if(f(mid1) < f(mid2)) l = mid1;
        else r = mid2;
    }
    return l;
}

// 三分求单谷函数极小值点
double TrisectionMin(double l, double r) {
    double mid1, mid2;
    for(int i = 0; i < 100; i ++) {
        mid1 = l + (r - l) / 3;
        mid2 = r - (r - l) / 3;
        if(f(mid1) > f(mid2)) l = mid1;
        else r = mid2;
    }
    return l;
}

示例

例：三分|函数

给定 \(n\) 个二次函数 \(f_1(x), f_2(x), \ldots, f_n(x)\)（均形如 \(ax^2 + bx + c\)），设 \(F(x) = \max\{f_1(x), f_2(x), \ldots, f_n(x)\}\)，求 \(F(x)\) 在区间 \([0, 1000]\) 上的最小值。

输入

1
2
3
4
5
6
2
1
2 0 0
2
2 0 0
2 -4 2

输出

1
2
0.0000
0.5000

分析：都是朝上的二次函数，画画图可以发现，两个口朝上的单峰函数取较大函数值叠加，仍然是口朝上的单峰函数，那么无数个叠加也仍然是，可以用三分求极值。

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
#include<cstdio>
#include<algorithm>

const int maxn = 1e4 + 10;

int n;

struct Func {
    double a, b, c;
    double calc(double x) {
        return a * x * x + b * x + c;
    }
} f[maxn];

double F(double x) {
    double ret = f[0].calc(x);
    for(int i = 1; i < n; i++)
        ret = std::max(ret, f[i].calc(x));
    return ret;
}

double TrisectionMin(double l, double r) {
    double mid1, mid2;
    for(int i = 0; i < 100; i ++) {
        mid1 = l + (r - l) / 3;
        mid2 = r - (r - l) / 3;
        if(F(mid1) > F(mid2)) l = mid1;
        else r = mid2;
    }
    return l;
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%lf%lf%lf", &f[i].a, &f[i].b, &f[i].c);
            
        printf("%.4f\n", F(TrisectionMin(0, 1000)));
    }
    return 0;
}