题解 P2210 【Haywire】

Ciyang · 2018-10-29 16:44:41 · 题解

此题一眼就看出是模拟退火模板题,写个模板就过了...

题目分析与思路:

此题要设置 N 个牛的位置,使每个牛与他的3个朋友的距离之和最小,并且 N 个牛的位置是 1 - N ,那么很容易想到,模拟退火中交换两个牛的位置,并随温度的大小,几率接受较差的排列方式就行了. 如果不知道模拟退火是什么,可以自行看一下百科

如果还不懂,我的凭自己的能力解释(瞎搞)一下:

先放张一次模拟退火过程的示意图(来自wikipedia)

此动态图片就是搜索最优解(最大函数值),在开始时先随便设置一个 X 坐标,计算函数值 Y ,设为当前最优解.
毕竟算法名为模拟退火,顾名思义,那么起始的温度一定很高(~~不然怎么退火~~),所以每次搜索时 X 坐标的增大或减少量变化很大.认真观察这幅图片上温度值较高时的 X 坐标变化量,会发现波动很大.
在每次改变 X 坐标后,就计算函数值 Y 坐标,称作当前解.如果当前解比最优解大,就更新最优解.如果当前解不如最优解,那么就会以一定几率接受.这样才会跳出当前当前最优解,才可能找到更优解.
几率接受的几率是个很玄学的问题,通常情况,设当前温度为 T ,当前解为 k ,最优解为 K_{max} ,我们通常用这样一个玄学公式...

exp((k-kmax)/T)<(double)rand()/RAND_MAX

我当初也不知道exp的意义何在,后来发现太妙了!如果不知道exp是啥,可以自己看一下百科,我稍作解释: exp函数在X < 0时, Y 一定为 0 - 1 之间的小数且单调递增,(double)rand()/RAND_MAX也是一个 0 - 1 之间的小数.这样温度越小,接受当前较差解的几率越低.

模拟退火最重要的三个参数,起始温度,终止温度,温度变化速度

这三个需要自己设置,起着改变准确率,精度,时间复杂度,较差解接受几率的作用,但这个题比较水,随便设置的差不多就能过

理解了模拟退火,就可以开始写这道题了.

这道题是找最小值,也是一样的思路.只需要写一个用来求当前的建造线路所需要的干草堆的函数和模拟退火过程函数.然后一直搜,多跑几次模拟退火全过程就行了

代码实现:

评测详情

Accepted 100

用时: 1903ms / 内存: 848KB

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <queue>
#include <map>
#include <limits.h>
using namespace std;
namespace Ciyang {
    struct q_instream {
        template < typename classT >
        inline q_instream operator>>(classT &e) const {
            e= 0;
            classT f= 1, c= 0;
            while(c < '0' || c > '9') {
                if(c == '-') f= -1;
                c= getchar();
            }
            while(c >= '0' && c <= '9') e= e * 10 + c - '0', c= getchar();
            return e= e * f, (*this);
        }
    } qin;
    //读入优化
    struct q_outstream {
        template < typename classT >
        inline q_outstream operator<<(const classT &e) const {
            if(e < 0) {
                putchar('-');
                (*this) << -e;
            }
            else {
                if(e > 9) (*this) << (e / 10);
                putchar(e % 10 + '0');
            }
            return (*this);
        }
        inline q_outstream operator<<(const char &c) const {
            return putchar(c), (*this);
        }
    } qout;
    //输出优化
}  // namespace Ciyang
using namespace Ciyang;
//前面全部为读入输出优化
int n, f[13][3], pos[13], best_ans= INT_MAX;
template < typename T >
T absi(T a) {
//求绝对值函数,也可以用自带的abs.
    return a > 0 ? a : -a;
}
int get_cost() {
//求需要干草堆数量的函数
    int tmp_ans= 0;
    for(int i= 1; i <= n; i++) {
        for(int j= 0; j < 3; j++) {
            tmp_ans+= absi(pos[i] - pos[f[i][j]]);
            //每个牛与三个朋友的坐标差的绝对值相加
        }
    }
    return tmp_ans;
    //得出当前解
}
const double BeginT= 10000, EndT= 1e-12, ChangeT= 0.99;
//起始温度,终止温度,温度改变速度
void SA(int times) {
//模拟退火过程
    int x, y, tmp_ans;
    while(times--) {
        for(double T= BeginT; T > EndT; T*= ChangeT) {
            do {
                x= rand() % n + 1;
                y= rand() % n + 1;
            } while(x == y);
            swap(pos[x], pos[y]);
            //任意交换两个牛的位置
            tmp_ans= get_cost();
            //求出当前解
            if(tmp_ans <= best_ans) {
                best_ans= tmp_ans;
                //更优就更新答案
            }
            else if(exp((best_ans - tmp_ans) / T) > (double)rand() / RAND_MAX) {
            //条不接收较差的条件
                swap(pos[x], pos[y]);
                //不接受较差解,将两个牛位置交换回去
            }
        }
    }
    return;
}
int main() {
    srand(time(0));
    //随机种子,看人品
    qin >> n;
    for(int i= 1; i <= n; i++) {
        for(int j= 0; j < 3; j++) {
            qin >> f[i][j];
        }
        pos[i]= i;
        //设置每个牛的初始坐标就是自己的编号
    }
    SA(275);
    qout << best_ans / 2 << '\n';
    //计算时每两个牛的距离都算了都两遍
    return 0;
}