华为软件精英挑战赛2019
代码链接(https://github.com/chierqj/CodeCraft-2019)
- 赛区：西北赛区
- 队名：赐我一个天命圈
- 名次：初赛（6），复赛（4），决赛32强
前前后大概经历了好几个版本，决赛之前都可以看到地图，所以用了一个线下可以调参的版本。决赛的时候想冲击大奖，导致最后没解开死锁。有点可惜但是没有遗憾。
初赛
思路
初赛思路比较单纯，没有花里胡哨的东西。分组发车 + 判题器调参
- 根据车辆起终点分布进行分类，将所有车分为5类，分别对应四个方向(假设地图拓扑结构已知，右上，右下，左下，左上，非)
- 前四类车，分别限制道路，比如起终点是右上方向的车辆，只限制走向右向上的道路。由于地图原因，会有这四种方向到不了的车辆，这些车辆归为第五类车，即非
- 显然可以得到一个结论，前四类车任意两类车同时存在道路上都必不死锁，因为不会构成环。那么就可以分为三大类 A, B, C
- 这三类车之间控制发车顺序和发车间隔进行调参即可。
- 每一类进行排序发车策略，大致是 根号n分组 + 速度优先，按照速度排序，快车先发原则，分成根号n个块，n表示这一类车的数目。每一个块是同一个发车时间，块和块之间累加一个数字即可。(只要保证慢车不能早于快车即可，根号n比较玄学，实际效果也不错)
- 最终解法就是，预先对每辆车跑dijkstra算法规划路径 + 调参数控制发车间隔
反思
将车辆进行分类控制分组发车，是 西北赛区‘魃魈魁鬾’ 一个师兄想出来的。在初赛阶段+判题器可以取得一个很好的名次。但是还是觉得没有动态规划路径效果好，并且耗费大量时间写好的判题器只是用来调参数有点浪费，果断在复赛阶段就修改算法了。
复赛
均匀发车 + 实时规划 + 回溯解锁
发车策略
采用是均匀发车，除去预制车辆之外，每个时间片可以发车的车辆数目x是均匀的，x作为参数根据判题器调整。复赛大致在60-100之间。
路径规划
- 根据实时路况信息跑dijkstra。路权比较玄学
value = (rate + lock_cost) * (100 / channel) - rate表示当前道路占比，lock_cost表示由于死锁在当前道路上累加的权重，channel表示当前道路宽度。也就只有一个rate是基于判题器获取的实时路况。
- 基于value加了一个 绕城高速的策略 越靠近中心的点觉得使用的越频繁。基于此，将整个道路网格进行分层。最终
value = value / level，最中心level为1，越往外扩展，level越大。效果有显著提升。这里贴一下南京大学某大佬的思路，基于流的思想，太强了。
flow_in = road.vis_count flow_out = sum(channel.lowest_speed) flow_speed = flow_out / flow_in value = length / flow_speed
length : 路长
lowest_speed : min(道路限速，车道的最慢车速)
vis_count : 有多少辆车的答案路径中包含当前道路。动态更新，当有一辆车驶出当前道路时，vis_count–
```
解决死锁
- 对于每一次死锁，找到死锁车辆所在的道路。
- 对于每条道路，增加死锁权重，lock_cost += x, 0 <= x <= 1.0
- 回到p个时间片之前，重新调度车辆。
- 死锁的权重只会影响到 T - p 到 T 这个时间段还没有规划路径的车，因此这个p是个玄学参数，复赛采用的是50
反思
抓不到死锁的本质原因，单纯增加道路权重会造成冗余，造成不必要的影响。
基于这点，决赛时候，不采用权重影响，采用直接变更道路。
决赛
动态发车 + 实时规划 + 回溯解锁
发车策略
采用的阈值限制发车，每一个时间片根据一个阈值来限制发车数目，超过阈值则不发车。这个阈值是根据道路总长度来设定的。大概是 道路总长度的百分之八九十左右 预制车辆不加限制，强行上路。
路径规划
路径规划和复赛没有多大变化，因为解锁采用修改路径(删路)的原则，因此取消了lock_cost这个信息。
解决死锁
- 对于每一次死锁，找到循环等待的车辆形成的环路。
- 对环路的每一条道路x上的所有车辆进行判断，如果这一辆车要驶入的下一条路和当前道路x的死锁车辆要驶入的道路一致，则加入需要修改路径的集合: FIX_CAR_SET
- 对于FIX_CAR_SET的每一辆车，修改要驶入的下一条路，并重新规划到终点的路线。eg: 死锁时: 1001->1002,修改成1001->1003
- 修复完路径之后，回到上一个时间片重新跑判题器即可。
反思
- 这种方法一定程度上解决死锁问题，但是有可能会导致循环死锁，LOCK_A -> LOCK_B -> LOCK_A -> LOCK_B；原因在于每一次面临死锁，解锁的局面是不变的，因此解锁结果也是不变的。（事实是这种死锁最终卡到了决赛结束）
- 解决方法：
- 死锁限制的驶入路径进行累计，死锁一次，就记录死锁限制驶入的道路
- 每一次解锁的时候，历史状态的限制路径也考虑在内。如果因为限制过多导致不能到达终点，那么就对该辆车取消所有限制进行重新规划
- 解锁的车变成，在环路上只有成为第一优先级的车辆，才对其进行重新规划(感觉这个很关键，找到了死锁的关键原因)
这种方法是比赛结束后某友校一个队伍说的，没有实现，他们的效果还是很好的。（对他们表示可惜，他们的实力绝对可以进8强的。但是因为版本控制没做好，找不到最优成绩代码，再加上现场分组分到了死亡分组，实在可惜）
题外话
前前后后经历了50多天，可以说是独自一人完成了整个代码，满满的全是感动和收获。
从没有想过自己能走到决赛的赛场上，复赛当前公布四强的时候，感动的眼眶都湿了。
我们队由于种种原因，90%的工作量都是我一个人完成的，包括想算法，写代码，关注群动态，段子手等等。
很感谢女朋友的理解和支持，因为比赛，陪她的时间几乎为零，但是她一直支持和鼓励我，给了我坚持下去的动力。
很感谢队友的努力和帮助，我们不是最好的，但是我们一定是最努力的。两个队友都是研二的，顶着导师巨大的压力，还参加比赛，很是不容易。某江姓队友初赛完第二天就被导师安排出差了，复赛前一天才回来，就被我拉着讨论，非常辛苦。决赛ai的部分全部是他手撕的，连着也是熬夜了好几晚上，再次感谢队友的努力。另一个余姓队友天天被导师gank还是坚持不懈的一起讨论想算法，段子也是一个接一个，为这个持久战添加了许多有趣的色彩。
很感谢’魃魈魁鬾’刘姓学长，因为之前打了两年ACM就是队友，想法debug什么的都很有默契，所以我们的交流甚至比我和队友还多。没有拿个大奖回来给学长看，也是蛮失落的。
很感谢西北赛区’心有多大路有多宽’队伍，最初我的判题器就是和他们一起讨论出来的，各种规则对不上之类的很头疼，一步一步完善最后全部对上了。
很感谢江山某大佬和臭皮匠四人组的帮助，当时判题器bug，我们四个队伍判题器都对不上，然后对着log看了一下午终于都解决了。江山某大佬的的思路也给了我很大启发。
决赛（游玩）很开心，感谢华为出题组，hr小姐姐们，认识了很多大佬和可爱美丽的小姐姐们。
决赛两天行程安排的满满的，虽然坐车快坐吐了，但是吃喝玩耍也是很开心的。
最后的庆功晚宴也是成功的灌倒了折磨我们的主题组，峰峰老师和康康老师。灌酒之路还未结束，在西安和康康老师继续喝起。
总结
总而言之，这次比赛是一个很棒很精彩的经历。付出很多，收获也很多。存有可惜，但是没有遗憾。
明年再战，西北狼强强强
