退火流程:
$1.$由上一次接受的解$pre$出发,随机得到一个可能解$x$。
$2.$若当前解优于最优解$ans$,覆盖最优解。
$3.$否则$x$将会以$exp(delta/T)$的概率成为下一次的$pre$。
$4.T*\Delta$降温。
$\Theta(???)$
“一般降温系数 $\Delta$ 与 $1$ 的差减少一个数量级, 耗时大约多 $10$ 倍;$T_0$和$T_k$变化一个数量级, 耗时不会变化很大。”
$by\;M$_$sea$
实现细节
$1.$降温系数取$[0.95,0.997]$左右。
$2.$如何生成新解?
坐标系内:随机生成一个点,或者生成一个向量。
序列问题:$random\;shuffle$ 或者随机交换两个数。
网格问题:可以看做二维序列,每次交换两个格子即可。
$by\;M$_$sea$
$3.$如果想多跑几次….
1 | MAX_TIME = 0.7~0.8 |
实测$P1337[JSOI2004]$平衡点 / 吊打$XXX$评测记录 $0.6->TLE$
$4.WA?$
不同的$\Delta$、$T_0$、$T_k$甚至$srand()$和$SA$的次数都会影响到答案。
$by\;M$_$sea$
$About:srand()$
你可以这样写:
$srand((unsigned)time(NULL))/srand(19260817)$
再$srand(rand())$几次。
例题
$P1337[JSOI2004]$平衡点 / 吊打$XXX$
$1.$势能的计算:$len*w$($len:$绳在桌面上的长度)
原理:绳子总长不变,$len$越大,物体越高。
$2.$横纵坐标的增量:$((rand() << 1) - RAND$_$MAX) * T$
$((rand() << 1) - RAND$$MAX)$得到介于$[-RAND$ $MAX,RAND$ _ $MAX-1]$之间的随机数。
1 |
|