AC. 梦想

frank_c1

[BZOJ 3680] 吊打XXX

发布于2016年03月19日 | 暂无评论 | 661阅读 | 启发式搜索,模拟退火

题意简述

给定平面上n个点的坐标(1 \le n \le 10000),每个点有一个权值w_i。求一个点s,使W = \sum_{i=1}^{n} {w_i dist(s,p[i])}最小。其中dist(a,b)为点a,b的欧几里得距离。(由于题目描述过于神奇,仅简述题意)

题目解析

经常听别人说模拟退火各种神奇,今天算是见识了。

这道题是求广义费马点,粗看好像并没有什么现成的好的方法。那我们就来搜索吧。当然暴力搜索是不可行的,我们考虑一些启发式搜索。这里采用模拟退火,采用的策略如下:

1.选定一个点s作为初始解。

2.当温度T大于边界值时,随机调整s的坐标得到s',调整参数为T(即温度越低,调整幅度越小,越稳定)。

3.若新解s'优于s,当前解变为s';否则,以exp(dE/T)的概率接受s'作为当前解(即温度越低,接受较劣解的概率越低,越稳定),转2。

最后,再对答案进行微调。即将坐标小幅移动,以提高答案的精度。

有一个问题:为什么上述算法要以一定的概率接受较劣的解呢?一直向更优解移动不是更好吗?但是,这样做很有可能让算法陷入局部最优解的泥潭,而得不到全局最优解。以一定的概率接受较劣的解,就为打破局部最优解,寻找全局最优解创造了条件。同时,接受较劣解的概率随时间变化而降低,是因为在逐步退火的过程中,答案渐渐趋于稳定。