题目链接：[ HDU - 2899 ]

题目大意：

函数 F(x) = 6x7 + 8x6 + 7x3 + 5x2 - yx, 其中x的范围是0 ≤ x ≤ 100.
输入y值，输出F(x)的最小值

模拟退火算法

模拟退火就是类似于物体降温的概率，来进行多次搜索迭代

在迭代过程中，模拟退火算法随机选择下一个状态，有两种可能

  1. 新状态比原来状态更优，那么接受这个新状态
  2. 新状态更差，那么以一定的概率接受该状态，不过这个概率应该随着时间的推移逐渐降低

模拟退火算法的主要步骤如下：

  1. 设置一个初始的温度T
  2. 温度下降，状态转移。从当前温度按降温系数下降到下一个温度，在新的温度计算当前状态
  3. 如果温度降到设定的温度下界，程序停止

伪代码

eps = 1e-8;              // 终止温度，接近0，用于控制精度
T = 100;                 // 初始温度，应该是高温，以100℃为例
delta = 0.98;            // 降温系数，控制退火的快慢，小于1，以0.98为例
g(x);                    // 状态x时的评价函数，例如物理意义上的能量
now, next;               // 当前状态和新状态
while (T > eps) {                   // 如果温度未降到eps
    g(next), g(now);                // 计算能量
    dE = g(next) - g(now);          // 能量差
    if (dE >= 0)                    // 新状态更优， 接受新状态
        now = next;
    else if (exp(dE / T) > rand())  // 如果新状态更差，在一定概率下接受他，e^(dE/T)
        now = next;
    T *= delta;                     // 降温，退火过程模拟
}

常见问题

模拟退火算法在ACM中的典型问题有函数最值问题、TSP旅行商问题、最小圆覆盖、最小球覆盖等

题解代码

#include<bits/stdc++.h>
using namespace std;

const double eps = 1e-8;    // 终止温度

double y;
double func(double x)   // 计算函数值
{
    return 6 * pow(x, 7.0) + 8 * pow(x, 6.0) + 7 * pow(x, 3.0) + 5 * pow(x, 2.0) - y * x;
}

double solve(void)
{
    double T = 100;         // 初始温度
    double delta = 0.98;    // 降温系数
    double x = 50.0;        // x的初始值
    double now = func(x);   // 计算初始函数值
    double ans = now;       // 返回值
    while (T > eps) {
        int f[2] = {1, -1};
        double newx = x + f[rand() % 2] * T;    // 按概率改变x，随t的降温而减少
        if (newx >= 0 && newx <= 100) {
            double next = func(newx);
            ans = min(ans, next);
            if (now - next > eps) {
                x = newx;
                now = next;
            }
        }
        T *= delta;
    }
    return ans;
}

int main(void)
{
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%lf", &y);
        printf("%.4lf\n", solve());
    }
    return 0;
}