2019华为软件精英挑战赛总结

Hello大家好，2019华为软件精英挑战赛于4.13复赛结束，我们的旅程也到此为止。复赛开始前，我们一直调侃自己是“摸鱼大队”，对进决赛并不抱太大的希望，但是当复赛结果出来时，心中还是难免失望。这里，首先还是要再次再次感谢我的两个队友，对这个比赛他们的确付出了很多。

我们是西北赛区的“心有多大路就有多宽”，初赛第28复赛第18。今年软件精英挑战赛提高了赛题难度的同时降低了奖励，赛区前32只能拿到笔试绿卡，赛区前4才能拿到面试绿卡，相比之前前32都可以拿到面试绿卡来说确实奖励严重缩水，算是没赶上好时候吧，想想去年的话这不就面试绿卡到手了吗，哈哈哈。不过也理解华为公司的这种做法，毕竟划水的人不在少数。下面进入正题：

本届赛题

今年的赛题是车辆调度问题，详细赛题信息请点击赛题，官方给出Car、Cross、Road三类信息，Cross和Road是交通网络，包含路口和道路的连接信息和道路的详细信息，参赛者需要根据交通网络让Car中的车以最快的速度全部从各自出发点到达终点。具体的行车规则官方用了27页的任务书说明，所以今年的赛题理解有多变态可想而知，我记得直到复赛的最后一天，比赛群里还是有不少人在问行车规则，还有很多人在赛题出来时就被27页的文档劝退了，所以我们都调侃这是一届阅读理解大赛。我的资源分别打包了赛题说明和初复赛数据包，需要者自取。

关于比赛

First

拿到赛题后首先需要做的就是好好理解赛题，这个过程需要做一些可视化之类的辅助理解。车需要尽快到达其终点，很容易想到需要找到车的最短路径，由于道路中不存在负权，我们采用的最短路径算法是Dijkstra算法。关于发车刚开始我们也没有好的思路，所以就按部就班地采用一辆一辆跑的思路做出了第一版提交代码，主要目的是跑通系统测试代码。这个过程可以在赛题发布但未开启提交的时间进行，所以系统开启提交代码后，我们很快上传成功有了最初的成绩，这个策略当然是最差了，调度时间50w+。

Second

一辆一辆跑对道路的利用当然是很差的，所以我们逐渐增加同时间发车数目，然后考虑到车速、车的计划消耗时间的影响，对车辆以车速为第一优先级以车的计划消耗时间为第二优先级进行了排序，并且由于官方允许对其发布的两张地图分别调参，所以设置了两组参数来提高线上成绩。在不死锁的条件下以这种方式发车，经过疯狂调参，线上成绩达到了1300+，这个时候我们也到了一个瓶颈。

Third

这时候有群里的大佬开源了一个线上线下结果有细微差距的可视化判题器，利用这个判题器，我们发现了我们输出的结果对道路的利用还是很差，有的路口车太多、有的道路比较差却走了很多车，所以我们对路口和道路进行了稀疏，即对路口和道路上的车进行统计，如果超出一定范围，则对范围外的车重新规划路线。对路口的规划起到了挺大的作用，对道路的规划却导致车的路线过于分散而出现容易死锁的情况。之后，为了解决道路的问题，对道路进行了重新分配权重，公式如下：

len_weight =length*30/((speedlim+15)*rwidth);

对道路重新分配权重也起到了不错的效果，最后成绩来到了900+。经过初赛正式赛的一番挣扎，总算勉强苟进复赛。

Fourth

复赛中，由于Car中增加了优先车以及预置车，发现在预置车没有发完的情况下容易死锁，然后针对预置车发完的时间点对预置车发完前和发完后进行了分开调参。因为这时候我们已经写出了准确的判题器，所以又用统计学的方法对每个时间片车在路上的情况进行统计，根据统计结果对发车情况进行调整，也有了一些进步。然后针对算法的细节进行了许多的优化，有些方法管用有些没用，复赛训练赛上分到2800+后我们的策略到了极限。这时候，复赛正式赛只剩两天了，听闻大佬们都用上了动态规划，匆忙写了一版出来，大致思路是根据路口的车的多少选择哪个路口发车，之前的思路是每个路口轮流发车，同时每隔一定时间，观察道路利用情况，选择改变部分车辆的路线。匆忙下写出的这版代码的结果连之前的效果都不如，此时也到了复试正式赛的时间了，所以最后放弃了动态规划。

正式赛临时需求变更为允许改变10%预置车的路线，由于比赛现场出现的一些问题，最终没处理这部分车，以之前的策略拿到了第18的成绩。

比赛感想

1 比赛很难，但最难的是坚持，技术不如人，那就花更多的时间。随时关注官方群和论坛，你遇到的问题可能别人也遇到过，看论坛很快可以解决。

2 多和别人沟通，本赛区和其他赛区都可以，做比赛消息很重要，和别人交流的过程中自己也会有很大的收获。

3 算法的稳健性很重要，初赛和复赛正式赛我们的成绩都不如训练赛好，这是因为算法中参数太多，正式赛限定时间内在新地图上无法调参至最优解，所以要尽量减少参数，提高算法的稳键性，把更多的参数消除掉或者让这些参去自适应。

4 代码的稳健性很重要，初赛开始前群里的老师已经说了正式赛Car、Cross、Road中的ID不保证连续，但正式赛开始后还是有很多队伍因为这个原因崩了，其实代码一开始写的时候就考虑到这点或只需在代码中做一个映射就可以了。

5 不可存侥幸心理，复试正式赛开始后我用了之前的一版算法跑出了一个结果上传验证我们的判题器，得到了一致结果，所以一直用新算法在线下调参，比赛快结束上传我们的最好成绩时，结果却在线上死锁。考虑是新算法在整理的过程中不小心动了判题器，导致新算法中的判题器出现了问题。结束前十分钟我们依然没有提交有效成绩，所以针对死锁的地图给了个很宽松的参，总算运行成功，最后就第18了。对我们的判题器过于自信也是复赛成绩差的一个原因，纵然进不了前四，但我们的实际水平应该比这个名次还是要高的。

写在最后

这次比赛真真是见识了很多的大佬，比如杭夏赛区的咕咕咕，一直遥遥领先其他所有队伍，还有西北赛区的我想喝手磨咖啡、咸鱼打挺还有其他赛区的队伍，真是佩服。也通过这次比赛意识到了自己的很多不足，参加比赛既是争取荣誉也是学习，最近有很多大佬在开源，我也是赶紧去学习一波，没准后续再来个“2019华为软件精英挑战赛学习篇”，敬请期待，哈哈哈哈哈哈~~~

无悔！！！2020年华为软件精英挑战赛再会！！！

开源整理后将给出~~~