CodeCraft2016区域复赛与全国决赛回顾

作者: 虾米小华


2016年5月30日,我们从深圳安全返回南京。至此,历时近三个月的2016年Code Craft软件精英挑战赛终于圆满结束。

区域复赛,意料之外的惊喜

5月15日,是江山赛区 (即江苏、山东赛区) 的区域复赛,32支队伍在华为南京研究所开战,只为争夺有资格进军全国总决赛的区域四强席位。我们在复赛前的排位赛位居赛区第7,和其他7支种子队被分在8个不同的小组。

比赛的规则类似足球世界杯。第一轮是小组赛,每个小组前两名晋级第二轮,选出16强;之后是淘汰赛,两两PK,16进8,8进4,以及决出冠亚季军。两队PK是9局5胜制,每支队提供两组case,官方提供5组case。PK时在同一组case上,两支队伍的算法首先比拼的是重合边的数量,重边数越少,结果越优;如果重边数一样,就比cost,cost越小则结果越优;如果cost还一样,那就拼算法的运行时间,运行时间越短的队胜出。运行时间通常是不会出现相等的情况,计算机的计时精确到10ms,出现运行时间相等的概率很低。(然而在全国决赛,就出现了这种情况)那要是运行时间真相等怎么办?看最终版代码的提交时间,提交越早胜出。提交时间总不会在同一秒吧。

比赛开始后,我们在小组位居第二。突然发现自己的算法竟然没解出自己设计的case! 赶紧检查源码,发现提交的是较早版本的代码,好在U盘里有备份最新版本。更新了源码以后,提交,升到了小组第一。此后一直到服务器上传通道关闭,我们基本稳定在小组第一。期间我们在赛场内走动,询问其他小组的算法运行情况,因为我们有两个官方case没解出来。了解到几乎所有的队都没解出官方的最后两个case,只有一个队解出来了官方第四组case。

我们给自己定的目标是进8强。后来下午公布每一轮结果时,看到依次进了16强、8强,也舒缓了一口气:目标达成!但是公布4强时,自己心里还是紧张又期待的。其实挺矛盾,一方面止步8强是一个令自己满意的结果,赶紧结束吧,都花了两个月了,之后就可以忙自己手头的许多事情了;另一方面又抱着一丝希望,因为那样的话就能去深圳了,谁不愿意呢?

南京苏州赛区复赛队伍合影

结果出乎意料——我们真的进了4强。那一刻,我激动地跳了起来,大声欢呼。后来有朋友告诉我,说我那时就像个欣喜若狂的孩子。我自己当时都没意识到,只觉得,那个时刻,世界属于我们。为什么那么激动,因为强队如云,自己从没对4强有过多少期盼,就算没进4强,也能心安理得;进了4强,那就是意料之外的惊喜了。

区域4强的奖励相当丰厚——每人一部华为mate-8手机,加入勇敢星实习计划,以及面试绿卡

南研所集训,强大的后勤支持

复赛结束后,华为南研所召集了赛区四强队伍,进行决赛前为期一周的集训。

集训的主要内容是对算法进行优化,对代码进行重构。一周的时间相当紧迫,重新设计新的算法时间已经不允许,我们能做的就是对目前代码的一些小改进,或者争取能够解出更多的case,适应更多的输入规模和结构。

南研所集训

在集训期间,南研所给我们提供了强大的后勤支持:四星级宾馆、免费的三餐、宽敞的培训场所,以及在学校和研究所之间往返的车费也全部报销。

我们和其他三支队伍建立了良好的友谊,从初赛复赛的竞争关系,到决赛的并肩作战,这是一种很奇妙的感觉。大家都很乐意分享自己的想法,每天在一起调试程序,晚饭后一起围着南研所的天鹅湖散步的时光短暂而快乐。

耐心的帆神,萌而幽默的冬哥,说话慢条斯理的刚哥,平易近人的凯哥,眼中闪耀着智慧之光的圣博哥,颇有“江南水乡”气质的陆晨哥,学霸+科研大神的俊梅姐……嗯,我竟然有机会和他们谈笑风生(因为其他三支队都是研二或研三的学长学姐,所以这里都称呼“哥”“姐”了)。

全国决赛,我们的算法尽力了

5月27~29日,来自全国八大赛区的四强,共32支队伍齐聚深圳,在福田区丽思卡尔顿酒店展开最后的较量。

由于我们使用的核心算法是遗传算法,所以参数的设定非常重要。在比赛前一天晚上,我们写了脚本持续运行算法,以获得较好的参数,好在比赛现场根据结果反馈进行不断调优。到第二天早上,我写的脚本收集了大约300多组参数,另一名队友的脚本收集了500多组参数,这样我们就有足够的参数来调试。我们的算法是随机算法,其缺点是不稳定,虽然收敛的速度还不错,但每次运行的结果都不是确定的,如果想增加稳定性,就得牺牲时间代价。

了解遗传算法的同学应该知道,遗传算法是模拟达尔文生物进化理论的一种智能优化算法,在组合优化领域有着广泛的应用,至今在科学界还保持着相当高的研究热度。遗传算法的主要算子有选择、交叉和变异。而我们在试验中发现,如果加上选择和交叉算子,将大大降低算法的运行效率,根本不可能在赛题要求的10秒钟限制之内给出结果,于是只采用了变异算子,并且把变异概率提升至1.0,变异算子的设计就相当重要。我们摒弃了常用的变异策略,而用一种邻域搜索算法——3-opt来作为变异算子。这种变异算子很有效,而且复杂度是O(n)级的,可以大大提升遗传算法的速度。所以本质上我们的遗传算法并不是通常的遗传算法,而是一种随机化的3-opt邻域搜索算法,试验发现,这种算法的性能非常好,求解中小规模的非对称TSP(Travelling Salesman Problem)能够得到不错的近似解,而且时间复杂度很低。但是随着规模变大,这种算法的性能就会下降。

为了增加遗传算法的稳定性,我在阅读了一些英文文献后,在我们的遗传算法中加入了一个交叉算子——有向DPX(Distance Preserving Crossover)交叉,经过试验,发现可以显著优化结果。但是会降低算法收敛速度。所以必须小心地引入该算子,比如降低它的调用次数,或者在种群进化到适当的时候开始执行。

遗传算法

上面这段代码就是遗传算法的进化函数,我加入的交叉算子被我命名为”make_love”,你可以理解为程序员的恶趣味。写代码不容易,何不幽默一番:P

决赛的规则和区域复赛的一样,先是小组赛,然后是淘汰赛。我们的目标是希望能够小组出线,晋级16强。

决赛开始后,我们就感觉到了比赛的艰难。有一个队完全把我们碾压,毫无还手之力,于是整个比赛的三个小时,我们都在和另外一个队伍争小组第二的出线名额,和他们不断地交替占据第二的位置。但是每提交一次就得等5-6分钟,距离比赛结束还有10分钟左右时,我们提交了最后一版代码,也是我们那时能够获得最好结果的代码。这版代码再次让我们回到小组第二。但是我们已经不再有调参数的时间,也不打算再提交代码,只能寄希望于对手不要反超。然而墨菲定律还是应验了——对手在最后10分钟逼平了比分。

比分相同就看净胜分,最后我们输在了净胜分。

总决赛现场

虽然有遗憾,但是不难过。我觉得我们的算法尽力了。赛后和其他队伍交流,发现我们的算法求解结果也基本是最优解,但是时间就比不上别人了。我们想的是尽可能地利用10s的时间,去求得更好的解,并期望以解的质量战胜对手,区域复赛我们就是这么做的。然而到全国决赛,大家几乎都能解出最优解,在一些case上拼的就是时间。而我们的随机算法在时间上是不占优势的。全国32强的队伍里,也很少有采用随机算法的,基本都是启发式确定算法。

比如,总决赛的冠军“六院八队”的算法是:spfa+指派+LKH(有向3/4/5-opt);比如,粤港澳的区域第一“中原逐鹿”的算法是:一直跑网络流,整形规划最小必经环,和spfa压缩;比如,我们赛区的”dz”,也是总决赛四强,算法是:基于约束Dijkstra压缩的ATSP近似+指派+分支定界;比如,杭厦赛区四强全部用的约束网络流,平均代码量只有500行。

我们的算法是基于约束Dijkstra压缩的ATSP近似+遗传算法(遗传算法的选择并不是最佳的,随机波动比较大)

冠军的代码量有1万+行,而亚军的代码量只有500行左右。

与顶尖高手之间,还有很大差距。

赢了,更加自信;输了,总结经验,看到和别人的差距,然后继续努力。这是我希望自己能够有的心态

巾帼不让须眉

这一小节单独拿出来说,因为很重要。

CodeCraft的赛场再次见证了IT界从来都不是为男孩纸量身定制的。虽然就参赛选手的男女比例而言,男生是占据了绝对优势,但是优秀的队伍中不乏女中豪杰。有图为证:

成渝赛区区域冠军

成渝赛区的区域冠军 “LTZ” (电子科技大学),就有两位女生。(一个队人数不多于3人);

武长赛区四强 (左5-左7为冠军队伍)

总决赛冠军队 “六院八队” (国防科技大学),也有两位女生。

一个队中有一个女生的就更是不胜枚举,她们或作为主力承担算法工程师的职责,或作为辅助协调队内分工合作,或负责后勤保障,肩扛“程序员鼓励师”的艰巨任务。

有男神的队伍所向披靡,有女神的队伍创造奇迹

深圳之行,梦幻般的体验

另外值得一提的是深圳之行,说它是一场梦幻般的体验并不为过。

第一次坐飞机。 第一次去深圳。 第一次住五星级酒店。 第一次吃海鲜自助。各种零食水果随便吃。 第一次参观华为总部。 …… 而所有的这些,全部由本次竞赛的主办方提供。

当然,最珍贵的,还是见识了那么多非常牛叉的同学,结交了很多志同道合的朋友。他们来自全国8个赛区,各大高校。

深圳

深圳之旅,感受的是梦幻,尝到的有苦涩,看到的是差距,收获的是友谊,增加的是动力。

对华为的再认识

参加比赛这两个多月时间的所见所闻,重塑了我之前对华为的许多认识和偏见。

社会上讨论最广泛的,就是华为的加班文化。在南研所的那段时间,我也算见证了加班现象的普遍。比如,华为员工每个月的最后一个周末是要上班的;比如,每天晚餐后,许多华为员工还是像上自习一样回到自己的工作岗位;比如,加班到晚上10点以后是家常便饭。

但是这样是否就意味着华为在压榨员工的血汗,以从中攫取剩余劳动力?我对此不置可否。至少我了解到的是,在华为,一个员工的付出,通常都能得到与之相应的回报,是“一分耕耘,一分收获”的形态。任何企业都要面临残酷的竞争、谋求生存,华为作为一家民营企业,能发展成现在的规模,是非常不容易的。华为给我的感觉,如果用三个词概括就是:专注实干、开拓进取、居安思危。

也许,许多人的理想工作状态是,每天朝九晚五,有双休,不加班,带薪休假,work-balance很舒适,还能年薪20万+奖金20万+分红20万……这当然是一种很好的工作状态。但是要知道,企业面临竞争,求职亦如是,自己没有竞争力,凭什么要求高薪?许多人误解了这种工作状态,他们内心想的其实是:不用辛苦工作,也能财务自由。没有人会轻轻松松就能实现财务自由,包括“精英阶层”。在我所了解的优秀的人中,不论是“大神”,还是“女神”;不论是本科毕业就加入Google总部的算法大牛,还是研二就发表多篇顶级会议论文的科研学霸,没有一个是不努力的,他们都是热爱自己所做,目标明确,并且愿意为了实现目标而能够(在很长一段时间内)克服人性弱点的人

一向在媒体面前行事低调的华为总裁任正非最近亮相央视,说的一番话朴素无华而充满力量:

……中国现在又冒出来很多企业,其实也跟华为一样,也是专心致志做一件事的。一个人一辈子能做成一件事,已经很不简单了。为什么?中国13亿人民,我们这几个把豆腐磨好,磨成好豆腐;你那几个企业好好去发豆芽,把豆芽做好;我们13亿人每个人做好一件事,拼起来我们就是伟大祖国……

致谢

参加2016年Code Craft,我们有幸从11409支队伍中脱颖而出,一路从线上初赛走到区域复赛,再到最后的总决赛,从春季到夏季,拥有了难忘的经历,收获远远大于付出。在这里,我想借用冠军队的其中一位女生说的话,沾沾喜气,同时来表达感谢。

首先,感谢我的队友。我从队友那里学到了很多。如果没有他们,我绝不可能在这场比赛中一路走到最后。

其次,感谢华为。华为举办的这个比赛,为我们提供了一个展示自己的舞台,给我们的生活添了一分精彩。

最后,感谢这个时代。这个时代是信息的时代,是计算机的时代。我为选择了和计算机、信息相关的专业而感到自豪,也想把自己的青春挥洒在这片土地上。

Code Craft,再见!

-----EOF-----

Categories: 随笔 Tags: 算法 寻路 华为 CodeCraft