3167逃离陷阱

题意:

给出n个点,求出到最近的 给出点 距离最长的点的坐标。

可以通过模拟退火来实现:

先随机出一个点A,再在以A为圆心,以R为半径,随机出一个点B。若ans(B)>ans(A),则用B来更新A。若ans(B)<ans(A),则以一定的概率P(dE) = exp( dE/T )来更新A,其中exp为自然指数,T是一个自己定的数,dE是ans(B)>ans(A)。

在每次随机点B后,R、T都要适当的减小,以便缩小随机范围和结束求解。

简单来说,模拟退火就是以一定的概率接受一个不是最优的解,来跳出之前的最优解,避免把局部最优解当成全局最优解

最后要注意常数T,和随机范围R的选取

继续阅读3167逃离陷阱

[POJ 1379] [CEOI 1999] 逃离陷阱

模拟退火。

概念见大白话解析模拟退火算法

实现:

首先随机在平面中取一个点 A,每轮都以这个点为圆心,R 为半径(每轮递减)随机选取若干个圆上的点 B。若点 B 已经优于 A,则直接用 B 更新 A,否则以一个概率 P(每轮递减)决定是否以 B 更新 A。这样就可以得到一个近似最优解。

在实现过程中,可以同时维护 20 个点,最后取这些点中的最优值作为答案。具体 R 与 P 的初始值与更新方式见代码。

代码如下:

继续阅读[POJ 1379] [CEOI 1999] 逃离陷阱