随机化算法

模拟退火

模拟退火玄学算法,解万能最值问题。
例题

#include <cmath>
#include <iostream>
using namespace std;
const double eps = 1e-8;
double L, W;
double f(double x) { return (L - 2 * x) * (W - 2 * x) * x; }
int cas;
void solve() {
    double T = min(L, W) - 0;
    double delta = 0.99;
    double x = T / 2;
    double now = f(x);
    double ans = now;
    double r = min(L, W) / 2;
    while (T > eps) {
        int m[2] = {1, -1};
        double newx = x + m[rand() % 2] * T;

        if (newx > 0 && newx < r) {
            double next = f(newx);
            ans = max(next, ans);
            if (now - next < -eps) {
                x = newx;
                now = next;
            }
        }
        T *= delta;
    }
    printf("Case %d: %.9f\n",++cas, ans);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> L >> W;
        solve();
    }
}
上一篇:八数码问题


下一篇:二解NOIP普及组2017年T3棋盘