Irelia

Irelia

逝去的是刀锋,不变的是意志

题解 P3382 【【模板】三分法】

posted on 2019-08-31 15:02:20 | under 题解 |

很多人对模拟退火算法的讲解都说过类似这样的话

为了避免落入局部最优解,我们要随机接受一个更坏的值来跳出局部最优解

然而,区间单峰函数并不存在让人落进去的局部最优解,所以我们引入一个更简单的算法——

爬山算法

算法思想

顾名思义,我们在函数上“爬山”,每次看左右哪边是“上坡”,就往哪边爬一点。代码实现极其简单,思维难度几乎为0

程序实现

// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

int n;
double l, r;
double co[15];

int Rand() {//我们不想随机出一个太大的数,那样每次移动的就太小了
    return rand() % 1000 + 500;
}

double Func(double x) {//暴力计算函数
    double res = 0;
    for (int i = 0; i <= n; i++) {
        double tmp = 1;
        for (int j = 1; j <= i; j++) tmp *= x;
        res += co[i] * tmp;
    }
    return res;
}

double Move(double x, int typ) {//左右移动,0为左1为右,注意是否跨过0
    if (x < 0) {
        if (typ == 1) {
            if (x > -1e-5) x += 1e-5;
            else x *= (1.000000 - 1.000000 / Rand());
        } else {
            x *= (1.000000 + 1.000000 / Rand());
        }
    } else {
        if (typ == 1) {
            x *= (1.000000 + 1.000000 / Rand());
        } else {
            if (x < 1e-5) x -= 1e-5;
            else x *= (1.000000 - 1.000000 / Rand());
        }
    }
    return x;
}

int main() {
    srand(114514);
    cin >> n >> l >> r;
    for (int i = n; i >= 0; i--) cin >> co[i];
    double cur = (l + r) / 2.000000; //随便找个初始开爬的点,强迫症让我选了中点
    double f = Func(cur);
    double f1, f2, nxt1, nxt2, mx = f, mxans = cur;
    for (int i = 1; i <= 100000; i++) {
//      cerr << cur << "\n";
        nxt1 = Move(cur, 0);//尝试左右移动
        nxt2 = Move(cur, 1);
        f1 = Func(nxt1);//计算两种函数值
        f2 = Func(nxt2);
        if (f1 > f) {
            cur = nxt1;
            f = f1;
        } else {
            cur = nxt2;
            f = f2;
        }
        if (f > mx) {//更新最优解
            mx = f;
            mxans = cur;
        }
    }
    cout << fixed << setprecision(5) << mxans << "\n";
    return 0;
}