我们学校有个很不错的历史传统,就是五一三天假会有一个大型的娱乐项目,“数模三天乐”,简直把人爽得不行不行的。一般地说是“自愿报名”,但是苦逼的数学系出身还有各种各样的原因吧,最终还是不得不报名打一把数模。

数模和ACM是两个完全不同的竞赛。从过程上和准备上讲,数模对于大家来说都是三天决定结果,但是ACM就不是5个小时的发挥决定结果了,毫不夸张地说,数模三天,ACM三年。从结果展现来讲,数模是论文优劣定胜负。可能你的成果或者你的答案和评委们手上的“最佳答案”有些出入,但是你的思维,你的想法往往是最核心的。大部分的数模题目多是些复杂难搞的多元的非线性的分析题,如何分析问题,如何取舍参数,如何的去评估算法往往是最重要的,答案和结论并不是主旋律。但是ACM的评判标准只有一个:“AC”&“WA”。你再怎么高效的算法,你个人能力再怎么强,没有AC,就是失败。可以讲,ACM是残酷的,哪怕你日日刷题夜夜分析也不能确保在赛场上AC。但ACM又是幸运的,它是客观反映你的数据问题处理能力的一场测试,罚时时间就是评分标准。

既然是两个不同的竞赛,考量的是不同的方面,那就不要再一次又一次的评论这两个竞赛的优劣好坏了。

4月30日 - 题目发布

题目出来之后,因为当时队友就在宿舍,所以直接就把题目发给我了。和去年的类型一样:一个是图论问题,一个是数据统计;一个是公共自行车调度问题,一个是预计CPI指数。理解题意之后,我们就开始了选题分析。A题是图论题,建模难度中档,编程难度中档,但是写作压力很大:要把一个问题解释清楚并不是那么容易,而且还是一个比较复杂的车辆分配调度问题。B题数据统计题,主要难点在于建模,也就是对一大坨商品的单独与综合的分析,编程难度几乎为0,写作的压力也不是很大。然后就到了短板取舍了。因为我们的建模都是渣渣一样的水平,又不好意思直接选个B题让建模大人灰常愉快的自娱自乐,所以我们在晚上7点就确定了A题作为我们这次的题目。

随后就是对题目的详尽分析过程。这里我们就出现了一两个分歧:

1、选曼哈顿距离还是欧氏距离?因为这是一个在城市里的图的模型,所以我们觉得似乎直接让车子穿墙穿楼不大合适而且十分不现实。所以我们自始自终都是用了曼哈顿距离,虽然带来了很多麻烦(主要还是编程的你妹的。。。),但是最后都克服了。 2、是在一个调度时间内(90分钟)不停地有自行车还入借出,还是只考虑一个时间段只有一次还入借车行为。这个分歧很大。因为题目中并没有明确说明,我们也没法去正确的理解题意。大概就是说,因为考虑到自行车速和每次自行车最多走2公里的原因,所以我们一开始以为是10分钟一拍。简单的讲,就是到底是10分钟发生一次还车借车行为,还是90分钟发生一次还车借车行为。这个分歧在第二天看到数据之后才被解决。

分歧归分歧,我们那天晚上的成果还是很多的:

1、计算了节点距离(曼哈顿距离)。因为是经纬度之间的距离计算,直接带公式编程计算就完成了,毫无难度可言。毕竟自己的编码量那么多而且公式又是现成的。 2、计算了一次借车还车行为中,每个节点还车的数量。这个无非是待定系数先求概率,然后直接假设期望就是还车辆。但是这个时候就有了一个插曲,概率是小于1的非负数,所以期望有可能就不是整数,这就导致了第一个人为误差。不同的小组不同的分析方法都有可能导致这个地方出现问题。

再有就是及时的整理思路并且写出需求。在写了几次小工程之后我越发地体会到如果你只是一个单纯的ACM算法程序员,并不能够很好的和队友们交互。因为我们需要的是标准的输入输出格式,但是很多时候现实不是这样。所以及时的写出需求,列出函数接口清单,保持大框架的清晰至关重要。对于函数方法中的代码,一定要做到头脑清晰。不要轻易地上手编程(当然排序什么的还是可以直接上手的,这里讲的是稍稍复杂,或者稍稍现实一点的函数方法),可以先写出算法,然后构思数据储存方案,最后上手编写。因为数模这个东西工作量大,工作时间长,如何时刻保持高效至关重要。及时的整理思路,保持大脑的清醒,事半功倍。当然效果也是非常明显的,这次的编程需求基本上都保证了大程序45 - 60分钟出结果,小的程序(修饰输入输出数据之类的那种)15 - 30分钟出结果,基本保证了实时满足建模数据需要。

5月1号 - 受挫不断

实在想不到比“受挫不断”更好的词汇了。题意和数据都显示,我们的10分钟一拍的想法太天真烂漫了,这样搞的话调度车完全就停不下来了。而且我们发现更蛋疼的是那个装卸自行车的时间竟然是1分钟1辆,哎,你们又在逗我,摆个自行车至于那么慢?搞得调度中完全是这个时间占了最大的比重。sad。

之后又到了逗比的初始数据生成环节,太TM逗了,完全停不下来有木有!有的节点只进不出,有的节点只出不进。一开始我们想放弃一些节点,通过实现给足量的方式,后来失败了。然后我们又考虑可以一部分节点调度,另外一部分什么多一辆少一辆的那种就可以暂时不调动,结果发现根本没有这种善良的节点,全是尼玛的丧心病狂的“来12辆车,我这里没有了。”“多了22辆,没地放车了亲!“”请组织再给我来10辆。”一群<BEEP!>,sad。

最后天才的用了一个迭代法去通过一个初始解,也就是种子,来生成并且优化解,竟然奇迹般的做到了,而且还比富帅君的答案还要小。不过这就是第二天的事情了。

一开始我们以为,真的是以为,可以撸掉第一问,结果,失败了,失败西马西大。。。

5月2号 5月3号 - 连轴转

到中午的时候,终于把初始的那个迭代出来的可能也许大概陷入局部最优的解算了出来。之后就开始纠结路径的选取。我还是太天真烂漫了,我以为找到一个环路就可以了,结果好多因素要考虑:

1、终点必须是需要补给的节点,起点必须是需要拉走自行车的节点。因为一个路上车的数量有限,不可能无中生有,更可能最后这辆车“满载而归”。 2、运输车上的自行车不能有多于50辆。题目条件。 3、路径选取不能无中生有,只能考虑真实的道路。 4、为什么不留一些车作为备份车?因为总量是不变的,看上去你留了一些车让前几次的调度量少了一些,但是实际上总调度量是不变的,所以只是挖东墙补西墙而已。

然后我就苦逼了,不会写程序只好人工启发式搜索啊=。=花了一个下午才搞定了。嗯星爷帮我们订餐时还特地多买了好多米,那个晚餐我吃了四份大米,嗯,胃口好,胃口好。

当然我在干活的时候建模大人也没闲着,他几乎是独立完成了第二问的选点方案,也是非常的叼。这就是分工优势了。因为我们都是至少掌握两门技能的,所以完全可以自己去独立的搞,在队友实在是抽不出时间的情况下。所以我们组到晚上12点的时候,第一问第二问同时撸通。

然后我们就在舍友的带领下,愉快的看起了舌尖上的中国=。=

然后就饿了Orzing。。。

但是更苦逼的不是饿了,因为边看《舌尖》边啃面包,饥饿症状缓解了不少,但是因为这个“没有程序,只有路径的选取算法”的情况让我着实反胃。。。所以五十多个节点的全新的路径选取又成了我一个人的手算时间。。。而且你懂的因为到了凌晨三四点,而且一天没有休息,注意力不集中,中间因为少记录了一个点的状态发现少了一辆车就疯了一样的开始“找你妹”,也是异常的丧心病狂。而且因为预估不足,原本以为能够4辆车完成的任务结果发现有一个图尽全力搜出来的结果最慢的一辆调度车时间消耗156min,多了6min,然后我当时就疯了你知道那种感觉吗!结果工作量又被无端的人为放大。从凌晨2点开始到中午10点,8个小时终于搜索完了路径,并且写好了路径表。终于,5月3号上午10点11分,我放假了,关掉QQ,开始闭门休息=。=

总结

不管你承认与否,团队的作用永远比一个人要强得多。并不是因为我的编程能力好一点就能比你们算得快,而是因为每次金大大让我算个东西前,他总能不厌其烦地听我问一个又一个的问题,直到我整理好思路;并不是金大大的建模方案就一定好,而是因为他的建模过程能够转述给小孙孙从而让小孙孙写出论文;并不是小孙孙文笔多么生动形象,而是因为我们都是尽力的在整理和排布着论文中的段落、表格、图片的展示顺序,追求更好的可读性。团队永远是最高的,所以不论做什么事,都要考虑团队,而不是考虑自己个人。

当然,个人的能力也同样很重要。毕竟不能指望啥都不会的人写出一点有建树的东西。但是如果自己的能力都不能满足团队需求的话那就最好不要去批评指责队友。列计划,写需求,时刻保持高效,这是我对我自己的要求。当然以后在其他方面,我也同样尽力做到。

好了扯犊子完了,跑步去了。