Tag Archives: heuristic

简单粗暴的MM及其他

呃……首先,我标题党了,这里的MM是指Topcoder的Marathon Match,具体来说是刚刚结束的TCO 2009的马拉松比赛第一轮。Topcoder的马拉松赛每场持续一周时间,在这一周之内你可以多次修改并提交程序,系统会实时进行评测并根据题目中说明的计算方法返回得分,同时你也可以看到别人的得分,这一周期间大家都会不停地改进自己的程序,分数会交错上升,与75分钟的算法赛相比是另一种激烈。

本次的题目简单来说就是,在一张W*H (W,H<=500) 的地图上,系统先随机生成15~25个初始点,每个初始点的位置(x,y)和高度z随机得到,另外每个点还有两个随机得到的参数f,w,然后对于地图上其他的点,根据一个公式计算出高度(这个公式与所有初始点的位置、高度、参数都有关,是一个加权平均值),这样就得到一张完整的地形图。但是这个图你是不知道的,所有的参数也都不知道,唯一知道的根据这张地形图生成的等高线图(等高线和极值点处值为1,其余位置为0),但是等高线的真正高度也是未知的。你可以进行若干次测量,每次测量可以得到一个指定点的实际高度(得到的返回值还会有符合高斯分布的随机噪声-_-),测量次数不得超过sqrt(W*H)次。然后你的程序需要把完整地形图输出,程序的得分与每个点的高度与真正高度的差有关,还与测量次数有关。

实际上我估计所有人一看到这题目都有一个直接的想法,就是测量出等高线的高度以后,在两条等高线之间的点实际上就是这两个高度的某种平均值。(根据我们的经验,地形图总是光滑的,要是处处不可导那就囧掉了。)但是我一开始的时候总感觉这个方法简单粗暴、毫无美感,于是就想了一个很yy的方法,首先取得极值点高度,因为极值点必定在初始点(当然还有一些初始点不是极值点,这里简单忽略),于是初始点的x,y,z就知道了,然后再取得等高线的实际高度,这样就得到一个最优化问题,即对每个初始点确定合适的w,f值使得在等高线上的Squared Error之和最小。然后我就想迭代求解,结果发现解不出,大部分情况下根本就不收敛……然后交上去只有零点几分……

然后我就开始简单粗暴了,测出峰值和等高线高度,对每个点取离它最近的两条等高线,按它到等高线的最短距离进行线性插值。然后效果出乎意料地好,交上去有5分多。再然后我发现这个方法对峰值处的处理不太准确,对山峰估计过低,对山谷估计过高,再加了一点修正以后,很轻松拿到了7分多。排名在200名多点,第一轮选300人是肯定能进了。对我这MM赛菜鸟来说这可是很不错的成绩。

感觉这种暴力方法能取得好效果的情况还是很常见的,在实际应用中那些理论很优美实现很精妙的算法往往比不过一个直观的优化,比如KMP vs BM,再比如昨天刚在水木看到的一个问题(cnhawk说百度面他的时候也问过这个),问如何记录下所有用户对所有版面文章的已读和未读状态。一个BBS的注册用户数和文章数都不少,两者相乘的矩阵更是相当庞大,远非一个简单架构能够实现。或者我们会想到把数据压缩等等方法,但实际上大部分BBS的解决方案十分暴力——直接把一段时间以前的文章全部标为已读(查看一下源码或者找一个从来没去过的版面使劲往前翻就可以发现),这个方法看上去蛮横无理,但几乎没有用户抱怨过,甚至很少有人发现有什么不对劲,即便是那些用Term灌水多年的老版油们。

再扯远一点,这种所谓的heuristic往往出于直觉,并总是被理论派所不齿,就像ACM比赛里面一板一眼分析复杂度的学术流都十分bs那些乱搞流一样。但是我想这种直觉在某种程度上是一种更高深的东西,它需要广阔的Domain Knowledge、长期的经验以及敏锐的洞察。当然,我认为heuristic还是只能算作权宜之计,它表明我们需要一个更优美更一般的理论把这种heuristic包容进来(比如用比最坏情况复杂度更精确的方法从理论上刻画BM算法的效率)。

最后扯一句,大家现在都在研究Machine Learning,我希望有一天能够出现Machine Intuition,当计算机也能像我们一样做出这种拍脑袋式的解决方案时,这一定是个有趣的景象……