CWYAlpha

Just another WordPress.com site

Thought this was cool: TopCoder Asia-Pacific 2012 解题思路

leave a comment »


上月偶然看到网上有提到TopCoder Asia-Pacific 2012,比赛形式为马拉松,题目和传感器定位问题有些类似。因为我今年比较忙,没报名KDD CUP,也没报名TCO,GCJ,这次感觉应该有时间把这个题目做完,就尝试了一下。
题目在此 http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15137&pm=11942
题目大致是说有$n (100 \le n \le 2000)$ 个10维空间上的点,每一维坐标从[0, 1000]的整数中随机选取。对于每一个点,你知道到它最近和最远的点的距离,也知道其他点到这个点距离的远近排序。每个点的每个维度都有一定概率已知,需要算出不知道的维度。
这题明显是需要一个全局优化算法,于是需要构造一个目标函数,关键也就在这里了。
假设n个点记为$x_1, x_2, … , x_n $,对每个点$x_i$,定义集合$$N(i)=\{ j : \text{if the distance between } x_i\text{ and }x_j\text{ is known} \} $$
所以一个目标是 $$\min. f_1=\sum_{i=1}^n \sum_{j \in N(i) } | d(x_i, x_j) – d_{ij} | $$
这里$d(x_i, x_j)$表示算出的两点间的距离,$d_{ij}$表示已知的实际距离。
另外还需要利用距离排序,对于点$x_i$,记$o(i,j)$为到他距离排在第$j$位的点的编号,则这部分的目标为$$\min. f_2= \sum_{i=1}^n \sum_{j=2}^{n} | d(x_i, x_{o(i,j)}) – d(x_i, x_{o(i,j-1)}) |$$
可以看到这部分目标实质上是将两个排序相邻的距离拉近。这个目标是可以保证在解处达到最优的,因为如果满足排序关系,那么必有$$ \sum_{j=2}^{n} | d(x_i, x_{o(i,j)}) – d(x_i, x_{o(i,j-1)}) | = d(x_i, x_{o(i,n)}) – d(x_i, x_{o(i,1)}) $$
等号右端是个已知的定值,如果不满足排序关系,那么上述等式应该变为大于。
于是我们可以用$f_1$和$f_2$加权求和作为总的目标函数。
算法的总框架是模拟退火。每次循环遍历所有点的每个分量。让一个分量随机取一个新的值时,计算目标函数是否有改进,以一定的概率保留新值。
刚开始的时候每个分量的选取范围都可以很大,但是随着迭代进行,应当逐渐缩小选取范围。因为距离太远的值基本上都不会好。
模拟退火温度的选取、温度的变化、分量随机选取范围的缩小速度,这些都是需要调整的参数。选取得好能保证$ 200 < n < 400$的时候基本都能求到最优。
对于n大的情况,每次计算目标函数太费时间。可以选取目标函数的一部分进行计算。比如$$f_2= \sum_{i=1}^n \sum_{j=s}^{t} | d(x_i, x_{o(i,j)}) – d(x_i, x_{o(i,j-1)}) |$$
这里s和t都是参数,可以适当的选取使得计算时间不太多,但是也能反应目标的改进。
如果一个点到其他点的已知距离都已经满足的情况下,就暂时不修改这个点的位置了,这是一个贪心思想的改进,在快搜到解的时候很有用。
另外在模拟退火过程中,由于每次只尝试修改一个点的一个分量,所以可以动态维护任意两点间的距离,代价不太大。
但是对于$n<200$,尤其是$n<120$的情况,可能是因为局部最优点太多,总是会搜到一个还可以的解,但是搜不到最优解。我想可能还需要进行一个局部搜索。除了ACRush以外似乎其他人这部分算的都不好。

from Dora Blog: http://diaorui.net/?p=279

Written by cwyalpha

六月 6, 2012 在 4:12 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: