关于三分法求最大值！

1万 · 2015-9-18 10:07

二分法作为分治中最常见的方法，适用于单调函数，逼近求解某点的值。但当函数是凸性函数时，二分法就无法适用，这时三分法就可以“大显身手”～～
类似二分的定义Left和Right，mid = (Left + Right) / 2，midmid = (mid + Right) / 2; 如果mid靠近极值点，则Right = midmid；否则(即midmid靠近极值点)，则Left = mid;
程序模版如下：

double Calc(Type a)
{
    /* 根据题目的意思计算 */
}
void Solve(void)
{
    double Left, Right;
    double mid, midmid;
    double mid_value, midmid_value;
    Left = MIN; Right = MAX;
    while (Left + EPS < Right)
    {
        mid = (Left + Right) / 2;
        midmid = (mid + Right) / 2;
        mid_area = Calc(mid);
        midmid_area = Calc(midmid);
        // 假设求解最大极值.
        if (mid_area >= midmid_area) Right = midmid;
        else Left = mid;
    }
}

1万 · 2015-9-18 10:08

分析三分法的具体实现
条线段上找到一点，与给定的Ｐ点距离最小。很明显的凸性函数，用三分法来解决。
Calc函数即为求某点到P点的距离。
人左右走动，求影子L的最长长度。
根据图，很容易发现当灯，人的头部和墙角成一条直线时(假设此时人站在A点)，此时的长度是影子全在地上的最长长度。当人再向右走时，影子开始投影到墙上，当人贴着墙，影子长度即为人的高度。所以当人从A点走到墙，函数是先递增再递减，为凸性函数，所以我们可以用三分法来求解。

1万 · 2015-9-18 10:10

下面只给出Calc函数，其他直接套模版即可。
double Calc(double x)
{
return (h * D - H * x) / (D - x) + x;
}
三分法，首先旋转的角度只要在0到180度即可，超过180度跟前面的相同的。坐标轴旋转后，坐标变换为：
X’ = x * cosa - y * sina;
y’ = y * cosa + x * sina;